ВАС РЕШИТЬ ЗАДАЧУ НА Python, можно и на C++
И СКОРЕЕЕ.
Задача B. Наивысший приоритет
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Программист Кеша начинает свой рабочий день с просмотра почтового ящика. Сегодня утром
в его почтовом ящике обнаружилось n писем.
Кеша читает письма по порядку, начиная с письма #1 и заканчивая письмом #n, и назначает
каждому письму приоритет. Приоритет — это целое положительное число, чем оно меньше, тем более
важным является письмо. Так, самый высокий приоритет имеет значение 1. Когда Кеша назначает
новому письму приоритет, то он изменяет приоритет всех менее важных писем, прочитанных им до
этого.
В частном случае, когда Кеша читает письмо, которое является более важным, чем все прочитанные ранее, он назначает читаемому письму приоритет 1, а приоритет всех ранее прочитанных
писем увеличивается на 1.
Ваша задача — по окончательной расстановке приоритетов pj определить, сколько писем в процессе расстановки получали приоритет 1.
Формальное описание алгоритма, используемого Кешей
Когда Кеша прочитывает письмо #j, он может назначить ему любое значение приоритета из
диапазона от 1 до j. Если он назначил письму #j некоторое значение приоритета k (k < j), это
приводит к увеличению всех назначенных ранее приоритетов, больших или равных k, на 1. Таким образом, в момент после прочтения письма #j приоритеты всех прочитанных писем образуют
перестановку чисел от 1 до j.
Пояснение к используемому Кешей алгоритму
Когда Кеша прочитает первое письмо, он назначит ему приоритет 1.
Когда Кеша прочитает второе письмо, он может назначить ему приоритет 2, если оно менее
важное, чем первое (текущий приоритет писем будет 1, 2), или приоритет 1, если оно более важное
(текущий приоритет писем будет 2, 1).
Когда Кеша прочитает третье письмо, он может назначить ему приоритет 1, 2 или 3 в зависимости от важности этого письма.
Так, Кеша назначит третьему письму приоритет 1, если оно важнее первого и второго писем. В
таком случае текущий приоритет писем будет 2, 3, 1 (если был 1, 2 до этого) или 3, 2, 1 (если был
2, 1).
Если же третье письмо менее важное, чем письмо, имеющее текущий приоритет 1, но более
важное, чем письмо, имеющее текущий приоритет 2, Кеша назначит третьему письму приоритет 2.
В этом случае приоритет писем станет 1, 3, 2 (если был 1, 2) или 3, 1, 2 (если до этого был 2, 1)
Наконец, если третье письмо менее важное, чем первое и второе письма, то его текущим приоритетом станет 3. В таком случае приоритет писем будет 1, 2, 3 (если был 1, 2) или 2, 1, 3 (если был
2, 1).
Формат входных данных
В первой строке содержится целое число n (1 6 n 6 3 · 105
) — количество писем, полученных
Кешей.
Во второй строке содержится n целых чисел p1, p2, . . . , pn, (1 6 pi 6 n, i = 1, 2, . . . , n) — окончательные приоритеты писем в порядке чтения их Кешей.
Гарантируется, что pi 6= pj для i 6= j.
Формат выходных данных
Выведите единственное целое число — количество писем, которые в процессе расстановки приоритетов получали приоритет 1.
Страница 2 из 11
Окружной этап всероссийской олимпиады школьников по информатике, 2020 - 2021 учебный год
Россия, Самара, 21 ноября 2020
Система оценки
В первой подзадаче применяется потестовая система оценки. В графе « » указано количество за тест и в скобках максимальное количество , которое можно набрать за
подзадачу. Участнику сообщаются номера тестов внутри этой подзадачи, которые не были пройдены.
Проверка решений на тестах второй, третьей и четвёртой подзадачах осуществляется только,
если все тесты первой подзадачи были пройдены. В этих подзадачах применяется потестовая система
оценки. Участнику сообщаются номера тестов внутри этой подзадачи, которые не были пройдены.
Проверка решений на тестах пятой подзадачи осуществляется только, если все тесты первых
четырёх подзадач были пройдены. за пятую подзадачу начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного
теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.
Подзадача за тест Ограничения Необходимые Информация
( подзадачи о проверке
за подзадачу)
1 1 (до 9) 1 6 n 6 3 нет полная
2 1 (до 21) 4 6 n 6 10 1 полная
3 1 (до 15) 11 6 n 6 100 1 полная
4 1 (до 15) 101 6 n 6 1000 1 полная
5 0 (40) 1001 6 n 6 3 · 105 1, 2, 3, 4 первая ошибка
ограничения по времени:
1.5 с на тест
Пример
стандартный ввод
7
4 2 6 3 5 1 7
стандартный вывод
3

asem052    1   21.11.2020 10:31    28