New Year's '15 P4 - Leftover Eggnog - Olympiads Online Judge

New Year's '15 P4 - Leftover Eggnog

View as PDF

Submit solution

All submissions

Best submissions

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$ $M$ $(1 \le M \le 1\,000)$ $(1 \leq M \leq 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$ $A$ and $B$ $B$ . He knows $A$ $A$ can hold $V_A$ $V_{A}$ $(1 \le V_A \le 1\,000)$ $(1 \leq V_{A} \leq 1 000)$ milliliters of eggnog, and $B$ $B$ can hold $V_B$ $V_{B}$ $(1 \le V_B \le 1\,000)$ $(1 \leq V_{B} \leq 1 000)$ .

Inaho can perform 3 operations:

fill I - Inaho fills cup $I$ $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$ $I$ into cup $J$ $J$ . Any leftover remains in cup $I$ $I$ .
chug I - With all his festive spirit Inaho downs cup $I$ $I$ , completely emptying it.

Knowing this, he can perform any number of operations on the containers with the goal of making one contain $M$ $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$ $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_{A}$ , $V_B$ $V_{B}$ , and $M$ $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$ $M$ , output Not possible.

Sample Input 1

Copy

100 1000 200

Sample Output 1

Copy

fill A
pour A B
fill A
pour A B

Sample Input 2

Copy

300 500 400

Sample Output 2

Copy

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

Sample Input 3

Copy

100 200 500

Sample Output 3

Copy

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?