DMPG '15 S6 - Apples to Oranges

View as PDF

Submit solution


Points:17 (partial)
Time limit:3.0s
Memory limit:256M
Authors:

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's visit 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 orange → 0.5 apples
  • 1 apple → 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 orange → 2 apples
  • 1 apple → 0.5 oranges
  • 1 apple → 1 grape
  • 1 grape → 1 orange

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

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 (2 \le N \le 500), the number of different types of fruit, and M (2 \le M \le 4\,000), the number of exchange rates.

The next N lines will each contain the name of a fruit, no longer than 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 lines will contain an exchange in the space-separated form of a, b, c, indicating that fruit a may be exchanged for c (0.0 < c \le 10\,000.0) units of fruit b.

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.0
APPLES ORANGE 0.5
APPLES GRAPE 1.0
GRAPE ORANGE 0.5

Sample Output

NAW

Comments


  • 0
    TheZombieCloud
     commented on June 25, 2017

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


    • 0
      eric574
       commented on June 25, 2017

      Have you considered decimals?


      • 0
        TheZombieCloud
         commented on June 25, 2017

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


        • 2
          eric574
           commented on June 25, 2017 edit 2

          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 simply involves performing a BFS, 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)


  • -1
    cranberrysauce26
     commented on June 20, 2017

    Decimals are a pain in the ass


  • 0
    root
     commented on June 18, 2017 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.


    • 1
      wleung_bvg
       commented on June 18, 2017

      The exchange rates are decimals


      • 0
        root
         commented on June 18, 2017

        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.


  • 0
    Ninjaclasher
     commented on June 18, 2017

    Am I missing something really big here? I have no clue what's wrong......and the fact that there's no output doesn't help it the slightest.


    • 1
      wleung_bvg
       commented on June 18, 2017

      I just ran your submission. It's essentially correct, except that you need to deal with floating point precision when exiting BFS (something like 1e-6 should work).


      • 2
        Ninjaclasher
         commented on June 18, 2017

        Thanks so much! Such an easy fix that I would have never found....but now comes the real question....how does a few extra decimal places affect the final result?


  • -3
    root
     commented on June 18, 2017 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.


  • 1
    atarw
     commented on March 27, 2016
    trading partial fruits

    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?


    • 1
      arock
       commented on March 27, 2016

      Yes


  • -1
    XIAOAGE
     commented on Dec. 27, 2015 edited
    No judge ?

    So sad....................should check it b4 code this......

    oh, i guess every problem doesn't have judge at the moment LOL nvm


  • 5
    bruce
     commented on June 23, 2015
    Description conflicts with test case

    In description, M <= 1000. But there are at least 3 cases M > 1000.


    • 1
      Xyene
       commented on June 25, 2015

      Thanks for noticing: the upper bound for M is 4000. I've updated the problem statement.


  • 0
    BMP
     commented on May 30, 2015
    Trading Back

    Can you trade back?

    1 Grape = 3 Oranges.

    Is this equivalent to:

    3 Oranges = 1 Grape?


    • 8
      jimgao
       commented on Dec. 28, 2015

      NAW


    • 1
      Xyene
       commented on May 30, 2015

      No.


  • -2
    ThorhillTeam3_15
     commented on May 28, 2015
    partial fruits

    is it possible for him to exchange a single apple for half an orange for example?


    • 2
      Xyene
       commented on May 28, 2015

      Yes.