Given some N, you want to split it in terms t1, t2, ..., tn where each term represents a cycle of arrows between circles. The number of steps in the dance corresponds to lcm(t1, t2, ..., tn) and this is what we want to maximize.
For N = 9, you could split it into 4 and 5, giving lcm(4, 5) = 20 For N = 12, you could split it into 3, 4, 5, giving lcm(3, 4, 5) = 3 * 4 * 5 = 60 For N = 15, you could split it into 3, 5, 7 giving lcm(3, 5, 7) = 3 * 5 * 7 = 105 I am not really sure about the optimal strategy - the simplest is a brute force but that's likely too slow for large values of N. I suspect you need to split N into terms such that each term is on the form P^x where P is a unique prime. On Sat, Aug 4, 2012 at 5:27 AM, Tejeshwar Singh <[email protected]>wrote: > The director of Hind Circus has decided to add a new performance called > the monkey > dance to his show. The monkey dance is danced simultaneously by N monkeys. > There are N circles drawn on the ground. There are N arrows drawn between > the > circles in such a way that for each circle, exactly one arrow begins at > that circle and > exactly one arrow ends at that circle. No arrow can both begin and end at > the same > circle. > When the show begins, each monkey sits on a different circle. At each > whistle of the > ringmaster, all the monkeys simultaneously jump from one circle to the > next, following > the arrow leading out of the current circle. This is one step of the > dance. The dance > ends when all the monkeys have simultaneously returned to the circles > where they > initially started. > The director wishes the dance to last as many steps as possible. This can > be achieved > by drawing the arrows intelligently. > For each of the three values of N given below, what is the maximum number > of steps > that the monkey dance can be made to last by drawing arrows appropriately? > (a) 9 (b) 12 (c) 15 > > PLS REPLY WITH A FIGURE TO HELP ME UNDERSTAND! > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msg/google-code/-/CD_ilH2yB8oJ. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
