在 2015年6月11日星期四 UTC-7下午1:02:09，Jing Huang写道： > I used the dynamic programming approach to solve the problem, but my program > failed at the following input for large data: > > 7 36 > > The correct output is 16 while my output is 24. > > This test case could be reduced to the input of > > 7 12 > > where the correct output (by the programs from others) is 16 and my output is > still 24. > > However, when I try to check the result by hand using the following > representation: > > Block A2 (period = 1) > 333333333333 > 333333333333 > > Block B3 (period = 4) > 222122212221 > 212121212121 > 212221222122 > > Block C2 (period = 3) > 221221221221 > 221221221221 > > Block D2 (period = 6) > 211222211222 > 222211222211 > > Block E1 (period = 1) > 222222222222 > > I get the following results: > > Input 4 12 > Output 5 (Correct) > 1: A2 + C2 > 2: A2 + D2 > 3: C2 + A2 > 4: D2 + A2 > 5: E1 + A2 + E1 > > Input 5 12 > Output 7 (Correct) > 1: A2 + B3 > 2: A2 + E1 + A2 > 3: B3 + A2 > 4: C2 + A2 + E1 > 5: D2 + A2 + E1 > 6: E1 + A2 + C2 > 7: E1 + A2 + D2 > > Input 6 12 > Output 21 (Correct) > 1: A2 + C2 + A2 (p3 +) (Note: p3 means period = 3, + means ended with A2) > 2: A2 + D2 + A2 (p6 +) > 3: A2 + E1 + A2 + E1 (p1) > 4: B3 + A2 + E1 (p4) > 5,6,7: C2 + A2 + D2 (p6) > 8,9,10: C2 + A2 + C2 (p3) > 11,12,13: D2 + A2 + C2 (p6) > 14,15,16,17,18,19: D2 + A2 + D2 (p6) > 20: E1 + A2 + B3 (p4) > 21: E1 + A2 + E1 + A2 (p1 +) > > Input 7 12 > Output 24 (Incorrect) > 1: A2 + B3 + A2 (p4 +) > 2: A2 + C2 + A2 + E1 (p3) > 3: A2 + D2 + A2 + E1 (p6) > 4: A2 + E1 + A2 + C2 (p3) > 5: A2 + E1 + A2 + D2 (p6) > 6,7,8: B3 + A2 + C2 (p12) (3 combinations) > 9,10,11,12: B3 + A2 + D2 (p12) (4 combinations) > 13,14,15: C2 + A2 + B3 (p12) (3 combinations) > 16,17,18,19: D2 + A2 + B3 (p12) (4 combinations) > 20: C2 + A2 + E1 + A2 (p3 +) > 21: D2 + A2 + E1 + A2 (p6 +) > 22: E1 + A2 + C2 + A2 (p3 +) > 23: E1 + A2 + D2 + A2 (p6 +) > 24: E1 + A2 + E1 + A2 + E1 (p1) > > I still cannot figure out what cases among the 24 I listed are duplicated or > wrong. Could anybody point it out for me? > > Thanks in advance!
I finally know where I was wrong thanks to Mikhail Goncharov's answer on Google+: E.g. d2 + a2 + b3 gives you only 2 combinations = gcd(4, 6) not min(4, 6) -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/f8fe6334-70ad-474c-b2ac-832d47df5bc7%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
