Тестування CATCHER
Військовий підрядник Міністерства оборони завершив серію попередніх тестів для нової оборонної ракети під назвою CATCHER, яка здатна перехоплювати кілька наступальних ракет. CATCHER має бути видатною оборонною ракетою, здатною рухатися вперед, вбік і вниз на дуже високих швидкостях, перехоплюючи наступальні ракети без пошкоджень. Проте, у неї є один суттєвий недолік: хоча її можна запустити на будь-яку початкову висоту, вона не може піднятися вище останньої ракети, яку перехопила.
Тести, які провів підрядник, були комп'ютерними симуляціями бойових умов та ворожих атак. Оскільки це були лише попередні тести, симуляції перевіряли лише здатність CATCHER рухатися вертикально. У кожній симуляції CATCHER запускався на послідовність наступальних ракет, які надходили з фіксованими інтервалами часу. Єдина інформація, доступна для CATCHER для кожної наступальної ракети, була її висота в точці, де її можна було перехопити, і її позиція в послідовності. Кожна наступальна ракета в тестовій послідовності з'являється лише один раз.
Результат кожного тесту подається як послідовність наступальних ракет і загальна кількість ракет, які CATCHER перехоплює в цьому тесті.
Головне бухгалтерське управління хоче переконатися, що результати симуляційних тестів, подані військовим підрядником, є досяжними з урахуванням обмежень CATCHER. Ви повинні написати програму, яка приймає вхідні дані, що представляють шаблон наступальних ракет для кількох різних тестів, і виводить максимальну кількість ракет, які CATCHER може перехопити в цих тестах. Для будь-якої наступальної ракети в тесті CATCHER може її перехопити, якщо і тільки якщо вона задовольняє одну з цих двох умов:
Наступальна ракета є першою ракетою, яку перехоплюють у цьому тесті.-або-
Ракета була запущена після останньої ракети, яку перехопили, і вона не вища за останню ракету, яку перехопили.
Вхідні дані
Вхідні дані для будь-якого тесту складаються з послідовності одного або більше невід'ємних цілих чисел, всі з яких менші або дорівнюють 32767, що представляють висоти наступальних ракет (шаблон тесту). Останнє число в кожній послідовності - це -1, що означає кінець даних для цього конкретного тесту і не вважається висотою ракети. Кінець даних для всього вводу - це число -1 як перше значення в тесті; воно не вважається окремим тестом.
Вихідні дані
Вихід для кожного тесту складається з номера тесту (Тест №1, Тест №2 тощо) і максимальної кількості наступальних ракет, які CATCHER міг би перехопити для тесту. Ця максимальна кількість з'являється після ідентифікаційного повідомлення. Між виходами для наступних наборів даних має бути принаймні один порожній рядок. На звороті цієї сторінки наведено приклад вхідного файлу, який складається з двох різних сценаріїв і відповідного виходу.
ПРИМІТКА: Кількість ракет для будь-якого даного тесту не обмежена. Якщо ваше рішення базується на неефективному алгоритмі, воно може не виконатися в відведений час.