10726 - Coco Monkey

Arm.Turbo · Post by **Arm.Turbo** » Wed Sep 22, 2004 10:46 am

I AC for this problem but my algorithm is slow. In ranklist for this problem i saw results 0.000 seconds. Is there exist analitical solution? I.e. simple equation?

Per · Post by **Per** » Wed Sep 22, 2004 10:52 am

Yeah, there is an analytical solution. Hint: for fixed S and M, look for a pattern in the possible values of C.

little joey · Post by **little joey** » Wed Sep 22, 2004 11:09 am

Is zero coconuts acceptable at any stage? I think the text is not clear about it.
In other words:
- for 2 sailors and no monkeys, is 0 coconuts acceptable?
- for 2 sailors and one monkey, is 3 coconuts acceptable?

Guess I could try both alternatives, or did I overlook someting in the text?

Per · Post by **Per** » Wed Sep 22, 2004 11:16 am

little joey wrote:- for 2 sailors and no monkeys, is 0 coconuts acceptable?
- for 2 sailors and one monkey, is 3 coconuts acceptable?

Yes in both cases. The only thing that matters is that every sailor gets M coconuts left after dividing the coconuts evenly in the S baskets (even if he gets 0 coconuts in each basket).

circle · Post by **circle** » Mon Oct 04, 2004 3:08 pm

I solve it but WA.
Please can anyone give me some critical I/O who got AC.

failor · Post by **failor** » Sat Dec 10, 2005 10:37 am

Per wrote:Yeah, there is an analytical solution. Hint: for fixed S and M, look for a pattern in the possible values of C.

I don't understand .
Will u help me to clear this?

failor · Post by **failor** » Sat Dec 10, 2005 11:10 am

Per wrote:Yeah, there is an analytical solution. Hint: for fixed S and M, look for a pattern in the possible values of C.

What is analytical solution ?
Per or anyone else , will u tell me?
plz.

lonelyone · Post by **lonelyone** » Sat Feb 04, 2006 9:31 am

What's the analytical solution
Any hint in detail, please..

rieo · Post by **rieo** » Mon Aug 21, 2006 8:23 am

can anyone explain case2 and case3?
in case 1, i can understand what it means..

but case 2: 10 -> means S=4 M=2 C=5+10=15, right?
15/4=3...3 left 9.. but 3!=M...
C should be 506, isn't it?
506/4=126...2 left 378
378/4=94.....2 left 282
282/4=70.....2 left 210
210/4=52.....2 left 156
156/4=39.....0

in case 3: 357, means S=6 M=4 C=1+357=358
358/6=59....4 left 295
295/6=49....1 <-- 1!=M

do i misunderstand this problem? can somebody teach me.. thx..

sclo · Post by **sclo** » Wed Oct 04, 2006 1:22 am

lonelyone wrote:What's the analytical solution
Any hint in detail, please..

Observe that if C is a solution, then C + S^(S+1) is also a solution.
So the solutions can be computed mod S^(S+1)
So generally, the solution are of the form S^(S+1)*a + b, where a,b are non-negative integers.
The key is to find out what b is.
Hint: b can be written in terms of S and M and it depends on the parity of S.

OJ Board

10726 - Coco Monkey

10726 - Coco Monkey

how to?