ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1474. About Frogs

Have you any tricks how to solve?
Posted by SkorKNURE 5 Apr 2008 19:48
Subj
Re: Have you any tricks how to solve?
Posted by Vedernikoff Sergey 8 Apr 2008 10:50
No, just bruteforce...
Re: Have you any tricks how to solve?
Posted by SkorKNURE 9 Apr 2008 06:24
>No, just bruteforce...
A little optimized bruteforce gave me TLE in 'n' < ~20

There is a simple pattern in frogs moving. Paper simulation is so bored pastime - I had found out the pattern when wrote simple bruteforce for small 'n' cases.
GL :)
Re: Have you any tricks how to solve?
Posted by MarX 27 Jul 2015 10:45
I found a pattern on the movemente...
move first black frog
Then: move  first & second white frog
then: move first & second & third black frog
keep doing this until the end

while doing that:
   always start for the first frog that hasn't arrive to their final position
   always end if you don't have anymore frogs to move

example with 2 and 3

8
1 3 4 2 0 1 3 2

15
2 4 5 3 1 0 2 4 6 5 3 1 2 4 3

Good luck