Тексты задач для тренировочных интернет-туров по информатике для размещения на сайте school-collection. edu. ru (стр. 2 )

В нескольких следующих строках даны пары п and т (1 ≤ n, m ≤ 100).

Последняя строка содержит два нуля, этот тест обрабатывать не надо.

Формат выходных данных

Для каждого теста выведите его номер и значение А(п, т) mod t. Смотрите пример, для уточнения формата.

Пример

Задача B. Как разрушить свой мозг

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

Пока Скив, Гвидо и Нунцио регистрировались в качестве участников, к Аазу подошёл представитель организаторов и спросил:

— Вы приехали как тренер?

— Да, а разве Вам не пришла заявка? Команда Possiltum U M. Y.T. H. ...

— Конечно, пришла. Просто у нас тут возникла идея. Раз Вы, во-первых, тренер, а во-вторых, как я знаю, давно им работаете, то мы приглашаем Вас принять участие в работе жюри.

— Значит так. Во-первых, это действительно так, а во-вторых, я очень суров... — уточнил Ааз.

— Тем более, у нас в жюри как раз не хватает сторонников строгого подхода. Так что давайте, жюри Вас ждёт.

Ааз решил, что лишняя информация о ходе соревнований ему не повредит, и принял приглашение, предварительно осведомившись о вознаграждении, положенном членам жюри за работу.

Вчитываясь в условие очередной задачи, как раз и посвящённой вычитыванию условий задач, Ааз почувствовал, что этот текст начинает разрушать его мозг. Он вспомнил, что можно разрушить свой мозг чтением строки S, если хотя бы половина из всех её k-буквенных подпоследовательностей совпадает.

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

Формат входных данных

В первой строке дана непустая строка S, длиной до 1 000 прописных букв латинского алфавита. Во второй – натуральное число к (1 ≤ к ≤ |S|).

Формат выходных данных

Выведите «YES», если строка может разрушить мозг Ааза, и «NO» – иначе.

Примеры

Задача C. Снег

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 0.3 секунды

Ограничение по памяти: 256 Мебибайт

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

Для простоты представим, что действия происходит в двумерном пространстве. Путь от центральной площади до места перемещения снега за городом представляет собой отрезок прямой [0, EndX], а снежный ком — строго выпуклый многоугольник. Одно усилие дворника позволяет перекатить ком на следующую грань (если пронумеровать грани последовательно с 1 до N, то если текущая грань i = N, то следующая будет с номером 1, а иначе — с номером
(i + 1)).

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

Формат входных данных

В первой строке входного файла записаны два целых числа. Первое из них — N (3 ≤ N ≤ 80 000) — количество вершин снежного кома. Второе — координата конца города EndX (0 ≤ EndX ≤ 109)

Далее следует N описаний вершин снежного кома в начальном положении, каждое из которых представляет собой две целочисленные координаты Xi и Yi. Гарантируется, что X1 = 0, Y1 = 0, Y2 = 0, Х2 > 0, все Yi неотрицательны и не превышают 109, все Xi по модулю не превышают 109, а порядок вершин во входном файле совпадает с обходом против часовой стрелки вершин снежного кома.

Гарантируется, что в предпоследний и последний моменты времени расстояния между концами грани, на которой лежит снежный ком, и точкой EndX будут ³ 0.1 (то есть, проблем с точностью не должно возникнуть).

Формат выходных данных

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

Пример

Задача D. Сумма не без разнообразия

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мебибайт

Задана последовательность целых чисел А1 А2,..., AN.

Необходимо выбрать из нее подпоследовательность из подряд стоящих чисел Ai, Ai+1,..., Aj так, чтобы она содержала не менее К различных чисел и сумма S = Ai + Ai+1+ ... + Aj была максимальной.

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

Формат входных данных

Первая строка ввода содержит целые числа NиK(1≤K≤N≤ 200 000). Вторая строка содержит N целых чисел А1 А2,..., AN (| Ai | ≤ 1 000 000 000).

Формат выходных данных

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

Если не существует подпоследовательностей, удовлетворяющих решению задачи, требуется вывести одну строку со словом «IMPOSSIBLE» (без кавычек).

Подзадача 1

Дополнительные упрощения: 1 ≤ N ≤ 100.

Решение оценивается в 25 баллов.

Подзадача 2

Дополнительные упрощения: 1 ≤ N ≤ 5 000.

Решение оценивается в 25 баллов.

Подзадача 3

Дополнительные упрощения: | Ai | ≤ 100 000.

Решение оценивается в 25 баллов.

Подзадача 4

Дополнительные упрощения отсутствуют.

Решение оценивается в 25 баллов.

Примеры

3.  Тексты задач для третьего интернет-тура

На третьем туре было предложено 4 задачи: задача A «Оранжерея», задача B «Экскурсия», задача C «CATS» и задача D «Обелиск».

Оранжерея

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мебибайт

Братья Алекс и Берт много лет работали и сажали деревья в большой оранжерее своего дяди. Оранжерея представляет собой массив деревьев размером п×т. Алекс сажал яблони, а Берт — банановые пальмы. Братья не следовали никакой системе, и некоторые яблони легко могли быть посажены среди пальм (и наоборот). Каждый из братьев посадил хотя бы одно дерево.

Перед уходом на пенсию дядя решил официально передать деревья во владение братьям. Он сказал им, что сначала все деревья перейдут во владение Алекса. Затем Алекс и Берт могут выбрать прямоугольный участок из оранжереи (со сторонами, параллельными сторонам оранжереи) и передать все деревья из этого прямоугольника Берту. Все последующие изменения могут быть сделаны только через юриста.

Алекс хочет получить во владение все свои яблони, а Берт – все свои пальмы, но пересаживать деревья они не хотят. Знакомый юрист согласился переоформить несколько деревьев с Алекса на Берта и наоборот, но за каждое дерево придётся заплатить $1. Теперь братья хотят выбрать такой прямоугольник, чтобы плата за переоформление была как можно меньше.

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

Рис. 1 Рис. 2 Рис. 3

В первом примере лучшим решением будет выбрать участок в виде четвёртого столбца и передать его Берту, как показано на рис. 1. После этого потребуется переоформить два дерева: одну пальму от Алекса Берту и одну яблоню от Берта Алексу. Таким образом, суммарная стоимость оформления составит $2.

Во втором примере (см. рис. 2) оптимальным решением будет выбрать все деревья не на границе поля и заплатить $6 за переоформление шести деревьев.

В третьем примере (см. рис. 3) одним из нескольких способов заплатить всего $1 будет выбрать прямоугольник из трех пальм и после этого дополнительно переоформить самую правую пальму на Берта.

Формат входных данных

Первая строка ввода содержит два положительных целых числа — п и т. Каждая из следующих п строк содержит по т нулей или единиц, где 0 обозначает яблоню, а 1 — банановую пальму.

Формат выходных данных

Необходимо вывести единственное целое число — минимальное количество долларов, требуемое для переоформления.

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

Подзадача 1

п = 1, 2 ≤ т ≤ 20.

Решение оценивается в 16 баллов.

Подзадача 2

п = 1, 2 ≤ т ≤ 15 000.

Решение оценивается в 16 баллов.

Подзадача 3

п = 1, 2 ≤ т ≤ 106.