Problema 5: Míssil

Arquivo: missil.c ou missil.pas
Entrada: missil.in
Saída: missil.out

O Departamento de Defesa americano está terminando os testes preliminares de um novo míssil defensivo chamado ``the catcher'' que é capaz de interceptar diversos mísseis vindos ao mesmo tempo. Os militares reputam que o ``catcher'' é um excelente míssil defensivo. Ele pode se mover para frente, para o lado e para trás muito rapidamente, e pode interceptar um míssil inimigo sem ser destruído. Mas o míssil tem um grande problema. Embora ele possa ser lançado para atingir qualquer elevação inicial, ele não tem energia para ir mais alto do que o último míssil que ele interceptou.

Os testes feitos pelo Depto. de Defesa foram simulações por computador de condições de batalha e ataque hostil. Como eram testes preliminares, as simulações testavam somente a capacidade do catcher se mover verticalmente. Em cada simulação atiravam contra o catcher uma seqüência de mísseis hostis que vinham em intervalos fixos de tempo. A única informação que o catcher tinha era a seqüência de mísseis e a altura de cada um deles.

O resultado de cada teste é o número total desses mísseis que foram interceptados pelo catcher naquele teste.

O escritório geral quer ter certeza de que os testes simulados foram suficientes, dadas as restrições do catcher. Você deve escrever um programa que, dados diversos testes com seqüências de mísseis, imprime o número máximo de mísseis que o catcher pode interceptar. Para cada míssil hostil, o catcher pode interceptá-lo se e somente se uma destas condições estiver satisfeita:

• o míssil hostil é o primeiro a ser interceptado neste teste; ou
• o míssil foi disparado depois que o último míssil foi interceptado e ele não está mais alto do que o último míssil que foi interceptado.