I have got problem with this task from my university algorithm course (translated from german):
> John have got a party. He prepared $x$ glasses of vodka and $k*x$
> glasses of rum.
>
> Number of glasses is n. Each guests drink one
> round of alcohol (one round is $k$ glasses of rum and $one$ of vodka) but
> guest must chose glass that every full glass must have got one full
> neighbor.
>
> Write the program which simulate John's party. The party ends when all
> glasses are empty.
>
> In input we have got $n$ and $k$ which means number of glasses and number
> of glasses of rum drunk in single turn).
Simple Input : (assume that r is rum and v - vodka ).
> 16 3 vvrrrvrvrrrrrrrr
Simple Output : (we numbered glass 1...n)
> 1 14 15 16
> 2 11 12 13
> 3 4 5 6
> 7 8 9 10
Explain :
Guest 1 drink 1, 14, 15 and 16 glass.
Guest 2 drink 2, 11, 12, 13 glass.
etc.
We write it in ascending order. Notice that we have got $\frac{n}{(k+1)}$ guests, $n$ glasses, $k$ glasses of rum in every round. And in all inputs $k+1$ divides $n$. And $n$ can be very big - about 2 000 000. And we have about 1-2s to answer the question.
Find the fastest as possible algorithm to solve this problem.
Thanks for every help. If you have got any questions, i will answer it.
Edger.
