New Year's '15 P4 - Leftover Eggnog

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 2.5s
Memory limit: 64M
Author:
Xyene
Problem type

What few people know is that Inaho is a fan of eggnog. He's also a fan of sales. It stands to reason, therefore, that the last time eggnog was on sale Inaho stockpiled dozens of cartons of eggnog. With the holiday season drawing to a close, he's found himself left with many a carton of eggnog nearing its expiration date. Since Inaho doesn't like expired eggnog, he's decided to serve the eggnog at the New Year's party he'll soon be attending.

Inaho has a large assortment of eggnog, but he's lacking in one area: he does not have any graded container or any means to determine volume. Specifically, every person who wants eggnog wants exactly M (1 \le M \le 1\,000) milliliters of it, but without a way to measure eggnog Inaho has looked to you for help in distributing his eggnog.

He has two cups with which to handle eggnog in, A and B. He knows A can hold V_A (1 \le V_A \le 1\,000) milliliters of eggnog, and B can hold V_B (1 \le V_B \le 1\,000).

Inaho can perform 3 operations:

  • fill I - Inaho fills cup I up to the brim with eggnog. He has so much eggnog on hand that he can do this an infinite number of times.
  • pour I J - Inaho pours the contents of cup I into cup J. Any leftover remains in cup I.
  • chug I - With all his festive spirit Inaho downs cup I, completely emptying it.

Knowing this, he can perform any number of operations on the containers with the goal of making one contain M milliliters.

Since he knows that there will be many people at the party, he'd like to streamline the serving process by knowing exactly which operations he'll perform for a given M. Of course, he'd also like to perform as few operations as he can. He's busy packing his eggnog though, so he's asked you to come up with this sequence of operations for him.

Input Specification

The first and only line of input will contain 3 space-separated integers: V_A, V_B, and M.

Output Specification

The list of operations Inaho should perform, with each item on a new line. There may be multiple shortest operation lists, and outputting any is acceptable. If it is impossible to get M, output Not possible.

Sample Input 1

100 1000 200

Sample Output 1

fill A
pour A B
fill A
pour A B

Sample Input 2

300 500 400

Sample Output 2

fill B
pour B A
chug A
pour B A
fill B
pour B A

Sample Input 3

100 200 500

Sample Output 3

Not possible

Comments


  • 0
    tappbros  commented on Feb. 10, 2022, 1:38 a.m.

    Ah yes, I too would want to drink an entire litre of eggnog.


  • 3
    Oppenheimer  commented on Jan. 2, 2015, 8:46 p.m.

    Will A be always less than B?


    • 5
      snowblind  commented on Jan. 2, 2015, 8:59 p.m.

      no


  • 5
    omaewamoushindeiru  commented on Jan. 2, 2015, 7:24 p.m.

    msa789 thought this question was called 'eggroll'


    • 10
      Xyene  commented on Jan. 2, 2015, 7:54 p.m.

      I guess it could've been, but I like eggnog more.


      • 6
        FatalEagle  commented on Jan. 2, 2015, 7:57 p.m.

        Are you the real Inaho?