---> 27 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 >> Отображать по:
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes
Для каждой клавиши клавиатуры задано количество выдерживаемых нажатий. Задана последовательность нажатия на клавиши. Требуется определить, какие клавиши выйдут из строя.

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

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

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

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100) – количество клавиш на клавиатуре. Вторая строка содержит n целых чисел – с1, с2, … , сn, где сi (1 ≤ сi ≤ 100000) – количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1  k  100000) – общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj (1  pj  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
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке задано число n (1 ≤ n ≤ 106). Во второй строке задается описание построенного ряда из мальчиков и девочек — строка из n символов a и b (символ a соответствует девочке, а символ b — мальчику).

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

В единственной строке должно содержаться единственное число — количество вариантов выбора требуемой группы.

Система оценки

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

  1. Тест 1. Тест из условия, оценивается в 0 баллов.
  2. Тесты 2–8. $N \le 101$, оцениваются в 30 баллов.
  3. Тесты 9–14. $N \le 6\,000$, оцениваются в 30 баллов.
  4. Тесты 15–20. Дополнительных ограничений нет, оцениваются в 40 баллов.

Примеры
Входные данные
8
aabbaabb
Выходные данные
10
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Помимо открыток Петя и Вася решили устроить одноклассницам чаепитие и заразили своей идеей еще K–2 своих друзей. Они собрались вместе и выбрали в одном довольно известном супермаркете P тортиков. Настал черед рассчитываться за них.

В магазине есть N работающих касс, занумерованных числами от 1 до N. Про i-ю кассу известно, что кассиру требуется Ai единиц времени на обработку одного товара и Bi единиц времени для того, чтобы рассчитаться с покупателем. Обойдя все кассы, школьники посчитали, что на обслуживание покупателей, уже стоящих в i-ю кассу, уйдет Ti единиц времени.

Теперь Петя и Вася задались вопросом, в какие кассы надо встать им и их друзьям (в каждую из выбранных касс должен стоять хотя бы один из них, и каждый из них может стоять не более, чем в одну кассу, поэтому суммарно они могут стоять не более чем в K касс) и сколько тортиков каждый должен взять, чтобы последний из них вышел из магазина как можно раньше. Некоторые из ребят могут в кассу не стоять, а, отдав все тортики другим, выйти через специальный выход для тех, кто ничего не купил.

Напишите программу, которая определит это минимальное время.

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

В первой строке записано одно число N — количество касс в супермаркете (1 ≤ N ≤ 100000). В следующих N строках записано по три числа Ai, Bi, Ti (0 ≤ Ai, Bi, Ti ≤ 100000). В последней строке записаны два числа — K и P — число школьников и покупок у них соответственно (0 ≤ P ≤ 100000, 2 ≤ K ≤ 100000).

Все числа во входном файле целые.

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

Выведите минимальное время выхода последнего школьника из магазина.

Комментарии к примерам тестов

Здесь лучше всего встать в обе кассы и купить там по одному тортику.

Выгоднее всего одному из школьников встать со всеми тортиками в первую кассу, а остальным выйти без покупок.

Частичные ограничения

Первая группа состоит из тестов, в которых N ≤ 10.

Вторая группа состоит из тестов, в которых N K ≤ 100000.

Примеры
Входные данные
2
100 10 40
10 100 50
2 2
Выходные данные
160
Входные данные
3 
1 2 0
5 2 1
2 10 1
3 5
Выходные данные
7
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Даны два слова на отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают 255.

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

Требуется вывести "YES"  – если введенные слова являются анаграммами друг друга, "NO"  – если нет.

Примеры
Входные данные
sharm
marsh
Выходные данные
YES
Входные данные
ananas
nnaass
Выходные данные
NO
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дано N целых чисел, которые требуется отсортировать в порядке неубывания. В связи с нормами СЭС среди чисел не будет двух, разница между которыми превышает $10^7$.

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

Первая строка входного файла содержит целое число N. (1 <= N <= 100000), вторая строка – N целых чисел, не превышающих по модулю 2*109. Никакие два не различаются более, чем на $10^7$.

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

Выведите данные числа в порядке неубывания.

Примеры
Входные данные
1
863961129 
Выходные данные
863961129 
Входные данные
5
1866455200 1866455199 1866455198 1866455197 1866455196 
Выходные данные
1866455196 1866455197 1866455198 1866455199 1866455200 

Страница: << 1 2 3 4 5 6 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест