239 - Tempus et mobilius. Time and motion

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
vanessa
New poster
Posts: 1
Joined: Fri Jul 16, 2004 9:57 am

239 - Tempus et mobilius. Time and motion

Post by vanessa » Fri Jul 16, 2004 10:05 am

Hi all... what is the output for this

Code: Select all

354
1027
1400
2000
2500
3400
5321
6000
6700
7000
thx

seedman
New poster
Posts: 3
Joined: Thu Sep 22, 2005 4:52 pm

Post by seedman » Fri Oct 14, 2005 9:57 am

354 balls cycle after 4616520 days.
1027 balls cycle after 10811920 days.
1400 balls cycle after 2520540 days.
2000 balls cycle after 489940 days.
2500 balls cycle after 349605 days.
3400 balls cycle after 3960198 days.
5321 balls cycle after 105969950976 days.
6000 balls cycle after 5925 days.
6700 balls cycle after 124080589096182 days.
7000 balls cycle after 207574488 days.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 239 - Tempus et mobilius. Time and motion

Post by brianfry713 » Wed Dec 03, 2014 11:15 pm

You only need to simulate the clock for 12 hours, from that you generate the permutation array.
Then keep applying the entire permutation array to all balls until all balls have cycled at least once. You only have to check them at the end of each day.
Then you have the cycle length of each ball and compute the LCM of that for all balls.
For 7000 balls, it will take 6281 days for all balls to cycle at least once.
My AC code takes 0.3 seconds to generate the output for 7000 balls.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 239 - Tempus et mobilius. Time and motion

Post by brianfry713 » Wed Dec 03, 2014 11:27 pm

My approach above got AC in 0.228 seconds.

To optimize even further, iterate each ball individually through the permutation array and calculate the cycle length.
Mark each location as visited so you don't have to repeat the same permutation loops.
All of the cycle lengths can be computed in O(N) instead of O(N * N).
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 2 (200-299)”