Страница: 1 Отображать по:

#1209

Клавиатура

Темы: [Сортировка подсчетом]

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

Для каждой клавиши клавиатуры задано количество выдерживаемых нажатий. Задана последовательность нажатия на клавиши. Требуется определить, какие клавиши выйдут из строя.

Всем известно, что со временем клавиатура изнашивается, и клавиши на ней начинают залипать. Конечно, некоторое время такую клавиатуру еще можно использовать, но для нажатий клавиш приходиться использовать большую силу.

При изготовлении клавиатуры изначально для каждой клавиши задается количество нажатий, которое она должна выдерживать. Если знать эти величины для используемой клавиатуры, то для определенной последовательности нажатых клавиш можно определить, какие клавиши в процессе их использования сломаются, а какие – нет.

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

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100) – количество клавиш на клавиатуре. Вторая строка содержит n целых чисел – с₁, с₂, … , с_n, где с_i (1 ≤ с_i ≤ 100000) – количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1 ≤ k ≤ 100000) – общее количество нажатий клавиш, и последняя строка содержит k целых чисел p_j (1 ≤ p_j ≤ n) – последовательность нажатых клавиш.

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

В выходной файл необходимо вывести n строк, содержащих информацию об исправности клавиш. Если i-ая клавиша сломалась, то i-ая строка должна содержать слово “yes” (без кавычек), если же клавиша работоспособна – слово “no”.

Разбалловка для личной олимпиады

Тест 1 — из условия. Оценивается в 0 баллов.

Тесты 2-21 — дополнительных ограничений нет. Группа тестов оценивается в 100 баллов.

Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп. При выставлении баллов за отдельные тесты каждый тест (кроме тестов из условия) оценивается в 5 баллов.

Примеры

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

5
1 50 3 4 3
16
1 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5

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

yes
no
no
no
yes

#111493

Имена

Темы: [Сортировка подсчетом]

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

На далекой планете Тау Кита есть непонятные нам обычаи. Например, таукитяне очень необычно для землян выбирают имена своим детям. Родители так выбирают имя ребенку, чтобы оно могло быть получено как удалением некоторого набора букв из имени отца, так и удалением некоторого набора букв из имени матери. Например, если отца зовут «abacaba», а мать — «bbccaa», то их ребенок может носить имена «a», «bba», «bcaa», но не может носить имена «aaa», «ab» или «bbc». Возможно, что имя ребенка совпадает с именем отца и/или матери, если оно может быть получено из имени другого родителя удалением нескольких (возможно, ни одной) букв.

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

Формально, строка S лексикографически больше строки T, если выполняется одно из двух условий: строка T получается из S удалением одной или более букв с конца строки S;
первые (i - 1) символов строк T и S не различаются, а буква в i-й позиции строки T следует в алфавите раньше буквы в i-й позиции строки S.

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

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

Первая строка входного файла содержит X — имя отца. Вторая строка входного файла содержит Y — имя матери. Каждое имя состоит из строчных букв латинского алфавита, включает хотя бы одну букву и имеет длину не более \(10^5\) букв.

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

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

Система оценивания

Правильные решения для тестов, в которых имена содержат только буквы «a» и «b» и имеют длину не более 1000, будут оцениваться из 20 баллов.

Правильные решения для тестов, в которых имена содержат только буквы «a» и «b» и имеют длину не более \(10^5\), будут оцениваться из 40 баллов.

Правильные решения для тестов, в которых имена имеют длину не более 1000, будут оцениваться из 40 баллов.

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

Примеры

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

abcabca
abcda

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

ca

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

ccba
accbbaa

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

ccba

#112041

Кондиционеры

Темы: [Сортировка подсчетом]

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

При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.

Все классы школы пронумерованы последовательно от 1 до \(n\). Известно, что для каждого класса с номером \(i\), требуется ровно один кондиционер, мощность которого больше или равна \(a_i\) ватт.

Администрации школы предоставили список из \(m\) различных моделей кондиционеров, которые можно закупить. Для каждой модели кондиционера известна его мощность и стоимость. Требуется написать программу, которая определит, за какую минимальную суммарную стоимость кондиционеров можно оснастить все классы школы.

Формат входного файла

Первая строка входного файла содержит одно целое число n (1 ≤ \(n\) ≤ 50 000) количество классов в школе.

Вторая строка содержит \(n\) целых чисел \(a_i\) (1 ≤ \(a_i\) ≤ 1000)- минимальная мощность кондиционера в ваттах, который можно установить в классе с номером \(i\).

Третья строка содержит одно целое число \(m\) (1 ≤ \(m\) ≤ 50 000) - количество предложенных моделей кондиционеров.

Далее, в каждой из \(m\) строк содержится пара целых чисел \(b_j\) и \(c_j\) (1 ≤ \(b_j\) ≤ 1000, 1 ≤ \(c_j\) ≤ 1000) мощность в ваттах \(j\)-й модели кондиционера и его цена в рублях соответственно.

Формат выходного файла

Выходной файл должен содержать одно число минимальную суммарную стоимость кондиционеров в рублях. Гарантируется, что хотя бы один корректный выбор кондиционеров существует, и во всех классах можно установить подходящий кондиционер.

Пояснения к примерам

В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.

Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе – кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).

Система оценивания

Частичные решения для \(n\), \(m\) ≤ 1000 будут оцениваться из 50 баллов.

Примеры

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

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

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

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

#113101

Счет в гипершашках

Темы: [Сортировка подсчетом] [Перестановки]

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

Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал \(a\) баллов, второй — \(b\), а третий \(c\), то говорят, что игра закончилась со счетом \(a:b:c\).

Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в \(k\) раз.

После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа \(x_1, x_2, …, x_n\). Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.

Требуется написать программу, которая по числу \(k\) и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.

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

Первая строка входного файла содержит два целых числа: \(n\) и \(k (3 \le n \le 100 000, 1 \le k \le 10^9\) ).

Вторая строка входного файла содержит \(n\) целых чисел \(x_1, x_2, …, x_n (1 \le x_i \le 10^9 )\).

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

Выходной файл должен содержать одно целое число — искомое количество различных вариантов счета.

Пояснение к примеру

В приведенном примере Андрей сможет показать следующие варианты счета: 1:1:2, 1:2:1, 2:1:1, 1:2:2, 2:1:2, 2:2:1, 2:2:3, 2:3:2, 3:2:2. Другие тройки чисел, которые можно составить с использованием имеющихся карточек, не удовлетворяют заданному условию, что баллы любых двух игроков различаются не более чем в \(k\) = 2 раза.

Описание подзадач и системы оценивания

В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Подзадача 1 (15 баллов)

\(3 \le n \le 100 000, k = 1, 1 \le x_i \le 100 000\)

Подзадача 2 (23 балла)

\(3 \le n \le 100, k \le 100, 1 \le x_i \le 100\)

Подзадача 3 (30 баллов)

\(3 \le n \le 100 000, k \le 10^9 \le x_i \le 10^9\), все \(x_i\) различны

Подзадача 4 (32 балла)

\(3 \le n \le 100 000, k \le 10^9 \le x_i \le 10^9\)

Примеры

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

5 2
1 1 2 2 3

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

Страница: 1 Отображать по:

Выбрано

Отменить

Добавить в контест