### 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

if it isn't possible to split the beer evenly)`infinity`

### 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)

ryuugaon Aug 03, 2010 - 2:02:42 am UTC my solution has WA only for bonus?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

SourSpinachon Aug 03, 2010 - 3:51:52 pm UTC Re: my solution has WA only for bonus?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.

SourSpinachon Aug 03, 2010 - 3:54:58 pm UTC Re: Re: my solution has WA only for bonus?ryuugaon Aug 03, 2010 - 6:19:10 pm UTC Re: Re: my solution has WA only for bonus?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

bbi5291on Aug 07, 2010 - 3:25:03 pm UTC Re: Re: my solution has WA only for bonus?StealthAdepton Dec 05, 2008 - 6:36:34 pm UTC Does Bonus part have to be done for full 10pt?bbi5291on Dec 09, 2008 - 11:47:03 pm UTC Re: Does Bonus part have to be done for full 10pt?