Информатика

Буква A по краям

Дана строка s. Рассматриваются все подряд идущие фрагменты длины 3 (в том числе пересекающиеся). Найдите количество фрагментов, для которых выполнено условие: первый и третий символы равны A, а средний отличается от A.

Ввод: одна строка без пробелов. Длина строки от 1 до 2500 символов. Строка содержит только символы A, B, C.

Вывод: одно целое число.

Пересекающиеся фрагменты учитываются отдельно.

Буква A только справа

Дана строка s. Рассматриваются все подряд идущие фрагменты длины 2 (в том числе пересекающиеся). Найдите количество фрагментов, для которых выполнено условие: второй символ равен A, а первый не равен A.

Ввод: одна строка без пробелов. Длина строки от 1 до 2500 символов. Строка содержит только символы A, B, C, D.

Вывод: одно целое число.

Пересекающиеся фрагменты учитываются отдельно.

Ни одной B

Дана строка s. Рассматриваются все подряд идущие фрагменты длины 2 (в том числе пересекающиеся). Найдите количество фрагментов, для которых выполнено условие: оба символа отличаются от B.

Ввод: одна строка без пробелов. Длина строки от 1 до 2500 символов. Строка содержит только символы A, B, C, D.

Вывод: одно целое число.

Пересекающиеся фрагменты учитываются отдельно.

Ровно одна цифра 7

Дана строка s. Рассматриваются все подряд идущие фрагменты длины 2 (в том числе пересекающиеся). Найдите количество фрагментов, для которых выполнено условие: ровно один символ равен 7.

Ввод: одна строка без пробелов. Длина строки от 1 до 2500 символов. Строка содержит только символы 1, 2, 3, 7, 8, 9.

Вывод: одно целое число.

Пересекающиеся фрагменты учитываются отдельно.

Хотя бы одна A

Дана строка s. Рассматриваются все подряд идущие фрагменты длины 2 (в том числе пересекающиеся). Найдите количество фрагментов, для которых выполнено условие: хотя бы один символ равен A.

Ввод: одна строка без пробелов. Длина строки от 1 до 2500 символов. Строка содержит только символы A, B, C, D.

Вывод: одно целое число.

Пересекающиеся фрагменты учитываются отдельно.

Обе буквы гласные

Дана строка s. Рассматриваются все подряд идущие фрагменты длины 2 (в том числе пересекающиеся). Найдите количество фрагментов, для которых выполнено условие: оба символа входят в набор AEIOU.

Ввод: одна строка без пробелов. Длина строки от 1 до 2500 символов. Строка содержит только символы A, B, C, D, E, I, O, U.

Вывод: одно целое число.

Пересекающиеся фрагменты учитываются отдельно.

Ровно одна гласная

Дана строка s. Рассматриваются все подряд идущие фрагменты длины 2 (в том числе пересекающиеся). Найдите количество фрагментов, для которых выполнено условие: ровно один символ входит в набор AEIOU.

Ввод: одна строка без пробелов. Длина строки от 1 до 2500 символов. Строка содержит только символы A, B, C, D, E, I, O, U.

Вывод: одно целое число.

Пересекающиеся фрагменты учитываются отдельно.

Соседи разных типов

Дана строка s. Рассматриваются все подряд идущие фрагменты длины 2 (в том числе пересекающиеся). Найдите количество фрагментов, для которых выполнено условие: один символ — цифра, второй — буква.

Ввод: одна строка без пробелов. Длина строки от 1 до 2500 символов. Строка содержит только символы X, Y, Z, 1, 2, 3.

Вывод: одно целое число.

Пересекающиеся фрагменты учитываются отдельно.

Пара по убыванию

Дана строка s. Рассматриваются все подряд идущие фрагменты длины 2 (в том числе пересекающиеся). Найдите количество фрагментов, для которых выполнено условие: первый символ больше второго по алфавиту.

Ввод: одна строка без пробелов. Длина строки от 1 до 2500 символов. Строка содержит только символы A, B, C, D, E.

Вывод: одно целое число.

Пересекающиеся фрагменты учитываются отдельно.

Пара по возрастанию

Дана строка s. Рассматриваются все подряд идущие фрагменты длины 2 (в том числе пересекающиеся). Найдите количество фрагментов, для которых выполнено условие: первый символ меньше второго по алфавиту.

Ввод: одна строка без пробелов. Длина строки от 1 до 2500 символов. Строка содержит только символы A, B, C, D, E.

Вывод: одно целое число.

Пересекающиеся фрагменты учитываются отдельно.

Смена цифры на букву

Дана строка s. Рассматриваются все подряд идущие фрагменты длины 2 (в том числе пересекающиеся). Найдите количество фрагментов, для которых выполнено условие: первый символ — цифра, а второй — буква.

Ввод: одна строка без пробелов. Длина строки от 1 до 2500 символов. Строка содержит только символы A, B, C, D, 0, 1, 2, 3.

Вывод: одно целое число.

Пересекающиеся фрагменты учитываются отдельно.

Одинаковые соседи

Дана строка s. Рассматриваются все подряд идущие фрагменты длины 2 (в том числе пересекающиеся). Найдите количество фрагментов, для которых выполнено условие: два символа одинаковы.

Ввод: одна строка без пробелов. Длина строки от 1 до 2500 символов. Строка содержит только символы A, B, C, D.

Вывод: одно целое число.

Пересекающиеся фрагменты учитываются отдельно.

Разные соседние символы

Дана строка s. Рассматриваются все подряд идущие фрагменты длины 2 (в том числе пересекающиеся). Найдите количество фрагментов, для которых выполнено условие: два символа различны.

Ввод: одна строка без пробелов. Длина строки от 1 до 2500 символов. Строка содержит только символы A, B, C.

Вывод: одно целое число.

Пересекающиеся фрагменты учитываются отдельно.

Алекс выбирает приборы для экспедиции. У него есть n разных приборов. Каждый существует в единственном экземпляре и имеет массу wᵢ и научную ценность vᵢ. Массы и ценности выбранных приборов складываются.

В рюкзак помещается груз общей массой не более W. Алекс хочет получить максимальную суммарную ценность. Среди всех наборов с такой ценностью он выбирает набор наименьшей общей массы. Можно не брать ни одного прибора.

Найдите максимальную ценность и соответствующую минимальную массу.

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

Первая строка содержит целые числа n и W (1 ≤ n ≤ 200, 1 ≤ W ≤ 10 000). Следующие n строк содержат wᵢ и vᵢ (1 ≤ wᵢ ≤ 20 000, 1 ≤ vᵢ ≤ 10⁹).

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

Выведите два целых числа: максимальную ценность и минимальную массу набора с этой ценностью.

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

Пример 1. Нужно взять третий и четвёртый приборы: ценность 6 + 12 = 18, масса 2 + 5 = 7.

Пример 2. Ценность обоих одиночных наборов равна 5, поэтому выбираем более лёгкий.

Алекс записал результаты n последовательных измерений. Результат каждого — целое неотрицательное число. Для отчёта он может выбрать любой непустой непрерывный фрагмент журнала.

Фрагмент считается согласованным, если сумма его чисел делится на K без остатка. Посчитайте количество согласованных фрагментов. Фрагменты с разными границами считаются различными, даже если числа в них совпадают. Нулевая сумма делится на K.

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

Первая строка содержит целые числа n и K (1 ≤ n ≤ 200 000, 1 ≤ K ≤ 10⁹). Вторая строка содержит n чисел aᵢ (0 ≤ aᵢ ≤ 10⁹).

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

Выведите количество согласованных непустых фрагментов.

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

Пример 1. Подходят фрагменты [1,2], [1,3], [1,5], [3,3], [3,5], [4,5], [2,4]; в скобках указаны номера границ.

Пример 2. Подходят все шесть непустых фрагментов.

К фестивалю Алекс готовит k значков. В мастерской работают n независимых станков. В момент 0 Алекс включает их все.

Станок i сначала прогревается sᵢ секунд, затем изготавливает один значок за pᵢ секунд. Его первый значок готов в момент sᵢ + pᵢ, второй — в момент sᵢ + 2pᵢ и так далее. Между значками станок не останавливается. Материалов достаточно.

Найдите самый ранний целый момент времени, когда суммарно будет готово не менее k значков. Значок, завершённый ровно в этот момент, уже считается готовым.

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

Первая строка содержит целые числа n и k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 10⁹).

Следующие n строк содержат по два целых числа sᵢ и pᵢ (0 ≤ sᵢ ≤ 10⁹, 1 ≤ pᵢ ≤ 10⁹).

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

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

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

Пример 1. К моменту 8 готовы 2 + 2 = 4 значка, а к моменту 9 — 3 + 2 = 5.

Пример 2. Значки единственного станка готовы в моменты 9, 13 и 17.

Алекс должен пройти из зала s в зал t научного центра. Есть n залов и m двусторонних переходов. Каждый переход занимает одну минуту.

Часть переходов открыта, а часть закрыта. У Алекса есть одноразовый электронный пропуск: он позволяет один раз пройти по одному закрытому переходу. После использования пропуск исчезает, а сам переход остаётся закрытым. По открытым переходам можно ходить без пропуска.

Найдите минимальное время пути. Использовать пропуск необязательно. Если добраться до цели невозможно, выведите −1.

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

Первая строка содержит целые числа n, m, s, t (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000, 1 ≤ s, t ≤ n). Старт и финиш могут совпадать.

Следующие m строк содержат u, v, c (1 ≤ u, v ≤ n, u ≠ v). При c = 0 переход открыт, при c = 1 — закрыт. Между парой залов не более одного перехода.

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

Выведите минимальное время в минутах либо −1, если допустимого маршрута нет.

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

Пример 1. Нужно идти 1 → 2 → 3 → 4 → 5 и использовать пропуск в конце. Быстрый переход 1 → 3 потратил бы пропуск слишком рано.

Пример 2. Чтобы пройти этот маршрут, понадобились бы два пропуска.

Алекс готовит оборудование экспедиции к испытаниям, которые продлятся n часов. В каждый час всё оборудование нужно обеспечить электричеством. В час i питание от основной сети стоит aᵢ монет, а питание от резервного генератора — bᵢ монет.

Генератор можно запустить не более одного раза. Сам запуск стоит C монет. После запуска генератор должен работать несколько последовательных полных часов, хотя бы один. Затем его можно выключить, но повторно включить уже нельзя. Пока генератор работает, всё оборудование питается от него, и плата за основную сеть не взимается.

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

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

Первая строка содержит целые числа n и C (1 ≤ n ≤ 200 000, 0 ≤ C ≤ 10¹⁴).

Вторая строка содержит n целых чисел a₁, …, aₙ — стоимость основной сети по часам. Третья строка содержит n целых чисел b₁, …, bₙ — стоимость работы генератора по часам. Для всех i: 0 ≤ aᵢ, bᵢ ≤ 10⁹.

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

Выведите одно целое число — минимальную общую стоимость.

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

Пример 1. Выгодно включить генератор на часы со 2-го по 6-й. Эти часы стоят 2 + 7 + 2 + 7 + 2 = 20 монет. Ещё 5 монет стоит запуск, а в 1-й и 7-й часы сеть стоит по 2 монеты. Всего 29. В 3-й и 5-й часы генератор дороже сети, но включить его несколькими отдельными периодами нельзя.

Пример 2. Генератор дешевле в каждом часу, но за все три часа экономит только 3 монеты. Запуск за 10 монет не окупается; лучше пользоваться сетью.

Задание выполняется с использованием прилагаемых файлов.

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты, проекции вектора скорости, масса и признак внутреннего строения, обозначенный римской цифрой от I до VII.

Входные данные представлены в файле {1}. В каждой строке записаны шесть значений: x y Vx Vy m признак. Числовые значения разделены пробелами. Количество строк не превышает 10 000, модуль каждого числового значения не превышает 100.

Типовой пример организации данных:

12.109529 9.296790 4.191372 -1.404421 2.018885 II
2.978594 6.367063 2.761727 -0.380255 2.029252 II
18.651563 12.977132 5.884316 0.963875 1.975106 II
19.776880 13.695828 5.885796 -0.025341 2.046900 II
6.388189 4.952984 2.708223 1.181748 2.045710 II
20.151611 14.120760 5.847102 -0.570668 1.974583 III
20.503637 13.166587 5.474787 2.254411 1.963220 III
9.750723 7.833330 4.235968 1.314596 1.969003 II
19.743683 15.963785 5.156460 2.746525 2.037685 IV
10.424793 9.702717 4.251482 1.405363 2.002848 III
6.707575 6.418853 2.549310 -1.066458 1.973822 III
12.562317 8.099051 4.556720 0.384677 1.954612 III
3.842300 2.503859 2.639580 -1.154394 1.986924 III
6.636489 6.467062 2.844667 -0.816615 1.965780 IV
12.273069 10.541207 4.043127 2.050429 2.021882 IV

Задание выполняется с использованием прилагаемых файлов.

Рассматриваются частицы на плоскости. Для каждой частицы известны декартовы координаты, проекции вектора скорости, масса и признак внутреннего строения, обозначенный римской цифрой от I до VII.

Входные данные представлены в файле {1}. В каждой строке записаны шесть значений: x y Vx Vy m признак. Числовые значения разделены пробелами. Количество строк не превышает 10 000, модуль каждого числового значения не превышает 100.

Типовой пример организации данных:

3.043538 1.841211 -2.702636 0.439243 1.826657 II
19.756379 14.735503 4.079223 -2.787031 2.789380 II
11.285660 11.218020 -4.904728 2.151100 1.393593 II
14.348475 8.125936 -3.111643 -4.977388 1.180346 II
10.433958 6.501781 1.730554 -4.530042 1.669777 III
5.433649 5.661029 -1.876422 -1.900184 2.316750 II
19.842436 15.760256 4.711530 4.446957 1.605937 II
20.408568 12.245833 6.755048 2.548903 1.265911 III
6.623439 5.021078 0.431111 -3.501112 1.156754 III
4.277080 5.252907 0.396524 2.236119 2.925267 III
7.499155 4.490922 0.980423 2.967586 1.618680 IV
11.569454 10.839799 3.202465 -1.864505 3.060974 III
17.141691 15.078520 -1.858515 -6.333222 1.498603 III
11.184124 7.289443 3.841075 -4.470683 1.190047 IV
19.973547 11.512409 -4.818342 4.852559 1.425560 IV