Woburn Challenge 2001 - Suicidal

Thursday night — Blind Date

Ah, it's the end of frosh week and love is in the air. New couples are forming everywhere and everyone is happy. Hi, I'm Roger Lodge. Let's meet our couple, shall we? Simon is a Computer Engineering frosh who has a "fetish" for precision. His favourite books are "Advanced Number theory" and "The Hermit, The Hospital and The Place: baby names for mathematicians". Simone is an electrical engineering frosh who likes sparks to fly on the first date. She likes to mix psychology with physics and is currently reading "Jung on Young" and "Freud and the solenoid". Yikes.

Simon and Simone are at dinner. When their drinks (ie. beer) arrive, it is in a large glass that holds 2N litres (the glass is full). In addition, the waiter has been kind enough to supply 2 other glasses: a small one that holds N-K litres and a medium one holding N+K litres, where 0 < K < N.

These 2 glasses are empty. Simon, being very precise, wants to pour exactly the same amount of beer for him and his date (so that there are exactly N litres left in the large and medium sized glasses). However, the only measuring devices he has are the 3 glasses.

Since the jugs are not calibrated, the only way that he can know how much volume he is pouring is by emptying a jug fully or filling another jug fully. Dr. Love says that Simon hasn't been to the gym in a while (he's been too busy reading early 21st century literature), and so he finds the jugs heavy and wants to minimize lifting a glass and pouring it. Plus, he doesn't want to go pouring back and forth like an idiot, if it isn't even possible to split the beer evenly.

Input

N K (0 < K < N < 4000; -1 -1 denotes end of input)

Bonus

Josh, another Waterloo keener, has solved this program for 0 < K < N < 64000. Simon doesn't want to lose his reputation as the class nerd, so he's desperate to repeat this feat. If you can help him, you'll get twice as many points.

Output

P (P = the minimum number of pours will fit within a longint; output infinity if it isn't possible to split the beer evenly)

Sample Input

2 1
3 1
-1 -1

Sample Output

3
infinity

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 32M
Added: Dec 05, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

My solution runs within time and memory constraints(after realizing that solution wasn't actually O(n^2 or n^3) time and memory), but gives WA for the bonus, and not the regular cases.


My solution doesn't seem to have any mistakes. It covers all of the cases (small->medium, small->large, 4 others, assert() show it is completely filling or emptying at least one pitcher after each pour, as stated) and fits within memory, time constraints.
assert() shows amount of beer does not become negative or exceed capacity of cups, so cases seem to be handled correctly.
There is no reason for integer overflow to happen for n< 64000, since separate integers are used for each cup.

--This leaves me with no idea of what could be wrong, except the judge, or some ridiculously tiny detail I overlooked

Well, I don't know what to say - Hanson agrees with the output that we had for this problem, and he's Hanson.

You only get 1 of the 6 sub-cases wrong (the 3rd one, which is close to the limit), in which you output a fairly large number instead of infinity.

I don't know which of you is right, but I wouldn't worry too much about it if I were you.

However, I do notice that Hanson's solution is different than yours, and it most definitely uses a small-enough amount of time and memory, while yours seems a bit uncertain. Plus, it's Hanson.

??? did you even look at the third test case when you said that?
 The third could easily be solved by hand, unlike the others
In the third line of second test case(sorry about getting it on my own), 
there are two large numbers n, k, where k = n-1

That means there is one jug with n-k = n-(n-1) = 1 unit of capacity, and another jug with n+k = n+(n-1) = 2n - 1 units of capacity

Since there is a jug with a capacity of one, IT MUST BE POSSIBLE to pour n units
So there is no way it could be infinity

One possible solution involves pouring 1 from L->S and S->M n times. This is rather obvious, and takes 2n steps, but is not optimal
Another possible solution involves pouring as much as possible from larger to medium (size n+(n-1)) then pouring 1 from M->S, then S->L (n-1) times.
This takes 1 + 2*(n-1) = 2n-1 steps, and is optimal. This is the answer my program gets by simulation in my solution

There must be a bug in hanson's code if he says its infinity. (it is a border case, after all)
Please correct the judge for that case and test most recent 10/20 submission. Or did you not mean the third, but some other one

*S(size    1) represents small
M (size 2n-1) represents medium
L (size 2n  ) represents large

I agree with you, Hanson must be wrong somehow. It's fixed.

It appears you'll get half the points if you don't do the bonus.