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

Современное искусство - 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средняяВойти и решать

Подсчёт коров#38143

Коровы Фермера Джона разбрелись по огромному пастбищу, представленному в виде 2D-решётки (шахматной доски). Размещение коров весьма занимательно. Для каждой ячейки (x,y) с \(x>=0\) и \(y>=0\), существует корова в ячейке (x,y), если для всех целых чисел \(k>=0\), остатки \(\lfloor {\frac {x}{3^k} }\rfloor\) и \(\lfloor {\frac {y}{3^k} }\rfloor\) по модулю 3 имеют одну и ту же четность. Другими словами оба эти остатка нечётные (равны 1) или оба чётные (равны 0 или 2). Например, ячейки для \(0<=x,y<9\), которые содержат коров обозначены цифрой 1 на рисунке ниже.

 x
    012345678

  0 101000101
  1 010000010
  2 101000101
  3 000101000
y 4 000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101

Ферме Джон интересуется сколько коров присутствует в определённом квадратном регионе его пастбища. Он задаёт Q вопросов, кажый содержит три целых числа x_i,y_i,d_i. Для каждого вопроса Фермер Джон хочет знать, сколько коров в ячейках с (x_i, y_i) до (x_i+d_i, y_i+d_i) (включая конечные точки).

Входные данные
Первая строка содержит Q (\(1<=Q<=10^4\)) - количество вопросов.
Каждая из следующих Q строк содержит 3 целых числа d_i, x_i, и y_i (\(0<=x_i,y_i,d_i<=10^{18}\)).

Выходные данные
Q строк, по одной для каждого вопроса - одно целое число - ответ.

Примеры

№	Входные данные	Выходные данные
1	8 10 0 0 10 0 1 9 0 2 8 0 2 0 1 7 1 1 7 2 1 7 1000000000000000000 1000000000000000000 1000000000000000000	11 0 4 3 1 2 2 1000000000000000001

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

✓ 2✗ 5—Войти и решать

Год Коровы - 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средняяВойти и решать

Достаточно зеленого#38139

Пастбище Фермера Джона может рассматриваться как NхN решётка (\(1<=N<=500\)) квадратных ячеек с травой (как большая шахматная доска). Из-за изменчивости почвы, трава в некоторых ячейках зеленее, чем в других. Каждая ячейка (i,j) описывается целым числом - уровнем зелёности G(i,j), в интервале \(1…200\).

Фермер Джон хочет сделать фотографию прямоугольной подрешётки своего пастбища. Он хочет, чтобы минимальная из величин G на его фотографии была ровна 100. Помогите ему посчитать, сколько таких различных фотографий он сможет сделать. Подрешётка может быть размером от всего пастбища и до одной ячейки. Всего существует \(N^2(N+1)^2/4\) различных подрешёток, для хранения такого числа используйте 64-битное целое (типа long long в C++).

Входные данные
Первая строка содержит N. Каждая из следующих N строк содержит N целых чисел и все вместе они описывают величины G(i,j) для пастбища NхN .

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

Заметим, что для ответа требуется использовать 64-битную целую переменную типа long long в C++.

Примеры

№	Входные данные	Выходные данные
1	3 57 120 87 200 100 150 2 141 135	8

Префиксные суммы(минимумы, ...)

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

Забор по часовой стрелке#38137

Фермер Джон решил заменить изгородь вокруг своего пастбища.
Эта новая изгородь описывается строкой символов, каждый из которых "N" (north), "E" (east), "S" (south), или "W" (west). Каждый символ описывает 1 метр изгороди. Например, если строка NESW, это означает, что изгородь начинатся одним метром на север, затем 1 метр на восток, затем 1 метр на юг, и затем 1 метр на запад, возвращаясь в стратовую точку.

Изгородь всегда заканчивается в той же позиции, где стартовала, и это - единственная точка, посещенная более одного раза путем изгороди (а стартовая точка, единственная точка посещённая второй раз - в конце пути). Как следствие, изгородь огораживает один связный регион травяного пастбища, даже если этот регион может иметь довольно странную форму.

Фермер Джон хочет узнать, указанный путь обходится по часовой стреле или против часовой стрелки? По часовой стрелке - огороженный регион находится по правую сторону от изгороди, если идти по пути, определённому строкой. Против часовой стрелки - огороженный регион находится по левую сторону от изгороди, если идти по пути, определённому строкой.

Входные данные:
Первая строка содержит целое число N (1≤N≤20). Каждая из последующих N строк содержит строку длиной не менее 4 символов и не более 100, описывающую путь изгороди.
Выходные данные:
Для каждого из N путей, описанных по вводе, выведите строку содержащую "CW" (clockwise - по часовой стрелке) или "CCW" (counterclockwise - против часовой стрелки).

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 NESW WSSSEENWNEESSENNNNWWWS	CW CCW	Оба пути (? символ "пробел") обозначает стартовую точку: > ^ v <* <<< v ^ < v ^ * >>* * v ^ v ^ * < * * v ^ v ^ >>* >

Элементарная геометрия

✓ 4✗ 10—Войти и решать

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

Из N коров выбирается делегация (1≤N≤2⋅10⁵). Они стоят в ряд, корова i имеет породу b_i.

Делегация будет состоять из непрерывного участка коров не менее трёх, то есть коровы l…r для целых l и r удовлетворяющих условиям 1≤l<r≤N и r−l≥2. Три коровы в выбранном интервале помечаются как лидеры делегации. Две граничные коровы обязательно должны быть лидерами. Кроме того, каждый лидер должен иметь породу отличную от всех остальных коров в делегации (лидеры или не лидеры).

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

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

Примеры

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

Дерево отрезков, RSQ, RMQ

✓ 1✗ 1—Войти и решать

Организация коров фермера Джона#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средняяВойти и решать

Перестановка#38131

У Беси есть N (3≤N≤40)любимых точек на 2D-решётке, никакие три из которых не коллинеарны. Для каждого 1≤i≤N, i-ая точка задаётся двумя целочисленными координатами x_i и y_i (0≤x_i,y_i≤10⁴).
Беси рисует некоторые отрезки между точками следующим образом:

Она выбирает некоторую перестановку p₁,p₂,…,p_N из N точек
Она рисует отрезки между p₁ и p₂, p₂ и p₃, p₃ и p₁.
Затем для каждого целого i от 4 до N по порядку, она рисует отрезки прямых от p_i до p_j для всех j<i так, этот отрезок не пересекает никакой из ранее нарисованных отрезков (вне конечных точек)
Беси заметила, что для каждого i она нарисовала ровно три новых отрезка. Вычислите количество перестановок, которые Беси могла выбрать на шаге 1, которые удовлетворяют этому свойству по модулю 10⁹+7.

Входные данные:
Первая строка содержит N.
Каждая из последующих N строк содержит два разделённых пробелом целых числа x_i и y_i.

Выходные данные:
Количество перестановок по модулю 10⁹+7.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 0 0 0 4 1 1 1 2	0	Никакая перестановка не сработает.
2	4 0 0 0 4 4 0 1 1	24	Все перестановки работают.
3	5 0 0 0 4 4 0 1 1 1 2	96	Одна из перестановок, удовлетворяющих свойству - (0,0),(0,4),(4,0),(1,2),(1,1). Для этой перстановки Сначала она рисует отрезки между каждой парой (0,0),(0,4), и (4,0). Затем она рисует отрезки от (0,0), (0,4), и (4,0) до (1,2). Наконец, она рисует отрезки от (1,2), (4,0), и (0,0) до (1,1). Рисунок: Перестановка не удовлетворяет свойству, если её первые четыре точки (0,0)(0,0), (1,1)(1,1), (1,2)(1,2), и (0,4)(0,4) в некотором порядке.

Рекуррентные последовательности

✓ 2✗ 1—Войти и решать

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средняяВойти и решать

Дамка#37893

Домовой Кузьма очень любит играть в шашки на доске 8х8. Когда никто не хочет с ним играть, он просто сидит и думает. Например, сейчас он пытается посчитать сколько есть вариантов провести белую шашку в дамки, если она находится одна на доске?
(Белая шашка ходит по диагонали на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)

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

Вводятся два числа от 1 до 8: номер номер столбца (считая слева) и строки (считая снизу), где изначально стоит шашка.

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

Выведите одно число - количество вариантов.

Примеры

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

Динамическое программирование на таблицах

✓ 178✗ 286600лёгкаяВойти и решать

Муравьиная ферма#37892

У мальчика Пети есть муравьиная ферма. На ферме есть участок прямоугольной формы, состоящий из NxM квадратов. В правом нижнем квадрате данной области имеется дырка, благодаря которой можно сбежать с фермы. Каждый день очередной муравьишка начинает свой путь с левой верхней клетки. Далее он перемещается в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться он не может), и двигается так до достижения правой нижней клетки. Затем он выбирается наружу. Каждый муравьишка двигается своим уникальным путем (т.е. никакой муравей не повторяет ни один путь другого). Если муравей не может пойти по своему уникальному пути, то он остается на ферме. Посчитайте, сколько муравьев сбежит с фермы и поселится в комнате Пети.

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

Вводятся два числа N и M - размеры таблицы (\(1<=N<=10\), \(1<=M<=10\)).

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

Выведите искомое количество способов.

Примечание
При указанных ограничениях число способов входит в тип Longint.

Примеры

№	Входные данные	Выходные данные
1	1 10	1

Динамическое программирование на таблицах

✓ 210✗ 229500лёгкаяВойти и решать

Играем в Камушки#37891

Когда-то в далеком детстве мы все с удовольствием играли в игру "Камушки" или "Пять камешков", кто как называл. Для игры нужны были обычные камешки, которые можно было запросто найти на улице. Играть можно было в любом месте, Для игры нужна была небольшая ровная площадка утоптанной земли или ровный пол крыльца или беседки.
Первый шаг игры заключался в следующем. На землю перед собой бросаются все пять камешков. Выбирался один из них. Это биток. Этот камешек подбрасывается в воздух и, пока он летит, необходимо поднять один из оставшихся на земле камешков и успеть подхватить этой же рукой летящий. Подобранный камешек откладывается в сторону и действие повторяется для всех оставшихся камешков.
На следующих шагах количество камешков, которые надо подхватить увеличивается. Последним шагом был экзамен, когда необходимо было подбросить все собранные камешки в воздух и поймать их тыльной стороной ладони, а затем опять подбросить, и поймать открытой ладонью. Сколько камешков в итоге оставалось, столько баллов и получаешь. Ход переходит к следующему игроку, который также повторяет все шаги. Далее запускался новый тур игры. Выигрывал тот, кто набирал больше всего баллов за все туры.
Многие ребята усложняли игру самыми разными способами.
Допустим у ребят есть бесконечное число камешков лежащих на земле. В конце тура им необходимо поймать в ладони не все камешки, а ровно столько, чтобы общее число баллов у них увеличилось на 1 или удвоилось или утроилось. Перед началом игры у всех уже имеется 1 балл. Победителем будет считаться тот, кто быстрее наберет N баллов.
Будем считать, что у всех играющих достаточно опыта игры, и они всегда доходят до экзамена с нужным им числом камней (чтобы была возможность нужное число баллов увеличить на 1, удвоить или утроить).

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

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

Программа получает на вход одно число, не превосходящее 10⁶.

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

Требуется вывести одно число: наименьшее количество искомых операций.

Примеры

№	Входные данные	Выходные данные
1	1	0
2	5	3
3	32718	17

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

✓ 465✗ 899600лёгкаяВойти и решать

Хлебные крошки#37890

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

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

На вход программы поступает целое число N (\(1<=N<=100\) ).

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

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	1	2

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

✓ 793✗ 1 020400лёгкаяВойти и решать

Слинки "Радуга"#37889

Слинки — игрушка-пружина, созданная в 1943 году в США Ричардом Джеймсом. В нашей стране она называлась просто Радуга. Все дети любили ее запускать со ступенек, считая у кого она спустится ниже.
Обычно "Радуга" в руках детей спускалась на следующую ступеньку, на ступеньку через одну или через 2. (Например, если Радугу запускали с 10-ой ступеньки, то она могла остановиться на 9-ой, 8-ой или 7-ой.)
Допустим на лестнице N ступенек. Определите число всевозможных "маршрутов" Радуги с вершины лестницы на землю.

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

Вводится одно число \(0 < N < 31\).

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

Выведите одно число — количество "маршрутов" Радуги.

Примеры

№	Входные данные	Выходные данные
1	4	7

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

✓ 834✗ 1 217400лёгкаяВойти и решать

Оптимальное подмножество строк - 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средняяВойти и решать

Стич учит английский#37878

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

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

Входные данные
Сначала вводится число N — количество слов в словаре (\(0 <= N <=20000\)).
Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.

Далее идет запись разговора Стича. Разговор представляет собой строку текста, суммарным объемом не более 300000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Стич поставил ударение). Стич мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выходные данные
Выведите количество ошибок в речи Стича.

Примеры

№	Входные данные	Выходные данные	Примечание
1	4 cAnnot cannOt fOund pAge thE pAge cAnnot be found	2	В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот). Две ошибки, совершенные Стичем - это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Стич поставил ровно одно ударение, признается верным.
2	4 cAnnot cannOt fOund pAge The PAGE cannot be found	4	Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

Словари

✓ 309✗ 848600лёгкаяВойти и решать

Первое впечатление может быть обманчивым#37877

Нани с первых минут невзлюбила Стича и даже боялась оставаться вместе с ним в одном доме. Но спустя время она разглядела в малыше добрую душу и приняла его в свою семью. Вместе со Стичем пришлось приютить и его создателя Джамбо, которому пришлось остаться на Земле.
Чтобы запомнить имена новых знакомых инопланетян, Джамбо вносит их в компьютер. Имена инопланетянин могут содержать самые различные символы, но всегда удовлетворяют особым правилам. Правила следующие: все имена содержат только латинские буквы (заглавные и строчные), цифры и знак подчёркивания. Имя всегда начинается либо с буквы, либо со знака подчеркивания. Другие символы в именах отсутствуют.
Напишите для Джамбо программу, которая бы проверяла правильно ли он занес в компьютер имя очередного знакомого.

Входные данные
На вход программы подаётся символьная строка - имя, которое Джамбо занес в компьютер.

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

Примеры

№	Входные данные	Выходные данные
1	Abc123	YES
2	Abc[a!	NO

Множества

✓ 519✗ 1 044400лёгкаяВойти и решать