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! -- 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/7534f519-c83b-4428-81b4-3ad749534627%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
