ZOJ Problem Set - 1705
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
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.
>Item names will have length at most 20 and will contain only lowercase
! 6 shirt = 15 sock
5 sock = 2 shirt
Source: Mid-Central USA 1999