📄 problem 1705.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0047)http://acm.zju.edu.cn/show_problem.php?pid=1705 -->
<HTML><HEAD><TITLE>Problem 1705</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2900.3199" name=GENERATOR></HEAD>
<BODY>
<CENTER><IMG src="Problem 1705.files/logo.gif" align=center></IMG></CENTER>
<HR>
<CENTER><FONT color=blue size=+2>Exchange Rates</FONT></CENTER>
<HR>
<CENTER><FONT color=green>Time limit:</FONT> 1 Seconds <FONT
color=green>Memory limit: </FONT>32768K </FONT><BR><FONT
color=green>Total Submit:</FONT> 142 <FONT color=green>Accepted
Submit:</FONT> 91 </CENTER>
<HR>
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.)
<P>Your job is to write a program that, given a list of exchange rates,
calculates the exchange rate between any two items. </P>
<P><BR><B>Input</B></P>
<P>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 </P>
<P>! m itema = n itemb<BR><BR>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
<BR><BR>? itema = itemb<BR><BR>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). </P>
<P><B><BR>Output</B></P>
<P>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. <BR><BR>Note: </P>
<P>>Item names will have length at most 20 and will contain only lowercase
letters. <BR>>Only the singular form of an item name will be used (no
plurals). <BR>>There will be at most 60 distinct items. <BR>>There will be
at most one assertion for any pair of distinct items. <BR>>There will be no
contradictory assertions. For example, "2 pig = 1 cow", "2 cow = 1 horse", and
"2 horse = 3 pig" are contradictory. <BR>>Assertions are not necessarily in
lowest terms, but output must be. <BR>>Although assertions use numbers less
than 100, queries may result in larger numbers that will not exceed 10000 when
reduced to lowest terms. </P>
<P><BR><B>Sample Input</B></P>
<P>! 6 shirt = 15 sock<BR>! 47 underwear = 9 pant<BR>? sock = shirt<BR>? shirt =
pant<BR>! 2 sock = 1 underwear<BR>? pant = shirt<BR>.</P>
<P><BR><B>Sample Output</B></P>
<P>5 sock = 2 shirt<BR>? shirt = ? pant<BR>45 pant = 188 shirt<BR></P>
<HR>
<FONT color=green size=+1>Problem Source: </FONT><I>Mid-Central USA 1999</I>
<HR>
<CENTER><A href="http://acm.zju.edu.cn/submit.php?pid=1705">Submit</A>
<A href="http://acm.zju.edu.cn/list_problem.php?vol=8">Back</A>
<A
href="http://acm.zju.edu.cn/problem_status.php?pid=1705">Status</A> </CENTER>
<HR>
<CENTER>
<TABLE width="100%" border=0>
<TBODY>
<TR>
<TD align=right width="65%"><A href="http://acm.zju.edu.cn/"><FONT
color=red>Zhejiang University Online Judge</FONT></A> <A
href="http://acm.zju.edu.cn/"><FONT color=red>V1.0</FONT></A></TD>
<TD align=right width="35%"><A href="http://www.zzhang.cn/"><FONT
color=#ffffff
size=-3>Book</FONT></A></TD></TR></TBODY></TABLE></CENTER></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -