Internet Problem Solving Contest

• Correct output – A1
• Correct output – A2
• Python program solving both data sets

To solve the easy input simulating the war was enough. For the hard input it was better to realize that the order in which monsters are killed is simply the order according to their increasing strength.

Denote S_g the maximum strength of a monster from Godzilla’s army and S_m the maximum strength of a MechaGodzilla’s monster. If S_g ≥ S_m, all MechaGodzilla’s monsters will die before Godzilla’s strongest one and thus Godzilla wins. Otherwise, MechaGodzilla wins for the same reason.