Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Конь#38209

На доске размером KxN клеток (K строк, N столбцов) в j-й строке и i-м столбце стоит шахматный конь. Может ли он за один или несколько ходов попасть в клетку в m-й строке и s-м столбце?

Входные данные
Вводятся 6 натуральных чисел: K, N, j, i, m, s (1 ≤ K ≤ N ≤ 100). Клетки (i, j) и (s, m) не совпадают.

Выходные данные
Выведите слово YES, если такое возможно, и NO в противном случае.

Примеры

№	Входные данные	Выходные данные
1	8 8 1 2 7 8	YES

Условный оператор

✓ 22✗ 204800средняяВойти и решать

Автомат по продаже билетов#38206

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

Входные данные
Вводится сначала стоимость билета, который хочет приобрести пассажир, затем общее количество купюр и монет, которые он опустил в автомат, а затем достоинства каждой из этих купюр и монет. Входные данные записаны в одной строке и разделены пробелами. Известно, что сумма всех купюр больше, чем стоимость билета. Во всех тестовых примерах стоимость билета – натуральное число, не превосходящее 1 000 рублей, количество купюр и монет не более 50, достоинство каждой не превосходит 500 рублей. Общая сумма денег, опущенных в автомат покупателем, превосходит стоимость билета.

Выходные данные
Программа должна вычислить, какими купюрами и монетами можно выдать сдачу, и вывести достоинство каждой из этих купюр или монет в произвольном порядке. Автомат может выдавать сдачу купюрами в 10, 50, 100 и 500 рублей, а также монетами в 1, 2 и 5 рублей. Если решений несколько, требуется выдать одно любое из них. Если решений нет, требуется выдать текст:

Sorry! Our monetary system is not perfect!
Please, choose another way to pay!
Thank you!

Примеры

№	Входные данные	Выходные данные
1	100 1 500	50 100 100 100 50

Жадный алгоритм реализация

✓ 15✗ 42900средняяВойти и решать

Шахматное домино#38202

Комплект шахматного домино состоит из 32 костяшек 2x1, каждая из квадратов которой окрашен в черный или белый цвет (часть костяшек состоит из двух белых квадратов, часть – из двух черных, а часть из одного белого и одного черного). Комплект такого домино выложен на шахматную доску. Разрешается поворачивать костяшки домино на 180 градусов (менять местами их квадраты), оставляя каждую костяшку на своем месте. Требуется выяснить, можно ли так повернуть часть костей домино, чтобы в каждом горизонтальном ряду были квадраты только одного цвета.

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

Выходные данные
Требуется вывести одно слово – YES или NO (заглавными буквами).

Примеры

№	Входные данные	Выходные данные
1	1 2 2 7 7 8 8 9 1 3 6 10 10 11 11 9 4 3 6 31 31 24 23 12 4 5 5 30 32 24 23 12 28 29 29 30 32 25 22 13 28 27 27 26 26 25 22 13 18 19 19 20 20 21 21 14 18 17 17 16 16 15 15 14	YES

Примечание:
Доминошки нумеруются числами от 1 до 32 в произвольном порядке.

Двумерные массивы

✓ 4✗ 51 100средняяВойти и решать

Бегуны#38201

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

Входные данные
В первой строке вводится одно число – количество заданий, которые каждый спортсмен получил от тренера (оба спортсмена получают одинаковое количество заданий). В каждой из следующих строк записаны задания для спортсменов в следующем формате:

v₁ t₁ v₂ t₂

где v₁ – скорость первого игрока (в м/мин), t₁ – время, на протяжении которого спортсмен должен бежать со скоростью v₁; v₂ и t₂ – соответствующие величины для второго игрока. Скорости – положительные числа, если требуется бежать в направлении по часовой стрелке, и отрицательные, если требуется бежать против часовой стрелки.

Выходные данные
Выведите одно число – расстояние между бегунами в конце тренировки.

Примеры

№	Входные данные	Выходные данные
1	2 8000 1 8000 1 8000 10 8001 10	10
2	1 50 4 -100 1	100

Целые числа

✓ 14✗ 41900средняяВойти и решать

Метро#38191

Метрополитен состоит из нескольких линий метро. Все станции метро в городе пронумерованы натуральными числами от 1 до N. На каждой линии расположено несколько станций. Если одна и та же станция расположена сразу на нескольких линиях, то она является станцией пересадки и на этой станции можно пересесть с любой линии, которая через нее проходит, на любую другую (опять же проходящую через нее).

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

Входные данные
Сначала вводится число N — количество станций метро в городе (2≤N≤100). Далее следует число M — количество линий метро (1≤M≤20). Далее идет описание M линий. Описание каждой линии состоит из числа P_i— количество станций на этой линии (2≤P_i≤50) и P_i чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

Затем вводятся два различных числа: A — номер начальной станции, и B — номер станции, на которую нам нужно попасть. При этом если через станцию A проходит несколько линий, то мы можем спуститься на любую из них. Так же если через станцию B проходит несколько линий, то нам не важно, по какой линии мы приедем.

Выходные данные
Выведите минимальное количество пересадок, которое нам понадобится. Если добраться со станции A на станцию B невозможно, программа должна вывести одно число –1 (минус один).

Примеры

№	Входные данные	Выходные данные
1	5 2 4 1 2 3 4 2 5 3 3 1	0
2	5 5 2 1 2 2 1 3 2 2 3 2 3 4 2 4 5 1 5	2
3	10 2 6 1 3 5 7 4 9 6 2 4 6 8 10 7 3 8	1
4	4 2 2 1 2 2 3 4 1 3	-1

Способы задания графа

✓ 22✗ 2081 100средняяВойти и решать

Количество слов#38190

На вход программы поступает строка текста, в которой могут встречаться:
— прописные и строчные (т.е. большие и маленькие) латинские буквы;
— пробелы;
— знаки препинания: точка, запятая, восклицательный и вопросительный знак;
— символ –, обозначающий в некоторых случаях тире, а в некоторых — дефис.
Слово — это последовательность подряд идущих латинских букв и знаков дефис, ограниченная с обоих концов. В качестве ограничителей могут выступать начало строки, конец строки, пробел, знак препинания, тире. Тире отличается от дефиса тем, что слева и справа от знака дефис пишутся буквы, а хотя бы с одной стороны от тире идет либо начало строки, либо конец строки, либо пробел, либо какой-либо знак препинания, либо еще одно тире.
Напишите программу, определяющую, сколько слов в данной строке текста.

Входные данные
Вводится строка длиной не более 200 символов.

Выходные данные
Выведите одно число — количество слов, которые содержатся в исходной строке.

Примеры

№	Входные данные	Выходные данные
1	Hello , world!	2
2	www.olympiads.ru	3
3	Gyro-compass - this is a ...	4

Строки

✓ 29✗ 210800средняяВойти и решать

Кинотеатр#38189

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

Входные данные
Вводятся два числа — X и Y (оба числа натуральные, не превосходящие 100).

Выходные данные
Выведите какую-нибудь строку, в которой будет ровно X символов B (обозначающих мальчиков) и Y символов G (обозначающих девочек), удовлетворяющую условию задачи. Пробелы между символами выводить не нужно. Если рассадить мальчиков и девочек согласно условию задачи невозможно, выведите строку NO SOLUTION.

Примеры

№	Входные данные	Выходные данные
1	5 5	BGBGBGBGBG
2	5 3	BGBGBBGB
3	100 1	NO SOLUTION

Динамическое программирование: последовательности

✓ 29✗ 227900средняяВойти и решать

Симметричная последовательность#38188

Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:
1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.

Входные данные
Сначала вводится число N — количество элементов исходной последовательности (1 ≤ N ≤ 100). Далее идут N чисел — элементы этой последовательности, натуральные числа от 1 до 9.

Выходные данные
Выведите сначала число M — минимальное количество элементов, которое надо дописать к последовательности, а потом M чисел (каждое — от 1 до 9) — числа, которые надо дописать к последовательности.

Примеры

№	Входные данные	Выходные данные
1	9 1 2 3 4 5 4 3 2 1	0
2	5 1 2 1 2 2	3 1 2 1
3	5 1 2 3 4 5	4 4 3 2 1

Одномерные массивы

✓ 46✗ 111800средняяВойти и решать

Современное искусство - 3#38144

Наскучившись стандартными двумерными произведениями искусства (а также разочаровавшись тем, что другие копируют ее работы), великая художница Пикоусо решила перейти к более минималистичному, одномерному стилю. Ее последняя картина может быть описана одномерным массивом цветов длины N (\(1<=N<=300\)), где каждый цвет указывается целым числом в интервале \(1…N\).
К великому разочарованию Пикоусо, ее конкурент Муне, похоже, придумал, как копировать даже эти одномерные картины! Муне закрашивает один интервал одним цветом, ждет, пока он высохнет, затем красит другой интервал и так далее. Муне может использовать каждый из N цветов столько раз, сколько пожелает (возможно ни одного).

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

Входные данные
Первая строка содержит число N. Следующая строка содержит N целых чисел в интервале \(1…N\), указывающих цвет каждой ячейки в картине Пикоусо.

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

Примеры

№	Входные данные	Выходные данные
1	10 1 2 3 4 1 4 3 2 1 6	6

Пояснение

В этом примере Муне может скопироват картину так: (незакрашенные ячейки обозначены цветом 0).

Изначально весь массив не закрашен:
0 0 0 0 0 0 0 0 0 0
Муне закрашивает первые 9 ячеек цветом 1:
1 1 1 1 1 1 1 1 1 0
Муне закрашивает интервал цветом 2:
1 2 2 2 2 2 2 2 1 0
Муне закрашивает интервал цветом 3:
1 2 3 3 3 3 3 2 1 0
Муне закрашивает интервал цветом 4:
1 2 3 4 4 4 3 2 1 0
Муне закрашивает одну ячейку цветом 1:
1 2 3 4 1 4 3 2 1 0
Муне закрашивает последнюю ячейку цветом 6:
1 2 3 4 1 4 3 2 1 6
Заметим, что на первом движении кисти можно было закрасить цветом 1 и десятую ячейку. Это не изменило бы финальное состояние.

Динамическое программирование

✓ 3✗ 111 100средняяВойти и решать

Год Коровы - 2#38141

Известно, знаки зодиака в Китайском календаре следуют 12-летнему циклу: Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat, и затем опять Ox. Менее известен тот факт, что в конце каждого года Ox открывается временной портал, позволяющий коровам переместиться в любой другой год Ox в прошлом или будущем.

Корова Беси хочет посетить N своих предшественников, которые жили много раньше (\(1<=N<=0x10000\)). 0x10000 - это число в 16-ричной системе счисления, что равно 65536 в десятичной.

К несчастью, путешествия во времени утомительны, и Беси предпочитает сделать не более K прыжков во времени (\(1<=K<=N\)). Помогите Беси определить минимальное количество лет, которое потребуется Беси, чтобы посетить всех предшественников и вернуться в текущий год, совершив не более K прыжков во времени по пути.

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

Входные данные
Первая строка ввода содержит N и K. Следующие N строк содержат N различных целых чисел в интервале \(1…10^9\), указывающих сколько лет назад жил каждый из предшественников Беси.

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	5 3 101 85 100 46 95	36	Один из способов для Беси посетить всех своих предшественников за 36 лет таков: Войти в портал в текущем году и вернуться на 48 лет в прошлое. Подождать 12 лет затем войтив портал в 36 лет в прошлом и пропутешествовать 108 лет в прошлое. Подождать 24 года, затем зайти в портал в 84 года в прошлом и пропутешествовать обратно в текущий год.

Жадный алгоритм

✓ 6✗ 13800средняяВойти и решать

Комфорт для коров#38140

Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек (огромная шахматная доска). Изначально пастбище пустое.
Фермер Джон добавит N (1≤N≤10⁵) коров на пастбище одну за одной. i-ая корова занимает ячейку (x_i,y_i), которая отличается от ячеек, занятых всеми другими коровами (0≤x_i,y_i≤1000).

Говорят, что корове "комфортабельно", если по горизонтали и вертикали она имеет ровно три других коровы. Фермер Джон хочет посчитать, скольким коровам комфортабельно на его пастбище. Для каждого i в интервале 1…N, выведите общее количество коров, которым комфортабельно после того, как i-ая корова добавлена на пастбище.

Входные данные:
Первая строка содержит одно целое число N. Каждая из последующих N строк содержит два разделённых пробелом целых числа, указывающих (x,y) - координаты ячейки коровы. Гарантируется, что все ячейки различны.
Выходные данные:
i-ая строка вывода должна содержать общее количество коров, которым комфортабельно после добавления i-ой коровы на пастбище.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	8 0 1 1 0 1 1 1 2 2 1 2 2 3 1 3 2	0 0 0 1 0 0 1 2	После того, как добавлены первые 4 коровы, корове в ячейке (1,1) стало комфортабельно. После того, как добавлены первые 7 коров, корове в ячейке (2,1) стало комфортабельно. После того, как добавлены первые 8 коров, корове в ячейках (2,1) и (2,2) стало комфортабельно.

Двумерные массивы

✓ 104✗ 480800средняяВойти и решать

Организация коров фермера Джона#38133

Организация коров фермера Джона (UCFJ) направляет делегацию на Международную олимпиаду по овцеводству (IOI).
N коров участвуют в выборе делегации (1≤N≤2⋅10⁵). Они стоят в ряд, и корова i имеет породу b_i.

Делегация состоит из непрерывного интервала как минимум двух коров - то есть из коров l…r для целых l и r удовлетворяющих 1≤l<r≤N. две внешние коровы выбранного интервала называются "лидерами". Чтобы избежать конфликта между породами коров каждый лидер должен иметь породу отличающуюся от остальных коров делегации (лидеров и не лидеров).

Определите количество способов выбрать делегацию.

Входные данные:
Первая строка содержит N.
Вторая строка содержит N целых чисел b₁,b₂,…,b_N, каждое в интервале [1,N].

Выходные данные:
Количество возможных делегаций, на отдельной строке.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 1 2 3 4 3 2 5	13	Каждая делегация соответствует одной из следующих пар лидеров: (1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7).

Двоичное дерево поиска

✓ 4✗ 111 000средняяВойти и решать

Acowdemia I#38123

Беси учится на PhD в компьютерных науках. Она опубликовала N статей (1≤N≤10⁵) и её i-ую статью цитировали c_i раз (0≤c_i≤10⁵).

Беси слышала что академические успехи измеряются h-индексом. h-индекс - это наибольшее число h такое, что ученый имеет не менее h статей, каждая из которых цитируется не менее h раз. Например, учёный у которого четрые статьи с количествами цитат (1,100,2,3) имеет h-индекс равный 2, а ученый с количествами цитат (1,100,3,3) имеет h-индекс равный 3.

Чтобы повысить свой h-индекс Беси планирует написать обзорную статью, цитирующую некоторые из её прошлых статей. В связи с ограничением на количество страниц, она может включить не более L цитат в свой обзор (0≤L≤10⁵), т конечно она может процитировать каждую из своих статей не более одного раза.

Помогите Беси определить максимальный h-индекс, который она может достичь написанием своей обзорной статьи.

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

ФОРМАТ ВВОДА
Первая строка ввода содержит N и L.

Вторая строка ввода содержит N разделённых одиночными пробелами целых чисел c1,…,cN.

ФОРМАТ ВЫВОДА
Максимальный h-индекс, который Беси может получить написанием обзорной статьи.

№	Входные данные	Выходные данные	Пояснение
1	4 0 1 100 2 3	2	Беси не может цитировать свои статьи. Как указано ранее её h-индекс для (1,100,2,3) равен 2.
2	4 1 1 100 2 3	3	Если Беси процитирует третью статью, её количества цитирований станут (1,100,3,3). Как отмечено ранее, h в этом случае равен 3.

Использование сортировки

✓ 8✗ 69900средняяВойти и решать

Acowdemia II#38117

Беси поступает на работу в компьютерную лабораторию. Она хочет определить степерь важности каждого из N работников лаборатории (1≤N≤100). Все степени важности различны. То есть, нет двух работников с одинаковой степенью важности. Для определения степени важности сотрудников Беси использует список публикаций лаборатории.

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

Например, если лаборатория состоит (в порядке возрастания важности) из студентки Elsie, проф. Mildred и проф. Dean, они могут быть авторами статьи (Elsie-Mildred-Dean), если они все внесли различное количество усилий. А именно, Elsie внесла больше усилий чем Mildred, а Mildred больше чем Dean. Однако у них также может быть статья в порядке Elsie-Dean-Mildred если Mildred и Dean внесли одинаковое количество усилий, а Elsie больше их обоих.

По заданным K публикациям этой лаборатории (1≤K≤100), помогите Беси определить для всех пар сотрудников этой лаборатории кто более важен, если это возможно определить.

ФОРМАТ ВВОДА
Первая строка содержит два целых числа K и N.
Вторая строка содержит N разделённых одиночными пробелами строк, содержащих имена членов лаборатории. Каждое имя состоит не более чем из 10 маленьких латинских букв.

Каждая из следующих K строк содержит N разделённых одиночными пробелами строк, указывающих список авторов в одной публикации.

ФОРМАТ ВЫВОДА
Вывод должен состоять из N строк, по N символов в строке. На строке i, для любого j≠i, j-ый символ должен быть 1, если i-ый член более важный чем j-ый, 0, если i-ый член менее важный чем j-ый, и ? если невозможно определить при заданном списке публикаций.
i-ый символ в строке i должен быть B потому что это любимый символ Беси.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	1 3 dean elsie mildred elsie mildred dean	B11 0B? 0?B	В первом примере одна статья (elsie-mildred-dean) не даёт достаточно информации, чтобы определить кто важнее elsie или mildred. Однако точно Dean более важен чем оба. Поэтому возможны оба порядка Elsie<Mildred<Dean и Mildred<Elsie<Dean
2	2 3 elsie mildred dean elsie mildred dean elsie dean mildred	B00 1B0 11B	В этом втором примере единственный возможный порядок удовлетворяющий обоим статьям: Elsie<Mildred<Dean поскольку вторая публикация помогает определить, что Mildred важнее, чем Elsie.

Словари

✓ 5✗ 31 100средняяВойти и решать

Доставка контейнеров#38115

Малькольма Рейнольдса попросили доставить пустые контейнеры на самую отдаленную планету звездной системы. На корабле осталась только одна свободная ячейка объемом Х, в которую можно положить контейнеры. Капитан решил сложить несколько контейнеров друг в друга. Все контейнеры имеют подобные размеры. Контейнер с меньшим объемом свободно помещается в контейнер с объемом на 3 условных единицы больше. Определите, какое наибольшее количество контейнеров может доставить капитан Рейнольдс?

Входные данные
В первой строке вводится натуральное число Х - объем свободной ячейки (груз большего объема в ячейку не поместится). Во второй строке - количество контейнеров (целое неотрицательное число). В третьей строке - объем каждого контейнера. Все объемы - натуральные числа, не превосходящее 100, количество контейнеров не превосходит 1000.

Выходные данные
Выведите одно число — максимальное количество контейнеров, которое сможет доставить Малькольм Рейнольдс.

Примеры

№	Входные данные	Выходные данные
1	60 2 60 63	1
2	26 5 26 24 22 21 18	3

Квадратичные сортировки

✓ 199✗ 2 127900средняяВойти и решать

Оптимальное подмножество строк - 1#37888

Сегодня на уроке Петя узнал про беспрефиксные коды. Множество строк называется беспрефиксным кодом, если
- Все строки в множестве различны
- Не существует такой пары различных строк, что одна строка является префиксом другой
Строка s называется префиксом строки t, если длина строки s не больше длины t, а также для любого i, i-й символ строки s совпадает с i-м символом строки t. Например, ab является префиксом ab и abc, но не является префиксом a и ac.
Петя же решил придумать что-то новое и ввел новое понятие — k-беспрефиксный код. Таким кодом он назвал множество строк, такое, что:
- Все строки в множестве различны
- У любых двух различных строк наибольший общий префикс имеет длину не больше k
Наибольшим общим префиксом двух строк s и t называется наибольшая по длине строка, являющаяся префиксом обеих строк.
Теперь по данному множеству строк s1, s2, ..., sn и числу k Петя хочет найти в этом множестве k-беспрефиксный код, состоящий из максимально возможного количества строк. Помогите ему — найдите этот код.
Входные данные
В первой строке содержится два числа n и k — количество строк в множестве и максимальная длина общего префикса соответственно (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 100).
В i-й из следующих n строк содержится строка из строчных латинских букв si — i-е слово из множества (1 ≤ |si| ≤ 100).
Гарантируется, что суммарная длина всех строк в множестве не превосходит 10⁶.
Выходные данные
В первой строке выведите число m - максимально возможное количество строк в k-беспрефиксном
коде. В i-й из следующих m строк выведите i-й элемент этого кода. Элементы кода можно выводить в любом порядке.
Если существует несколько ответов с максимальным m, разрешается вывести любой.

Ввод	Вывод
5 2 aabc acbd aac acba aab	3 aab aac acba
4 2 aa abc aa abb	3 aa abb abc

Замечание
В первом примере у строк 1 и 5, а также у строк 2 и 4 наибольший общий префикс больше k, поэтому максимальное количество строк, из которых может состоять k-беспрефиксный код - 3. Во втором примере у любой пары подстрок наибольший общий префикс не больше 2, однако, так как код не может содержать одинаковые строки, больше 3 строк в него не включить.

Z-функция. Префикс-функция

✓ 11✗ 53900средняяВойти и решать

Самое главное – это семья!#37876

Одна из самых известных цитат из мультфильма: «Охана — значит семья, в семье не бросят никого и никогда и не забудут…» Что тут еще добавить? Так и есть!

Лило хочет составить генеалогическое древо своей семьи, для того, чтобы попытаться найти как можно больше своих родственником. В генеалогическом древе как известно у каждого кроме родоначальника, есть ровно один родитель. Лило хочет узнать, как расположить по отношению друг к другу некоторых двух членов семьи. Старшая сестра Лило Нани прекрасно помнит, кто является родителем кого. Она готова помочь Лило, но у нее так много работы. Помогите Нани написать программу для Лило.

Входные данные
Программа получает на вход число элементов в генеалогическом древе N. Далее следует \(N-1\) строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид:
имя_потомка имя_родителя.

Далее до конца файла идут строки, содержащие имена двух элементов дерева.

Выходные данные
Для каждого такого запроса выведите одно из трех чисел:
1 - если первый элемент является предком второго;
2 - если второй является предком первого;
0 - если ни один из них не является предком другого.

Примеры

№	Входные данные	Выходные данные
1	9 Keaka Kayla Ikika Kayla Akeneki Kayla Neolani Keaka Ley Ikika Kianalu Ley Aalona Kianalu Iukini Kianalu Ikika Iukini Neolani Kayla Keaka Kianalu END!	1 2 0

Словари

✓ 149✗ 434800средняяВойти и решать

Перебор элементов матрицы#37865

Напишите программу, которая вычисляет сумму элементов матрицы.

Входные данные: В первой строке записаны через пробел размеры матрицы: количество строк N и количество столбцов M ( 1 <= N , M <= 100 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.

Выходные данные: Программа должна вывести одно число – сумму элементов матрицы.

Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 3 4 5 6 12 8 9 10 11 12 12 14 15 16 17 18 12 20	207

Двумерные массивы

✓ 3✗ 16800средняяВойти и решать

Тренировки#37708

Внешкольная жизнь Маши, Даши и Миши очень насыщенная. Все вместе дети посещают \(K\) кружков. Дни, когда работает какой-либо кружок, родителям после работы приходится отвозить ребят на тренировки. Если дни занятий не выходные (суббота или воскресенье), то такие дни считаются загруженными.
Все кружки работают через определенное число дней. i-й кружок работает каждый \(b_i\) день, начиная с дня c номером \(a_i\). То есть i-й кружок работает в дни \(a_i\), \(a_i+b_i\), \( a_i+2b_i\) и т.д.
В календаре дополнительных занятий \(N\) дней, пронумерованных от 1 до \(N\). Первый день всегда понедельник, шестой и седьмой дни - выходные, неделя состоит из семи дней.

Входные данные: программа получает на вход число дней в календаре \(N\) (\(1<=N<=10^6\)) и число кружков \(K\) (\(1<=K<=100\)). Далее идет \( K\) строк, описывающие графики проведения тренировок. \(i\)-я строка содержит числа \(a_i\) и \(b_i\) (\(1<=a_i,b_i<=N\)).

Выходные данные: выведите единственное число: количество загруженных дней у родителей в течение всего календаря занятий.

Примечание: первый кружок работает в дни 2, 5, 8, 11, 14, 17. Второй кружок работает в дни 3, 8, 13, 18. Третий кружок - в дни 9 и 17. Дни номер 6, 7, 13, 14 являются выходными. Таким образом, загруженными будут дни 2, 3, 5, 8, 9, 11, 17, 18.

Примеры

№	Входные данные	Выходные данные
1	19 3 2 3 3 5 9 8	8

Множества

✓ 47✗ 191900средняяВойти и решать

Космические шахматы#37693

В космические шахматы играют на бесконечной доске, поэтому клетки нумеруют парой чисел (см. пример и рисунок к нему). Фигуры ходят по обычным правилам. Составьте маршрут шахматного коня из клетки (0; 0) в заданную клетку (x; y).
Напомним, что конь за один ход перемещается на одну клетку по одной оси и на две по другой, то есть, например, из клетки (0; 0) он за один ход может попасть в клетки (1; 2), (2; 1), (-1; 2), (2; -1), (1; -2), (-2; 1), (-1; -2) и (-2; -1).

В качестве ответа Вам нужно вывести любой (не обязательно кратчайший) маршрут с началом в (0; 0) и концом в (x; y), длина которого не больше 10⁵ ходов.

Формат входных данных
Программа получает на вход два целых числа x и y, записанных в отдельных строках, - координаты конечной клетки маршрута коня. Клетка (x; y) не совпадает с началом координат. |x| <= 10⁵, |y| <= 10⁵.

Формат выходных данных
Программа должна вывести последовательность ходов, один ход в отдельной строке. В i-й строке должно быть выведено два числа x_i и y_i через пробел - координаты клетки, в которой окажется конь после i-го хода. Количество ходов не должно превышать 10⁵. Последний ход должен вести в заданную клетку

Ввод	Вывод
-2 2	-2 1 0 2 -1 0 -2 2

Рисунок к примеру

Задачи на моделирование реализация

✓ 18✗ 671 000средняяВойти и решать