#3207

Чемпионат по стрельбе

Темы: [Одномерные массивы] [Линейный поиск]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 2 день, Задача B ]

Победитель школьного этапа олимпиады по информатике нашел дома в старых бумагах результаты чемпионата страны по стрельбе из лука, в котором участвовал его папа. К сожалению, листок с результатами сильно пострадал от времени, и разобрать фамилии участников было невозможно. Остались только набранные каждым участником очки, причем расположились они в том порядке, в котором участники чемпионата выполняли стрельбу.

Расспросив папу, школьник выяснил, что количество очков, которое набрал папа, заканчивается на 5, один из победителей чемпионата стрелял раньше, а папин друг, который стрелял сразу после папы, набрал меньше очков. Теперь он заинтересовался, какое самое высокое место мог занять его папа на том чемпионате.

Будем считать, что участник соревнования занял $k$-е место, если ровно $(k - 1)$ участников чемпионата набрали строго больше очков, чем он. При этом победителями считались все участники чемпионата, занявшие первое место.

Требуется написать программу, которая по заданным результатам чемпионата определяет, какое самое высокое место на чемпионате мог занять папа победителя школьного этапа олимпиады по информатике.

Входные данные

Первая строка входного файла содержит целое число $n$ — количество участников чемпионата страны по стрельбе ($3 \le n \le 10^5$).

Вторая строка входного файла содержит $n$ положительных целых чисел, каждое из которых не превышает 1000, — очки участников чемпионата, приведенные в том порядке, в котором они выполняли стрельбу.

Выходные данные

В выходном файле должно содержаться одно целое число — самое высокое место, которое мог занять папа школьника. Если не существует ни одного участника чемпионата, который удовлетворяет, описанным выше условиям, выведите в выходной файл число 0.

Примечание

Правильные решения для тестов, в которых $1 \le n \le 1000$, оцениваются из 50 баллов.

Примеры

Входные данные

7
10 20 15 10 30 5 1

Выходные данные

Входные данные

3
15 15 10

Выходные данные

#3788

Кубики

Темы: [Одномерные массивы]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2011, Задача C ]

ООО «Симптотика» собирается наладить выпуск обучающих игр для детей младшего дошкольного возраста. Одной из придуманных игр был набор кубиков, из которых можно было собирать различные фигуры. Кубики упаковывались в коробку размером N × N × 1 кубиков.

Однако, многочисленные маркетинговые исследования показали, что детям неинтересно просто собирать различные фигурки. Гораздо интереснее складывать некоторый набор кубиков на дно коробки в столбики, а после этого переворачивать коробку на 90 градусов по часовой стрелке и смотреть, как именно меняется их расположение. Будем для простоты считать, что коробка поворачивается мгновенно, после чего все кубики падают на дно. На следующем рисунке продемонстрировано, как выглядит расположение кубиков в коробке до и после поворота на 90 градусов.

$\text{[math]}$

Разумеется, многим детям становится интересно, как будет выглядеть расположение кубиков после K поворотов в том же направлении. Требуется написать программу, которая вычисляет итоговое положение кубиков в коробке после K поворотов.

Входные данные

Сначала вводятся целые числа N и K (1 ≤ N ≤ 10, 0 ≤ K ≤ 10⁹). После этого, во второй строке вводятся N неотрицательных чисел, не превышающих N. i-ое число обозначает количество кубиков в столбце под номером i.

Выходные данные

Необходимо вывести N чисел через пробел, i-ое из которых обозначает количество чисел в i-ом столбце в полученном после K поворотов расположении кубиков.

Примечание

Пример соответствует иллюстрации из условия.

Примеры

Входные данные

5 1
1 3 4 0 1

Выходные данные

4 2 2 1 0

#111855

Переливания

Темы: [Одномерные массивы] [Жадный алгоритм]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Москва, 2012, Задача B ]

Имеется 10 колб с водой и известен объем воды в каждой из них. За одно “касание” можно взять одну колбу и часть воды (или всю воду) из этой колбы разлить по одной или нескольким другим колбам в любом количестве. За какое наименьшее количество “касаний” можно уравнять объемы воды во всех колбах? Каждая колба может вместить любой объем воды.

Входные данные

Программа получает на вход 10 целых чисел $a_i$, каждое записанное в отдельной строке $--$ объем воды в каждой из колб. Все числа — целые, от 0 до 100.

Выходные данные

Выведите одно целое число — минимальное количество “касаний”, за которое можно уравнять объемы воды во всех колбах.

Примечание к примеру

В примере можно из первой колбы перелить 20 во вторую, оставляя в первой колбе 10. Затем из второй колбы разлить воду по всем остальным колбам так, чтобы в каждой из колб оказалось по 10.

Примеры

Входные данные

Выходные данные

#111989

Телефон

Темы: [Одномерные массивы]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2013, 10-11 классы, Телефон ]

У бизнесмена есть телефон, который он использует для связи с партнерами по бизнесу. Сегодня у предпринимателя запланировано n разговоров, про каждый из которых известно число P_i — сколько рублей прибыли получит бизнесмен, если i-й разговор состоится (P_i может быть равно 0 — в этом случае никакой выгоды от i-го разговора нет).

Телефон у бизнесмена сделан по новейшим технологиям, но иногда барахлит. Сегодня, например, телефон внезапно разрядился, поэтому он позволит бизнесмену провести только первые A₀ разговоров, а затем выключится до конца дня. Однако телефон можно зарядить, пропустив несколько первых запланированных разговоров. Более формально, если предприниматель будет заряжать телефон вместо первых j разговоров (то есть разговоров с номерами от 1 до j), то он потом сможет провести ровно A_j разговоров (с номерами от j + 1 до min(n, j + A_j)), после чего телефон опять же перестанет работать до конца дня.

Напишите программу, которая вычислит, сколько разговоров надо пропустить бизнесмену, чтобы заработать как можно больше. Если существует несколько ответов, то выведите тот, который требует большего времени зарядки, так как бизнесмену хочется отдохнуть подольше перед звонками.

Входные данные

На вход программе дается целое число n — количество запланированных звонков (1 ≤ n ≤ 2·10⁵). На следующей строке вводятся через пробел $n$ целых чисел P_i, обозначающие прибыли от звонков (0 ≤ P_i ≤ 1 000). Затем вводятся $n+1$ целых чисел A_j, обозначающие, сколько звонков можно будет провести после подзарядки (0 ≤ A_j ≤ 10⁶).

Выходные данные

Выведите два числа, первое — это максимальная выгода, которую может получить бизнесмен, второе — количество пропущенных первых звонков, при котором она получается (0, если выгоднее всего не заряжать телефон вовсе).

Примеры тестов

Входные данные

5
1 2 0 4 1
2 0 8 3 5 6

Выходные данные

5 3

Примечание

Рассмотрим пример из условия: n = 5, P₁ = 1, P₂ = 2, P₃ = 0, P₄ = 4, P₅ = 1, A₀ = 2, A₁ = 0, A₂ = 8, A₃ = 3, A₄ = 5, A₅ = 6.

Если бизнесмен не будет заряжать телефон, то результат будет равен P₁ + P₂ = 1 + 2 = 3 рубля. Если предприниматель будет заряжать телефон вместо первого звонка, то он не сможет позвонить ни разу, так как A₁ = 0. Если вместо первых двух звонков, то результат составит P₃ + P₄ + P₅ = 0 + 4 + 1 = 5 рублей. Если вместо первых трех, то P₄ + P₅ = 4 + 1 = 5. Если вместо четырёх звонков, то P₅ = 1 рубль. Наконец, если бизнесмен будет заряжать телефон вместо всех n = 5 звонков, то он заведомо ничего не получит. Таким образом, два лучших варианта — это заряжать либо вместо 2 первых звонков, либо вместо 3, в обоих случаях получаем 5 рублей прибыли. По условию, из них мы выбираем выбираем вариант с 3 пропущенными звонками.

Тесты к этой задаче состоят из трех групп.

Тест 1 — тест из условия, оценивается в ноль баллов.
Тесты 2 – 19. В тестах этой группы 1 ≤ n ≤ 10⁴. Эта группа оценивается в 50 баллов, баллы ставятся только при прохождении всех тестов группы.
Тесты 20 – 36. В тестах этой группы дополнительные ограничения отсутствуют. Группа оценивается в 50 баллов, баллы ставятся только при прохождении всех тестов этой и предыдущих групп.