ВАС РЕШИТЬ ЗАДАЧУ НА 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
234
449
Ответы на вопрос:
• при Word открыть файл, на который нужно установить пароль; • в левом верхнем углу окна Word щелкнуть мышкой по пункту "Файл"; • в левой части открывшегося меню щелкнуть по пункту "Сведения". Затем в его правой части нажать на "Защитить документ", после чего в появившемся списке выбрать "Зашифровать паролем" (см. изображение).
Объяснение:
Реши свою проблему, спроси otvet5GPT
-
Быстро
Мгновенный ответ на твой вопрос -
Точно
Бот обладает знаниями во всех сферах -
Бесплатно
Задай вопрос и получи ответ бесплатно
Популярно: Информатика
-
valerunik160val06.05.2020 03:25
-
13kristinka0128.02.2023 20:21
-
skyyymbria15.04.2023 12:41
-
Howcould15.02.2020 03:27
-
evakazakova2015.08.2022 04:22
-
toyzsr29.03.2023 16:22
-
hippol13.03.2020 20:48
-
arseniy011422.10.2022 17:15
-
katarakta13.12.2021 02:40
-
Supermatematik124503.06.2020 03:12
Есть вопросы?
-
Как otvet5GPT работает?
otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса. -
Сколько это стоит?
Проект находиться на стадии тестирования и все услуги бесплатны. -
Могу ли я использовать otvet5GPT в школе?
Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое! -
В чем отличия от ChatGPT?
otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.