A Fair Share
In the holy land of programmers, there once lived two great legends, Ravi and Prashant with their mother (she wasn't a good coder). Once she had a glass of milk filled up to the brim. She wanted to divide that glassful of milk equally between her sons. But she only had two other glasses of distinct capacities with no markings to facilitate measuring lower amounts directly. Your task is to find the optimum solution to distribute the milk equally (optimum=least no. of steps). There might be many solutions available to divide a given quantity but you're required to give the optimum solution.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The only line of input for each test case contains three integers A B C denoting the capacity of each glass.
For every testcase, output following data:
- First line contains Yes/No depending upon whether the problem can be solved, if it is Yes, proceed with remaining output, else, add a new line and continue with the next testcase
- Next lines contain the sequence of pours that must take place, each pour in a separate line.
- Next line contains the count of the total number of steps in the sequence
- 1 ≤ T ≤ 10
- 1 ≤ A,B,C ≤ 100
- Initially, milk is filled in the glass with the highest capacity.
Input: 2 4 3 1 2 3 8 Output: Yes 4->3 3->1 1->4 3 No
Example case 1: The mother will first pour the milk from glass with capacity 4 to glass with capacity 3, so the content of the glasses will become 1 3 0.Then she will pour from glass with capacity 3 to glass with capacity 1, so the content of the glasses will become 1 2 1. Finally, she will pour from glass with capacity 1 to glass with capacity 4, so the content of the glasses will become 2 2 0.
Example case 2: Here she won't be able to divide the milk into equal parts because the capacity of the empty glasses is less than half of filled glasses.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.