Отримання знань
дистанційна підтримка освіти школярів
Задача Military
(запропонована міністерством оборони)
Команда новобранців прибула в частину. Сержант велів їм вишикуватися в колону по одному для руху маршем у лазню. Новобранці, не маючи належних навичок, вишикувалися не по зросту, а як кому до душі припало. Особливо обурило сержанта те, що в колоні проглядалися ділянки, що явно кидали виклик усім статутам стройової служби – новобранці стояли в строю так, що слідом за низеньким знаходився високорослий, за ним – нижчий зростом, а потім знову вище і т.д., або навпаки – слідом за високим – нижчий нього, потім знову вище, потім – нижчий. Обурення сержанта стимулювало концентрацію математичних здібностей, і він одразу велів вийти зі строю тим новобранцям, що утворили найдовший "зубчатий" ланцюжок. Скільки новобранців вийшло зі строю?
Технічні умови: Програма читає з клавіатури в першому рядку кількість новобранців, а в другому – зріст кожного. Числа розділені пропусками. Програма виводить на екран кількість солдатів, що вийшли зі строю. Новобранців не більш 10000, зріст їх вимірюється натуральними числами не більш 255. Якщо декілька ланцюжків мають максимальну довжину, то зі строю виходить тільки один з них.
| Приклад: | Введення | Виведення |
| 20 | 8 | |
| 4 5 2 3 1 6 7 8 3 9 4 6 2 6 7 8 4 8 8 8 |
Розв'язок задачі Military
Позначимо через An зріст n-ого новобранця в строю. Розглянемо різниці A2 - A1, A3 - A2,…,An - An-1. Деяка послідовність новобранців буде зубчастою тоді, і тільки тоді, коли у відповідних різниць знаки чергуються, тобто добуток будь-яких двох сусідніх різниць менше нуля.Будемо проходити колоною зліва направо, на кожному кроці зберігаючи довжину найдовшого ланцюжка, який ми поки що зустріли, довжину ланцюжка, який закінчується поточним новобранцем, та різницю в зрості останнього й передостаннього новобранців. Якщо добуток наступної різниці з поточною невід’ємний, то потрібно починати новий ланцюжок (і порівнювати довжину старого з довжиною найдовшого). Інакше – продовжимо поточний ланцюжок.Часткові випадки: N=1 – відповідь 1; N=2 – якщо A1=A2, то відповідь 1, інакше – відповідь 2.
Перевірити свій розв'язок в режимі on-line
| Попередня | Зміст | Наступна |