Тестирование CATCHER
Военный подрядчик Министерства обороны завершил серию предварительных испытаний новой оборонительной ракеты под названием CATCHER, способной перехватывать несколько наступательных ракет. CATCHER должна стать выдающейся оборонительной системой. Она может двигаться вперед, вбок и вниз с высокой скоростью и перехватывать наступательные ракеты без повреждений. Однако у нее есть один значительный недостаток: она не может подняться выше последней ракеты, которую перехватила, хотя может быть запущена на любую начальную высоту.
Испытания, проведенные подрядчиком, представляли собой компьютерные симуляции боевых условий и вражеской атаки. Поскольку это были предварительные испытания, симуляции проверяли только вертикальную способность движения CATCHER. В каждой симуляции CATCHER сталкивалась с последовательностью наступательных ракет, прибывающих с фиксированными временными интервалами. Единственная информация, доступная для CATCHER о каждой наступательной ракете, — это ее высота в точке возможного перехвата и ее позиция в последовательности. Каждая наступательная ракета в тесте появляется только один раз.
Результаты каждого теста включают последовательность наступательных ракет и общее количество ракет, которые CATCHER смогла перехватить.
Главное бухгалтерское управление хочет удостовериться, что результаты симуляционных тестов, представленные подрядчиком, достижимы с учетом ограничений CATCHER. Вам нужно написать программу, которая принимает входные данные, представляющие последовательность поступающих ракет для нескольких тестов, и выводит максимальное количество ракет, которые CATCHER может перехватить в каждом тесте. Для любой поступающей ракеты в тесте CATCHER может перехватить ее, если выполняется одно из двух условий:
Поступающая ракета является первой, которую нужно перехватить в этом тесте.-или-
Ракета была запущена после последней перехваченной ракеты и не выше ее.
Входные данные
Входные данные для любого теста состоят из последовательности одного или более неотрицательных целых чисел, каждое из которых не превышает 32767, представляющих высоты поступающих ракет (тестовая последовательность). Последнее число в каждой последовательности — это -1, что означает конец данных для данного теста и не считается высотой ракеты. Конец всех данных ввода обозначается числом -1 в качестве первого значения в тесте; оно не считается отдельным тестом.
Выходные данные
Вывод для каждого теста должен содержать номер теста (Тест №1, Тест №2 и т.д.) и максимальное количество поступающих ракет, которые CATCHER могла бы перехватить в этом тесте. Это максимальное число следует после идентифицирующего сообщения. Между выводами для последовательных наборов данных должна быть как минимум одна пустая строка. На обратной стороне этой страницы приведен пример входного файла, состоящего из двух различных сценариев, и соответствующий вывод.
ПРИМЕЧАНИЕ: Количество ракет в любом тесте не ограничено. Если ваше решение основано на неэффективном алгоритме, оно может не уложиться в отведенное время.