Internet Problem Solving Contest

IPSC 2008

Solution to Problem A – Army Strength

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 Sg the maximum strength of a monster from Godzilla’s army and Sm the maximum strength of a MechaGodzilla’s monster. If Sg Sm, all MechaGodzilla’s monsters will die before Godzilla’s strongest one and thus Godzilla wins. Otherwise, MechaGodzilla wins for the same reason.