DMPG '15 S6 - Apples to Oranges - Olympiads Online Judge

DMPG '15 S6 - Apples to Oranges

View as PDF

Submit solution

All submissions

Best submissions

Points: 17 (partial)

Time limit: 1.4s

Memory limit: 256M

Authors:

Xyene, untitled123

Problem type

They say you cannot compare apples to oranges, but you actually can! In fact, by using money as a medium of exchange, we can compare anything in terms of value. Sun has a single apple. Being the incredibly talented person he is, he visits a variety of markets with different rates of exchange for his apple. His goal is to obtain infinite apples, and therefore total control of the fruit market.

Suppose the rates of exchange are:

$1$ ~1~ orange → $0.5$ ~0.5~ apples
$1$ ~1~ apple → $2$ ~2~ oranges

Then it is easy to see that it is in fact impossible to obtain more than one apple through exchanges.

However, if the exchange is:

$1$ ~1~ orange → $2$ ~2~ apples
$1$ ~1~ apple → $0.5$ ~0.5~ oranges
$1$ ~1~ apple → $1$ ~1~ grape
$1$ ~1~ grape → $1$ ~1~ orange

Then Sun can exchange his original apple for a grape, a grape for an orange, and an orange for $2$ ~2~ apples! He can then repeat this to get infinite apples.

$\text{[math]}$

The next trivial step is to note that he can now dominate and control the entire apple market.

Your goal is to find out if Sun's fruit market domination scheme is feasible.

Input Specification

The first line of input will contain two space-separated integers $N$ ~N~ $(2 \le N \le 500)$ ~(2 \le N \le 500)~, the number of different types of fruit, and $M$ ~M~ $(2 \le M \le 4\,000)$ ~(2 \le M \le 4\,000)~, the number of exchange rates.

The next $N$ ~N~ lines will each contain the name of a fruit, no longer than $25$ ~25~ alphanumeric characters long. Note that Sun starts with one apple, so APPLES will always be a type of fruit given.

Finally, the last $M$ ~M~ lines will contain an exchange in the space-separated form of $a$ ~a~, $b$ ~b~, $c$ ~c~, indicating that fruit $a$ ~a~ may be exchanged for $c$ ~c~ $(0.0 < c \le 20\,000\,000.0)$ ~(0.0 < c \le 20\,000\,000.0)~ units of fruit $b$ ~b~.

Note that $c$ ~c~ will be given to $10$ ~10~ decimal places.

Output Specification

Output YA on a single line if Sun can get infinite apples, or NAW if he can not.

Sample Input

3 4
APPLES
ORANGE
GRAPE
ORANGE APPLES 2.0000000000
APPLES ORANGE 0.5000000000
APPLES GRAPE 1.0000000000
GRAPE ORANGE 0.5000000000

Sample Output

NAW

Comments

0

dxke02 commented on Dec. 12, 2020, 8:22 p.m.

What is wrong with my code? I feel like my approach is probably wrong but I have no clue why it is wrong. Can someone give me a hint as to why my code is failing?

2

DM__Oscar commented on Dec. 12, 2020, 9:17 p.m.

well first of all you seem to be printing "YAW" instead of the required "YA"

0

dxke02 commented on Dec. 12, 2020, 9:45 p.m.

I changed it to "YA" but I only got 80/100, is it because of decimal precision now?

2

DM__Oscar commented on Dec. 12, 2020, 11:27 p.m.

Fun fact: sometimes when comparing floating point numbers, you need to add a little bias value.

3

dxke02 commented on Dec. 13, 2020, 12:41 a.m.

Decimal precision is so hard, I tried playing around with it and I passed the cases that I got wrong before but then now I'm getting different cases wrong now. I'll probably give up soon.

2

OneYearOld commented on July 10, 2020, 3:03 p.m.

What happens if you can get an infinite amount of another fruit, but not infinite apples?

(Example:

1 apple -> 1 grape

1 grape -> 1 orange

1 orange -> 2 grapes

In this scenario, you can get infinite grapes but not infinite apples.)

7

wleung_bvg commented on July 10, 2020, 3:42 p.m.

It does not matter whether or not you can get infinite grapes; it has no direct effect on the output. The output depends on whether you can make infinite apples or not.

In the specific example you provided, the output is NAW because you cannot get infinite apples.

0

Chess1000 commented on July 29, 2019, 1:26 p.m. ← edit 2 →

I have two questions.

Is it possible for a fruit to be exchanged for itself? For example, ORANGE ORANGE 0.9.

Is it always possible to exchange something for "APPLES"? Could there be the possibility that nothing can be exchanged for apples? In a similar way, is there always a path to apples from apples?

Edit: I solved it by using a solution that works in any case.

6

discoverMe commented on July 29, 2019, 7:51 p.m.

NAW

27

little_prince commented on March 28, 2018, 2:03 p.m. ← edit 5 →

Weak cases. Also one of the cases has M>4000

1

AussieSeaweed commented on March 18, 2018, 2:59 a.m.

Help

Can anyone please check my code and see what I am doing wrong? Thanks in advance.

4

Evan_Yu123 commented on Sept. 6, 2017, 12:50 a.m.

Is double accurate enough for this question?

1

Pleedoh commented on Sept. 6, 2017, 3:13 p.m.

Yes.

1

Evan_Yu123 commented on Sept. 6, 2017, 8:25 p.m.

Thx

-1

TheZombieCloud commented on June 25, 2017, 9:07 p.m.

I've been stuck on this problem for a few hours now. Is my idea wrong or is it something else?

1

eric574 commented on June 26, 2017, 12:30 a.m.

Have you considered decimals?

0

TheZombieCloud commented on June 26, 2017, 2:27 a.m.

I think so. I've used double to for the decimals. Idk if the decimals would be long enough for some precision errors though.

4

eric574 commented on June 26, 2017, 3:12 a.m. ← edit 3 →

I checked your code and the problem doesn't seem to be decimals. In fact, some parts of your code seem to be unnecessary. The problem involves performing a BFS (or a similar SSSP algorithm), which means that you don't have to check for the indegree or outdegree. Also, optimize your code a bit and you will AC. (Try using a HashMap)

-7

cranberrysauce26 commented on June 20, 2017, 11:22 a.m.

Decimals are a pain in the ass

This comment is hidden due to too much negative feedback. Show it anyway.

30

pwnclub commented on June 25, 2017, 11:53 p.m.

https://www.youtube.com/watch?v=hpigjnKl7nI

2

root commented on June 18, 2017, 11:10 p.m. ← edited →

What exactly is the format of the input? The sample case seems to imply that ".0" will be included in the case that it is an integer. However, experimentation says otherwise.

2

wleung_bvg commented on June 18, 2017, 11:52 p.m.

The exchange rates are decimals

2

root commented on June 19, 2017, 12:14 a.m.

Thanks, I know that they are decimals, the issue seems to be with the format string, in theory, it should work with integers and decimals.

-4

root commented on June 18, 2017, 5:51 p.m. ← edit 2 →

Hint: If you're like me, and tried to scan the input as two integers separated by a dot, be aware that the input contains input like "1e-6". And a note to future problem setters, please, if only for my sanity alone, mention it in the problem statement if you have numbers like that. I wasted eight hours today on this one problem.

4

atarw commented on March 27, 2016, 7:30 p.m.

if I have 0.5 of fruit A, and the exchange rate between fruit A and fruit B is 1:2, does that mean that I can trade 0.5 of fruit A for 1 of fruit B?