Currency Exchange
货币 兑换
Time Limit: 1000MS
Memory Limit:
30000K
Total Submissions:
8269
Accepted: 2693
Description
Several currency exchange points are working in our city. Let us suppose that each
point specializes in two particular currencies and performs exchange operations only
专业 特定 货币 执行 操作
with these currencies. There can be several points specializing in the same pair of
currencies. Each point has its own exchange rates, exchange rate of A to B is the
quantity of B you get for 1A. Also each exchange point has some commission, the
数量 手续费
sum you have to pay for your exchange operation. Commission is always collected in
source currency.
源
For example, if you want to exchange 100 US Dollars into Russian Rubles at the
exchange point, where the exchange rate is 29.75, and the commission is 0.39 you
will get (100 - 0.39) * 29.75 = 2963.3975RUR.
You surely know that there are N different currencies you can deal with in our city.
处理
Let us assign unique integer number from 1 to N to each currency. Then each
分配 特有的
exchange point can be described with 6 numbers: integer A and B - numbers of
currencies it exchanges, and real R
AB
, C
AB
, R
BA
and C
BA
- exchange rates and
交换的货币数量 R
AB
R
BA
commissions when exchanging A to B and B to A respectively.
C
AB
C
BA
分别
Nick has some money in currency S and wonders if he can somehow, after some
在某种程度上
exchange operations, increase his capital. Of course, he wants to have his money in
资本
currency S in the end. Help him to answer this difficult question. Nick must
最终要持有货币 S
always have non-negative sum of money while making his operations.
没有负资产