By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,657 Members | 869 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,657 IT Pros & Developers. It's quick & easy.

Please help me to solve "Exchange Rates Problem"

P: 4
Exchange Rates

Source file: Exchange.cs
Input file: Exchange.in
Output file: Exchange.out

Using money to pay for goods and services usually makes life easier, but sometimes people prefer to trade items directly without any money changing hands. In order to ensure a consistent "price", traders set an exchange rate between items. The exchange rate between two items A and B is expressed as two positive integers m and n, and says that m of item A is worth n of item B. For example, 2 stoves might be worth 3 refrigerators. (Mathematically, 1 stove is worth 1.5 refrigerators, but since it's hard to find half a refrigerator, exchange rates are always expressed using integers.)

Your job is to write a program that, given a list of exchange rates, calculates the exchange rate between any two items.

The input file contains one or more commands, followed by a line beginning with a period that signals the end of the file. Each command is on a line by itself and is either an assertion or a query. An assertion begins with an exclamation point and has the format
! m itema = n itemb
where itema and itemb are distinct item names and m and n are both positive integers less than 100. This command says that m of itema are worth n of itemb. A query begins with a question mark, is of the form
? itema = itemb
and asks for the exchange rate between itema and itemb, where itema and itemb are distinct items that have both appeared in previous assertions (although not necessarily the same assertion). For each query, output the exchange rate between itema and itemb based on all the assertions made up to that point. Exchange rates must be in integers and must be reduced to lowest terms. If no exchange rate can be determined at that point, use question marks instead of integers.
Format all output exactly as shown in the example.

Note:

Item names will have length at most 20 and will contain only lowercase letters. l
Only the singular form of an item name will be used (no plurals). l
There will be at most 60 distinct items. l
There will be at most one assertion for any pair of distinct items. l
There will be no contradictory assertions. For example, "2 pig = 1 cow", "2 cow = 1 horse", and "2 horse = 3 pig" are contradictory.
Assertions are not necessarily in lowest terms, but output must be.
Although assertions use numbers less than 100, queries may result in larger numbers that will
not exceed 10000 when reduced to lowest terms.


Example input

! 6 shirt = 15 sock
! 47 underwear = 9 pant
? sock = shirt
? shirt = pant
! 2 sock = 1 underwear
? pant = shirt
.
Example output:
5 sock = 2 shirt
? shirt = ? pant
45 pant = 188 shirt
Aug 13 '07 #1
Share this Question
Share on Google+
5 Replies


sicarie
Expert Mod 2.5K+
P: 4,677
Sure, what do you have so far?
Aug 13 '07 #2

P: 4
Sure, what do you have so far?
thanks for reply.....
I'm not able to understand how should i calculate values if they are present in 3 or 4 statements.
Aug 13 '07 #3

sicarie
Expert Mod 2.5K+
P: 4,677
thanks for reply.....
I'm not able to understand how should i calculate values if they are present in 3 or 4 statements.
The best way to figure something like that out, is to ignore the programming for a bit, and sit down and figure out how you would write instructions for a child to do it.

I would imagine you could go about this several ways. You could create a relation for each of the 60 items, or you could go through and build the relation for the current item (if you know which one you are searching for, you can search each line for that one. Then see if there is a direct comparison between the two. If there's not, go to the next on one, see if there is a valid comparison (if if they both compare to the same item), etc... until you have a match.

Are you having trouble with the logic (like above), or the implementation?
Aug 13 '07 #4

P: 4
The best way to figure something like that out, is to ignore the programming for a bit, and sit down and figure out how you would write instructions for a child to do it.

I would imagine you could go about this several ways. You could create a relation for each of the 60 items, or you could go through and build the relation for the current item (if you know which one you are searching for, you can search each line for that one. Then see if there is a direct comparison between the two. If there's not, go to the next on one, see if there is a valid comparison (if if they both compare to the same item), etc... until you have a match.

Are you having trouble with the logic (like above), or the implementation?
I'm clear with the logic, but I'm feeling difficulty in implementation.
Aug 13 '07 #5

sicarie
Expert Mod 2.5K+
P: 4,677
I'm clear with the logic, but I'm feeling difficulty in implementation.
Oh, ok, what is your algorithm?
Aug 13 '07 #6

Post your reply

Sign in to post your reply or Sign up for a free account.