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

Луч света в темном царстве#38360

Темное царство представляет собой лабиринт NxM, некоторые клетки которого окружены зеркальными стенами, а остальные — пустые. Весь лабиринт также окружен зеркальной стеной. В одной из пустых клеток лабиринта поставили светофор, который испускает лучи в 4 направлениях: под 45 градусов относительно стен лабиринта. Требуется изобразить траекторию этих лучей.

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

Входные данные
В первой строке входного файла записаны два натуральных числа N и M — число строк и столбцов в лабиринте (каждое из чисел не меньше 1 и не больше 100). В следующих N строках записано ровно по M символов в каждой — карта лабиринта. Символ * (звездочка) обозначает клетку, окруженную зеркальными стенками, . (точка) — пустую клетку, символ X (заглавная латинская буква X) — клетку, в которой расположен светофор (такая клетка ровно одна).

Выходные данные
В выходной файл выведите N строк по M символов в каждой — изображение лабиринта с траекториями лучей. Здесь, как и раньше, * (звездочка) должна обозначать клетки, окруженные зеркальными стенами, . (точка) — пустые клетки, через которые лучи света не проходят, / (слеш) — клетки, через которые луч света проходит из левого нижнего угла в правый верхний (или обратно — из правого верхнего в левый нижний), \ (обратный слеш) — клетки, через которые луч проходит из левого верхнего угла в правый нижний (или обратно), а символ X (заглавная латинская буква X) — клетки, через которые лучи проходят по обеим диагоналям.

Примеры

№	Входные данные	Выходные данные
1	3 5 X.... ..... .....	XXXXX XXXXX XXXXX
2	3 3 ... ..X ...	/X\ X.X \X/

Двумерные массивы Задачи на моделирование

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

Черно-белые палиндромы#38359

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

Вам дана полоса длины N. Требуется разрезать ее на полоски, являющиеся палиндромами, так, чтобы количество получившихся полосок было строго меньше величины (2/5)N + 3.

Входные данные
Первая строка входного файла содержит число N — длину исходной полосы (N — натуральное число, не превышающее 100000). Далее идет N чисел, описывающих раскраску полосы: 0 означает черную клетку, а 1 — белую.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	6 0 1 0 1 1 0	3 5	Из исходной полосы мы получим 3 полосы-палиндрома, сделав разрезы после 3-й клетки (то есть между 3-й и 4-й) и после 5-й (то есть между 5-й и 6-й)
2	6 0 1 1 0 0 0	1 3	Данную полосу можно разрезать на 2 полосы-палиндрома, однако по условию не требуется искать решение с минимальным числом получившихся полосок — достаточно, чтобы число полосок удовлетворяло указанному в условии ограничению.
3	5 0 0 0 0 0		Исходная строка уже является палиндромом, поэтому можно ничего не разрезать

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

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

Перегоны#38355

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

Входные данные
Во входном файле записаны сначала числа N — количество станций (2 ≤ N ≤ 100) и E — количество пар станций, расстояния между которыми заданы (0 ≤ E ≤ 10000). Далее идет E троек чисел, первые два числа каждой тройки задают номера станций (это числа из диапазона от 1 до N), а третье — расстояние между этими станциями (все эти расстояния заданы точно и выражаются вещественными неотрицательными числами не более чем с 3-я знаками после десятичной точки).

Выходные данные
В случае, когда восстановить длины перегонов можно однозначно, в выходной файл выведите сначала число 1, а затем N–1 вещественное число. Первое из этих чисел должно соответствовать расстоянию от 1-й станции до 2-й, второе — от 2-й до 3-й, и так далее. Все числа должны быть выведены с точностью до 3-х знаков после десятичной точки.

Если приведенная информация о расстояниях между станциями является противоречивой или не позволяет однозначно точно восстановить длины перегонов, выведите в выходной файл одно число 2.

Примеры

№	Входные данные	Выходные данные
1	2 3 1 1 0 2 2 0 2 1 2.5	1 2.500
2	15 13 1 2 1 1 3 2 1 4 3 1 5 4 1 6 5 1 7 6 1 8 7 1 9 8 1 10 9 1 11 10 1 12 11 1 13 12 15 14 13	2

Обход в глубину

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

Соберите числа#38351

У Васи в распоряжении оказался набор кубиков. Вася решил на каждой грани каждого кубика написать по цифре и дальше использовать кубики для того, чтобы складывать из них числа. Вася хочет написать цифры так, чтобы уметь складывать любое число от 1 до некоторого числа K. Посчитайте такое максимальное K, до которого Вася сможет выкладывать все числа, если в распоряжении у Васи оказалось N кубиков. Заметьте, что если на какой-то грани какого-то кубика написана цифра 6, то эту же грань можно использовать и как цифру 9, просто перевернув соответствующий кубик.

При выкладывании числа Вася не обязан использовать все кубики. Ведущие нули в числах не нужны.

Рассмотрим примеры.

Пусть N=1. Тогда, написав на гранях кубика цифры от 1 до 6, Вася сможет выкладывать числа от 1 до 6. Тем самым, K=6.

Пусть N=2. Тогда, написав на гранях одного кубика цифры от 1 до 6, а на гранях другого цифры 0, 1, 2, 3, 7, 8, Вася сможет выложить любое число от 1 до 43.

Входные данные
Во входных данных записано одно число N (1≤N≤1000000).

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

Примеры

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

Эвристические методы

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

Посчитайте лампы#38348

На новой станции метро, которую планируют открыть в конце этого года, будет N эскалаторов (эскалаторы пронумерованы подряд числами от 1 до N). Эскалаторы имеют длину L и расположены на расстоянии H друг от друга. Шириной эскалатором пренебрежем. Между каждыми двумя соседними эскалаторами (точно посередине) будет установлен ряд ламп. В ряду будет K ламп. Лампы устанавливаются по следующему принципу: всю длину эскалатора L разбивают на K равных отрезков и в середине каждого отрезка устанавливают по лампе (см. рисунок). Всего будет установлено (N–1)*K ламп.

На приведенном рисунке N=4 (эскалаторы показаны жирными <горизонтальными линиями), L=20, H=4, K=5.

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

Входные данные
Во входном файле записаны числа N, L, H, K, J. Все числа — натуральные. 2≤N≤35, 1≤L≤1000, 1≤H≤1000, 1≤K≤35, 1≤J≤N.

Выходные данные
В выходной файл выведите одно число — ответ задачи.

Примеры

№	Входные данные	Выходные данные
1	2 20 4 5 1	0
2	4 20 4 5 2	11

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

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

Ёлочка#38324

«Нарисуйте» с помощью символов на экране лес. При этом не пользуйтесь командами перемещения курсора по экрану. Ваша программа должна последовательно выводить символы строк (или строки целиком).

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

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

Елочки должны изображаться символами «#» (решеточка), а пустые места между ними — символами «.» (точка). Во всех строках должно быть выведено одинаковое количество символов, при этом обязательно должна быть строка, в которой последним символом является решеточка, в последней строке обязательно должны быть решеточки (т.е. должен быть выведен прямоугольник из точек и решеточек, в нем не должно быть лишних столбцов и строк).

Входные данные
Вводится число елочек N, а дальше N пар натуральных чисел, описывающих елочки: первое число каждой пары задает количество треугольников в елочке, а второе — размер самого маленького треугольника. Елочки описываются в порядке слева направо (если смотреть на вершины елочек).

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

Выходные данные
Выведите требуемый «рисунок». Для лучшего понимания смотрите примеры.

Примеры

№	Входные данные	Выходные данные
1	2 3 2 3 3	...#......#.... ..###....###... ...#....#####.. ..###.....#.... .#####...###... ...#....#####.. ..###..#######. .#####....#.... #######..###... ........#####.. .......#######. ......#########
2	3 1 1 2 1 3 2	#.#...#... ..#..###.. .###..#... .....###.. ....#####. ......#... .....###.. ....#####. ...#######

№

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

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

2
3 2
3 3

...#......#....
..###....###...
...#....#####..
..###.....#....
.#####...###...
...#....#####..
..###..#######.
.#####....#....
#######..###...
........#####..
.......#######.
......#########

3
1 1
2 1
3 2

#.#...#...
..#..###..
.###..#...
.....###..
....#####.
......#...
.....###..
....#####.
...#######

Задачи на моделирование Символы

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

Робот#38285

На Марсе есть большой полигон для испытания роботов. Он представляет собой таблицу из n строк и m столбцов, столбцы которой направлены с севера на юг, а строки — с запада на восток. В каждой клетке таблицы находится ускоритель, направленный в одну из сторон света.

Находясь в клетке, робот может воспользоваться ускорителем в ней. При этом он попадает в соседнюю с текущей клетку в направлении ускорителя и не тратит топливо. Если соседней клетки в направлении ускорителя нет, то им нельзя воспользоваться. Также робот может не пользоваться ускорителем и переместиться в любую из соседних клеток, затратив один литр топлива.

Сегодня роботу дали следующее задание: ему надо доехать из первой клетки первого столбца в последнюю клетку последнего столбца. Напишите программу, которая определит, какое минимальное количество топлива ему придется для этого потратить.

Рисунок ниже показывает полигон, заданный в примере. Ускорители показаны в виде стрелок. Заштрихованы клетки, по которым оптимально проехать роботу. Ускорители, которыми робот воспользовался, показаны жирными стрелками.

Входные данные
Первая строка входных данных содержит два числа n и m — протяженность полигона с севера на юг и с запада на восток ( 1 ≤ n , m ≤ 20 ).

Следующие n строк содержат по m латинских букв, описывающих направления ускорителей в очередной строке. Буква соответствуют направлению ускорителя: N — на север, W — на запад, S — на юг, E — на восток. Строки занумерованы с севера на юг, а столбцы с запада на восток. Таким образом, направление на север соответствует уменьшению номера строки, направление на юг — увеличению номера строки, направление на запад — уменьшению номера столбца, а направление на восток — увеличению номера столбца.

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

Примеры

№	Входные данные	Выходные данные
1	5 3 SSN NSN SWN SWE ENS	2

0-1 BFS

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

Порталы#38132

Беси расположена на сети из N (2≤N≤10⁵) вершин помеченных 1…N и 2N порталов помеченных 1…2N. Каждый портал соединяет две различных вершины u и v (u≠v). Множество порталов может соединять некоторую пару вершин.
Каждая вершина v соседняя для четырёх различных порталов. Список порталов вершины v задаётся как pv=[p_v,1,p_v,2,p_v,3,p_v,4].

Ваше текущее положение может быть представлено упорядоченной парой (current vertex,current portal); то есть парой (v,p_v,i) где 1≤v≤N и 1≤i≤4. Вы можете использовать одну из следующих операций для изменения своего текущего положения:

Изменить текущую вершину перемещением через текущий портал.
Переключить текущий портал. В каждой вершине первые два портала в списке объединены в пару и последние два портала в списке также объединены в пару. Поэтому если Ваше текущее состояние (v,p_v,2), то Вы можете переключиться чтобы использовать портал (v,p_v,1) и обратно. Аналогично, если Ваше текущее положение (v,p_v,3) Вы можете переключиться на портал (v,p_v,4) и обратно. никакие другие переключения не разрешены (например, Вы не можете переключиться с портала pv,2 на портал) p_v,4).
Всего имеется 4N различных состояний. К несчастью, может не оказаться, что что любое состояние достижимо из любого с помощью последовательности заданных операций. Поэтому, за цену cv (1≤c_v≤1000) мунов вы можете сделать перестановку списка порталов соседних вершине v, в любом желаемом Вами порядке. После этого первые два портала в списке объединяются в одну пару, а последние два портала - в другую пару.

Например, если Вы переставить порталы вершины v в порядке [p_v,3,p_v,1,p_v,2,p_v,4], Это означает. что если Вы в вершине v,

Если Вы в портале p_v,1, Вы можете переключиться на портал p_v,3 и обратно
Если Вы в портале p_v,2, Вы можете переключиться на портал p_v,4 и обратно
Теперь Вы не можете переключаться с портала p_v,1 на p_v,2, или с портала p_v,3 на портал p_v,4 и обратно.
Вычислите минимальное количество мунов, требуемых для модификации сети таким образом, чтобы сделать достижимым каждое состояние из каждого состояния. Гарантируется, что тестовые данные сконструированы таким образом, что существует хотя бы один способ такой модификации сети.

Входные данные:
Первая строка содержит N.
Каждая из следующих N строк описывает вершину. Строка v+1 содержит 5 разделённых одиночными пробелами целых чисел c_v,p_v,1,p_v,2,p_v,3,p_v,4.
Гарантируется, что для каждой v все p_v,1,p_v,2,p_v,3,p_v,4 различны, и каждый портал появляется в списках ровно двух вершин.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 10 1 4 8 9 11 1 2 5 6 12 9 10 2 3 3 4 3 6 7 15 10 8 7 5	13	Достаточно сделать перестановку списков вершин 1 и 4. Это требует c1+c4=13 мунов. Перестановки такие: p1=[1,9,4,8] и p4=[7,4,6,3].

Древовидные структуры данных Минимальный каркас Система непересекающихся множеств

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

Мячи по сеткам#37502

На складе в коробки упаковывают волейбольные мячи. Сначала мячи пакуются в сетки ровно по N штук в каждую, а потом сетки - в коробки, причем в одну коробку помещается не более L сеток. Последняя коробка может быть неполная. Всего имеется М мячей. Сколько всего понадобится коробок, сколько сеток будет в последней коробке и сколько мячей останется на складе не упаковано (упаковать нужно как можно больше мячей)? Написать программу: вводятся три числа целых M, L, N в одной строке; вывести три числа в одной строке - сначала количество потребовавшихся коробок, затем количество сеток в последней коробке, а затем количество не упакованных мячей

Примеры

№	Входные данные	Выходные данные
1	40 4 3	4 1 1

Вычисление по заданной формуле Задачи на моделирование

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

Дом у озера#34780

Есть озеро, рядом с которым хотят построить дом. Архитектурный проект (форма дома) уже утверждён, можно только выбрать расположение дома так, чтобы он оказался рядом с озером. Желательно выбрать расположение дома рядом с озером так, чтобы у как можно большего числа жителей дома окна выходили на озеро, то есть чтобы длина общей границы дома и озера была максимальной.

План дома и озера задан в виде изображения на клетчатой бумаге, в котором отмечены клетки, принадлежащие дому и озеру. Первая строка входных данных содержит число N – количество строк в плане дома и озера. Вторая строка входных данных содержит число M – количество столбцов в плане дома и озера.

Следующие N строк содержат по M символов – план дома. Символ «.» в этих строках обозначает пустую клетку, символ «H» обозначает» обозначает клетку дома. План дома является связной областью и не содержит «дырок» внутри. В плане есть хотя бы одна клетка, принадлежащая дому. Следующие N строк по M символов в каждой содержат план озера, в этих строках символ «.» обозначает пустую клетку, символ «W» обозначает клетку, занятую озером. План» обозначает клетку, занятую озером. План озера является связной областью и не содержит «дырок» внутри. В плане есть хотя бы одна клетка, принадлежащая озеру.

Программа должна вывести одно число – максимальное значение длины общей границы дома и озера, измеряемую в сторонах клетки. При расположении дома рядом с озером его можно передвигать, но нельзя делать повороты и отражения. Вокруг озера есть неограниченное свободное пространство, дом может располагаться с любой стороны от озера.
Числа N и M являются целыми, положительными, не превосходят 15.

Ввод	Вывод	Примечание
5 6 ...... .HHHH. .HHHH. .HHHH. ...... ..WWW. ..WWW. ..WWW. ..WWW. ..WWW.	3	. . . . W W W H H H H W W W H H H H W W W H H H H W W W . . . . W W W
5 7 ...HHH. .H...H. .H.HHH. .H.H... .HHH... ....... ..WWWWW WWW...W W.W...W ..W....	11

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

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

*Сталкер#33469

В городе Н при невыясненных обстоятельствах территория одного из заводов превратилась в аномальную зону. Все подъезды к территории были перекрыты, а сама она получила название промзоны. В промзоне находятся N зданий, некоторые из них соединены дорогами. По любой дороге можно перемещаться в обоих направлениях.
Начинающий сталкер получил задание добраться до склада в промзоне. Он нашел в электронном архиве несколько карт территории промзоны. Так как карты составлялись разными людьми, то на каждой из них есть информация только о некоторых дорогах промзоны. Одна и та же дорога может присутствовать на нескольких картах.
В пути сталкер может загружать из архива на мобильный телефон по одной карте. При загрузке новой карты предыдущая в памяти телефона не сохраняется. Сталкер может перемещаться лишь по дорогам, отмеченным на карте, загруженной на данный момент. Каждая загрузка карты стоит 1 рубль. Для минимизации расходов сталкеру нужно выбрать такой маршрут, чтобы как можно меньшее число раз загружать карты. Сталкер может загружать одну и ту же карту несколько раз, при этом придется заплатить за каждую загрузку. Изначально в памяти мобильного телефона нет никакой карты.

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

Входные данные:
- в первой строке входных данных содержатся два натуральных числа N и K (\(2 <= N <= 2000\); \(1 <= K <= 2000\)) — количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад — в здании с номером N.
- в последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число r_i — количество дорог, обозначенных на i-ой карте;
- затем идут r_i строк, содержащие по два натуральных числа a и b (\(1 <= a\), \(b <= N\); \(a ? b\)), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (\(r_1 + r_2 + … + r_K <= 300 000\)).

Выходные данные: выведите одно число — минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число –1.

Примеры

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

0-1 BFS Дек

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

Проложи дорогу#33467

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

Формат входных данных
Первая строка содержит число N – количество городов в стране (\(1\leq N\leq10^4\)). Каждая из последующих N строк содержит по два целых числа, xi и yi – координаты соответствующего города (\(|x|, |y| \leq 10^6\) ). Далее содержится число M – количество особых пар городов (\(0\leq M \leq min(10^4, N(N-1)/2)\). Далее в M строках содержится описание особых дорог, каждое состоит из трех целых чисел: u, v – пара различных городов, между которыми проходит особая дорога, и w – стоимости постройки соответствующей дороги (\(1 \leq u,v \leq N, 0 \leq w \leq 10^6\)). В последней строке содержатся номера городов А и Б (от 1 до N).

Формат выходных данных
Выведите одно число – искомую минимальную длину. Ваш ответ должен отличаться от правильного не более чем на 10⁻⁵.

Алгоритм Дейкстры

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

Анализ файла - 07#33407

В первой строке текстового файла указано количество строк в файле, содержащих различные символы английского алфавита (от A до Z). Определите количество строк, в которых количество символов, обозначающих гласную букву английского алфавита больше, чем количество символов, обозначающих согласную букву. В ответе укажите одно число.

Для выполнения этого задания следует написать программу.

Файл

task24-2.txt

ЕГЭ_информатика ЕГЭ-24. Обработка символьных строк Обработка текста

1 200труднаяВойти и решать

Type Printer#33314

Вам нужно напечатать N слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:

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

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

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

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

Ваша программа должна считать следующие входные данные:

На первой строке число N (1<=N<=25000).

На следующих N строках слова, состоящие из маленьких букв латинского алфавита. Длина каждого слова не превышает 20. Все слова различны.

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

Ваша программа должна вывести следующие данные:

На первой строке M — число операций.

На следующих M строках по одному символу — описание операций. Каждая операция описывается одним символом:

Добавление символа обозначается собственно символом.

Удаление символа обозначается символом «-» (минус, ASCII-код 45).

Операция «напечатать текущее слово» обозначается символом «P» (заглавная латинская буква P).

Ввод	Вывод
3 print the poem	20 t h e P - - - p o e m P - - - r i n t P

Бор Обход в глубину

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

Шоколадка - революция#33300

Петя получил золотую медаль на IOI, за что от правительства ему положена благодарность в виде шоколадки. На данный момент имеется N видов шоколадок, которые производит государственная шоколадная фабрика. У каждой шоколадки есть стоимость. Кроме того, у каждого вида, кроме шоколадки "Юлька", есть вид-прародитель. Известно, что прародителем может быть только шоколадка, которая была выпушена хронологически раньше. Исторически самый первый вид - "Юлька". Чиновник и Петя выбирают шоколадку ему в подарок. При этом цель первого - сэкономить, второго - получить настолько дорогую шоколадку, насколько это возможно. Начинается выбор с "Юльки". Петя за ход либо берет текущую шоколадку, либо меняет свой выбор на шоколадку-потомка (если это возможно). Чиновнику же кажется, что позже выпущенные виды хуже и дешевле, поэтому он меняет выбор на шоколадку-потомка (если это возможно), либо покупает Пете шоколадку (если потомков нет). Они ходят по очереди, Петя - первый. Определите, на шоколадку какой стоимости может претендовать Петя.

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

Сначала вводится число 0 < N <= 200000 - количество видов. "Юлька" имеет номер 1. Далее идут N строк с парами чисел 0 <= P_i <= N - номер сорта-предка (для шоколадки "Юлька" указан 0, у остальных P_i > 0) и 0 < Ci <= 1000000000 - стоимость i-го сорта.

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

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

Ввод	Вывод
8 0 4 5 3 1 2 5 1 1 5 4 8 3 6 3 7	6

Простые игры

1 300средняяВойти и решать

Охота на Снарка#33296

В начальный момент времени Снарк находится в точке прямой с целой неотрицательной координатой X. За ход он может оказаться в любой точке с целой координатой Y при условии, что |X-Y| <= S. Кроме того, Снарк не любит булочки, поэтому он никогда не прыгнет в клетку, где одна из этих противных штук лежит. Булочник не хочет, чтобы Снарк попал домой. После каждого хода Снарка Булочник может положить булочку в любую точку прямой при условии, что это не начало координат (дом Снарка) и в этой клетке нет Снарка. Определите, сможет ли Булочник помешать Снарку оказаться дома. Изначально в некоторых клетках лежат булочки.

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

В первой строке задаются целые числа 0 <= X < 10000, 0 < S <= 100 и 0 <= N < max(X-1, 0) - количество булочек, которые уже лежат на прямой. Далее идут N различных чисел 0 < b_i < X - координаты точек, где лежит гадость.

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

Выведите "YES", если Булочник сможет реализовать свои грязные планы, "NO" - если при любых действиях врага Снарк сможет припрыгать домой.

Ввод	Вывод
1 1 0	NO
10 3 3 7 8 9	YES

Простые игры

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

*Упорядочивания#33257

Сегодня у Кэрол выходной. Но даже в этот прекрасный весенний день она не отдыхает, а тренируется и готовится к сражениям со скруллами. Одним из важных навыков является умение быстро ориентироваться в незнакомых местах. Для того, чтобы отточить это умение, Кэрол пригласила своего наставника Йон-Рогга.

Кэрол и Йон-Рогг будут играть в следующую игру. Сначала Йон-Рогг нарисует на бумаге карту убежища скруллов. Карта представляет из себя n помещений, пронумерованных от 1 до n. Некоторые пары помещений соединены двусторонними переходами. Убежище устроено так, что от любого помещения до любого другого можно добраться, перемещаясь по коридорам. Для того, чтобы игра не была слишком сложной, Йон-Рогг нарисует ровно n − 1 переход между помещениями. Иными словами, карта убежища представляет собой дерево.

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

После того, как Йон-Рогг нарисует на бумаге карту убежища, он также для каждого перехода отметит, в каком направлении по нему перемещаются роботы. Иными словами, Йон-Рогг ориентирует ребра нарисованного дерева.

Чтобы структурировать карту убежища, Кэрол должна составить список, состоящий из всех номеров помещений в некотором порядке. При этом должно выполняться следующее условие: в любом переходе роботы перемещаются от помещения, которое идет в списке раньше, к помещению, которое идет с писке позже. Более формально, Кэрол должна составить такую перестановку номеров помещений p₁p₂ . . . p_n, для которой верно, что если роботы могут перемещаться по переходу от помещения pi к помещению p_j , то i < j.

Пока Кэрол бьется над своим заданием, Йон-Роггу стало интересно, сколько всего решений существует у этой задачи. Иными словами, Йон-Роггу интересно, сколько перестановок удовлетворяют условию, описанному выше. Помогите ему узнать это. Так как ответ может быть очень большим, Йон-Рогг попросил вас сообщить лишь его остаток от деления на 998 244 353.

Входные данные: Первая строка входных данных содержит единственное целое число n — количество помещений в убежище, нарисованном Йон-Роггом (1 <= n <= 3 000).

Каждая из следующих n − 1 строк содержит два целых числа a, b — номера помещений, соединенных очередным коридором (1 <= a, b <= n). Роботы перемещаются по коридору в направлении от помещения a к помещению b.

Гарантируется, что убежище представляет собой дерево, то есть от любого помещения можно добраться до любого другого, двигаясь по переходам (возможно, в направлении, противоположном направлению движения роботов в этом переходе).

Выходные данные: Выведите остаток от деления на 998 244 353 количества различных перестановок p₁p₂ . . . p_n, для которых верно, что если роботы перемещаются по переходу от помещения p_i к помещению p_j , то i < j.

Примеры

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

Замечание

В первом тесте из примера Кэрол может выписать две перестановки: {1, 2, 3} или {1, 3, 2}.

Во втором тесте Кэрол может выписать три перестановки: {2, 3, 1, 4}, {2, 3, 4, 1} или {2, 4, 3, 1}.

Топологическая сортировка

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

Все кратчайшие маршруты#33229

Учёный-ботаник получил карту дорог страны Лимония. Чтобы составить план исследования этой страны, ему требуется найти кратчайшие расстояния между каждой парой городов этой страны (можно ехать только по проложенным дорогам). Помогите учёному – напишите программу, которая решает эту задачу.

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

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

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

Программа должна вывести все кратчайшие маршруты между всеми городами в следующем формате:

(1->3): 1 2 3 (23)

Сначала выводятся номера начального и конечного города (в скобках), затем – последовательность номеров городов, составляющая оптимальный маршрут, затем (в скобках) длина этого маршрута. Если между какими-то городами нет дороги, нужно вывести число 0.

Ввод	Вывод
4 0 0 0 0 0 0 2 1 0 2 0 4 0 1 4 0	(1,2): 0 (1,3): 0 (1,4): 0 (2,3): 2 3 (2) (2,4): 2 4 (1) (3,4): 3 2 4 (3)

Алгоритм Флойда кратчайшие пути

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

Обработка больших данных#33128

В научной лаборатории разрабатывается новая архитектура суперкомпьютера,

позволяющая эффективно обрабатывать большие объемы данных.

Суперкомпьютер имеет 2^k ячеек памяти, пронумерованных от 0 до 2^{k– 1}. Отрезком

[L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R,

включительно.

Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является

корректным, если его длина (R – L + 1) равна 2i для некоторого i, а число L делится на 2i.

Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются

отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,

6] и [7, 7].

Ключевой операцией в новой архитектуре является операция STORE, которая за одно

действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного

отрезка.

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

на суперкомпьютере программу обработки данных, но перед её запуском необходимо

инициализировать память определенным образом. А именно: первые с1 ячеек памяти

необходимо заполнить значениями v1, следующие c2 ячеек — значениями v2, и так далее,

последние cn ячеек памяти необходимо заполнить значениями vn, где 1 ≤ vi ≤ m.

Ученым надо выяснить, какое минимальное количество операций STORE необходимо

выполнить, чтобы проинициализировать память требуемым образом.

Например, если k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, то итоговое

содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для

инициализации памяти достаточно трех операций STORE:

- STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;

- STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];

- STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],

как и требуется.

Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не

является корректным отрезком памяти.

Требуется написать программу, которая по заданному содержимому памяти

определяет минимальное количество операций STORE, которое необходимо выполнить для

инициализации памяти заданным образом.

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

Первая строка входных данных содержит три целых числа: k, n и m (0 ≤ k ≤ 30,1 ≤ n ≤ 10

5, 1 ≤ m ≤ 10⁹).

Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа ci

и vi (1 ≤ ci ≤ 2^k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2^k).

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

Требуется вывести одно целое число – минимальное количество операций STORE,

которое необходимо выполнить для инициализации памяти заданным образом.

Ввод	Вывод
3 3 2 1 1 2 2 5 1	3

Динамическое программирование Множества Структуры данных

✓ 0✗ 101 300средняяВойти и решать

Вася с пультом#33116

Однажды, Вася взял без спроса у бабушки пульт от телевизора и выбежал во двор с прямого хода. Радиус двора - R метров. Прямой путь от парадного выхода до калитки - хорда AB, являющаяся диаметром этой окружности. Добежав до центра окружности, он увидел деда выскочившего ему наперерез. Василий принял решение сбежать через дырку в заборе. Но чтобы не портить бабушкины цветы и тем самым не добить её своим поступком, он подумал что лучше всего бежать по дорожкам. На картинке они обозначены.

Близжайщая тропинка ведущая до дырки - AC, к ней от центра ведёт дорожка ОН.

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

1 < R < AC < 10^18

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

10 16

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

24.000

(с) Медведев Д., 2018

Вычисление по заданной формуле Элементарная геометрия

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