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

Ральф любит пончики#44712

Громила Ральф вот уже 30 лет живёт в игровом автомате, и вы его можете увидеть на экране того самого автомата.
Сегодня Ральф гуляет по экрану, на котором отображается прямоугольное изображение, разбитое на N x N клеток. В каждой клетке находится тарелка с его любимыми блинчиками (на всех тарелках разное количество блинчиков). Ральф начинает перемещаться с левой нижней клетки прямоугольника. Съев все блинчики в текущей клетке, он перемещается на одну клетку вправо или на одну клетку вверх, всегда выбирая ту из клеток, где больше блинчиков в тарелке (за пределами прямоугольника тарелок с блинчиками нет). В конце концов Ральф приходит в правую верхнюю клетку. Вам же предстоит определить, сколко всего блинчиков съел Ральф пока путешествовал по экрану. Блинчики в начальной и конечной клетках Ральф тоже съел с большим удовольствием.

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

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

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

Выведите одно число - количество блинчиков, которое съест Ральф, добравшись до правой верхней клетки.

Примеры

№	Входные данные	Выходные данные
1	2 37 82 23 52	157

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

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

Новый вопрос#44601

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

—Войти и решать

Эффективные сборы#43870

Лука часто ездит на сборы по программированию. Сборы длятся n дней. Лука фиксирует количество решенных задач в каждый день сборов. Лука считает сборы «эффективными», если только один непрерывный не нулевой промежуток дней (от l до r), когда выполнялись следующие условия по числу решенных задач:

1 <= l <= r <= n;
a_l = a_l+1 = a_l+2 =…=a_r;
l = 1 или a_l-1 > a_l;
r = n или a_r < a_r+1;

Примеры

Пусть массив A хранит информацию о решении задач за каждый день сборов, тогда:

1) массив A = [5, 3, 3, 2, 3, 3, 4] описывает «эффективные», по мнению Луки, сборы (промежуток в 1 день l = r = 4 удовлетворяет условию);

2) массив А = [2, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8] также описывает «эффективные» сборы (промежут l = 1, r = 3 удовлетворяет условию);

3) массив А = [1, 2, 3, 4, 3, 2, 1] описывает не «эффективные» сборы (есть два промежутка удовлетворяющих условию l = r = 1 и l = r = 7).

Лука только что вернулся с очередных сборов по программированию и рассказал вам сколько задач ежедневно он решал. Определите, являются ли сборы, с которых вернулся Лука «эффективными» по его же мнению.

Входные данные
Первая строка содержит одно целое число n (1 <= n <= 2·10⁵) — длину массива. Вторая строка n целых чисел a_i (1 <= a_i<= 10⁹) — количество решенных Лукой задач в i-й день .

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

Примеры

№	Входные данные	Выходные данные
1	`7` `5 3 3 2 3 3 4`	YES
2	`11 2 2 2 3 4 4 5 6 7 7 8`	YES
3	`7 1 2 3 4 3 2 1`	NO

"Два указателя"

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

K-mex#43131

Вы думали, что сможете спокойно выехать из Озёрска, погостив у друга? Конечно же, нет. Полицейский опять остановил вас и снова просит решить задачу, чтобы удостовериться, что вы можете выехать из города. Придётся вам решить очередную задачу.
Изначально у вас множество, в котором есть единственный элемент — это 0. Вам нужно будет поддерживать q запросов следующего вида:
•   + x — добавить число x в множество. Гарантируется, что раньше его там не было,
•   - x — удалить число x из множества. Гарантируется, что это число там есть,
•   ? k — найти k − mex множества.
В нашей задаче мы считаем, что k − mex множества — это наименьшее целое неотрицательное число x, которое делится на k и которого нет в множестве.
Входные данные
В первой строке находится целое число q (1 <= q <= 2 · 10⁵) — количество запросов.
В следующих q строках находятся описания запросов. Если это запрос добавления, то в формате
+ x (1 <= x <= 10¹⁸), если запрос удаления, то - x (1 <= x <= 10¹⁸), если же запрос поиска, то ? k (1 <= k <= 10¹⁸). Гарантируется, что будет хотя бы один запрос типа ?.

Выходные данные
Для каждого запроса типа ? выведите k − mex множества.

Примеры

№	Входные данные	Выходные данные
1	18 + 1 + 2 ? 1 + 4 ? 2 + 6 ? 3 + 7 + 8 ? 1 ? 2 + 5 ? 1 + 100000000 ? 100000000 - 4 ? 1 ? 2	3 6 3 3 10 3 200000000 3 4

Замечание
После первого и второго запроса во множестве будут элементы 0,1,2. Наименьшее неотрицательное число, которое не делится на 1 и которого нет в множества, равно 3.
После четвертого запроса во множестве будут элементы 0,1,2,4. Наименьшее неотрицательное число, которое не делится на 2 и которого нет в множества, равно 6

реализация Хеш

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

Лети, лети, лепесток...#43127

Лети, лети, лепесток,
Через запад на восток,
Через север, через юг,
Возвращайся, сделав круг.
Лишь коснёшься ты земли
Быть по-моему вели.
© Цветик-семицветик.

Во время осенних каникул, проходящих с 1 ноября по 8 ноября 2022 года, вы планируете совершить экскурсию в один из городов России. Вы даже выбрали город и даты полётов туда и обратно, но страница с результатами прогрузилась лишь частично. Вам требуется по имеющейся информации найти самый дешёвый вариант посетить выбранный город и вернуться, заодно посчитав, сколько у вас будет времени на осмотр достопримечательностей. Стоит учесть, что часто авиакомпании предоставляют скидку на перелёт туда-обратно.

Входные данные
В первой строке входного файла заданы два целых числа n и m — количество вариантов перелёта «туда» и «обратно» (1 <= n,m <= 1000). В следующих n строках описаны варианты перелёта «туда» в формате: CCxxxx yyyy.mm.dd hh:mm YYYY.MM.DD HH:MM TT:tt value, где:
•   CC — код авиакомпании, xxxx — номер рейса,
•   yyyy.mm.dd hh:mm — дата и время вылета,
•   YYYY.MM.DD HH:MM — дата и время прилёта,
•   TT:tt — время в пути, гарантируется, что время перелёта не превышает 24 часа,
•   value — целое число, стоимость перелёта (0 <= value <= 100000).
В следующих m строках описаны варианты перелёта «обратно» в том же формате. Дата вылета рейса «туда» во всех случаях как минимум на три дня раньше даты рейса «обратно».
Гарантируется, что все перелёты начинаются во время осенних каникул.
В последующих строках выписаны скидки, которые предоставляют авиакомпании за полёт тудаобратно. Каждая строка описывает одну авиакомпанию в формате: CC — код авиакомпании и value — целое число, размер скидки в процентах (0 <= value <= 100). Скидка рассчитывается с точностью до рублей, копейки отбрасываются в пользу клиента. Гарантируется, что у перечисленных компаний есть хотя бы один рейс либо «туда», либо «обратно», и что компании в данном списке не повторяются.

Выходные данные
В первой строке выведите два натуральных числа через пробел — оптимальные номера вариантов рейсов туда и обратно. Если существует несколько пар рейсов, дающих оптимальную стоимость, то нужно выбрать ту, которая позволяет провести за осмотром достопримечательностей как можно больше времени. Из всех таких пар выбрать ту, номера вариантов которой как можно раньше встретились в поисковой выдаче. Во второй строке выведите, сколько времени у вас будет на осмотр, в формате dd:hh:mm. Считается, что осмотр достопримечательностей начинается с момента прибытия и продолжается до момента отлёта.

Примеры

№	Входные данные	Выходные данные
1	2 3 DP4160 2022.11.02 07:05 2022.11.02 07:35 02:35 4000 DP4130 2022.11.02 07:45 2022.11.02 08:10 02:36 3423 S71141 2022.11.07 05:55 2022.11.07 09:55 02:40 3432 S71042 2022.11.07 05:59 2022.11.07 09:59 02:45 3422 S71243 2022.11.07 04:25 2022.11.07 09:25 02:30 3432 DP 15 S7 10	2 2 04:21:49

Замечание
Россия – большая страна с 11 часовыми поясами, поэтому, вполне возможно прилететь в город назначения раньше, чем вылетел, поскольку время отправления и прибытия самолетов всегда указывается по местному времени. Из Челябинска можно улететь в Калининград, с разницей -3 часа, или во Владивосток, с разницей +6 часов.

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

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

Последовательности длины N#40064

Сколько целых последовательностей длины N, A = (A₁,…,A_N), удовлетворяют всем приведенным ниже условиям?
1) 1 <= A_i <= M (1 <= i <= N)
2)\(\sum\limits_{i=1}^NA_i \le K\)

Входные данные
На вход подается строка, содержащая три целых числа N, M (1 <= N, M <= 50), K (N <= K <= NM).

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

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 3 4	6	(1,1) (1,2) (1,3) (2,1) (2,2) (3,1)

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

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

Социальное дистанцирование II#39389

Фермер Джон продолжает бороться за здоровье своих коров.
Имеется N cows (1≤N≤1000) коров, некоторые из которых больны. Коровы выстроены в ряд (на числовой прямой), корова i стоит на позиции x_i. ФД знает что если другая корова находится в радиусе R от больной, то она тоже заболевает. А потом заболевают коровы, которые находятся в радиусе R от этой и т.д.

К несчастью, ФД не знает точное значение R. Однако он знает, какие из его коров больны. По этим данным определите минимальное количество изначально инфицированных болезнью коров.

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

Примеры

№	Входные данные	Выходные данные
1	6 7 1 1 1 15 1 3 1 10 0 6 1	3

Сканирующая прямая

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

Одностороннее движение#38844

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

Входные данные
В первой строке входного файла находятся числа N - количество площадей в городе и М - количество улиц их соединяющих (1 <= N <= 20000, 1 <= M <= 200000). Площади имеют номера от 1 до N. В каждой из следующих M строк находится пара натуральных чисел, описывающая между какими двумя площадями проходит соответствующая улица (две площади соединяются не более чем одной улицей).

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

Примеры

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

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

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

Ананасы на Шешинеру#38832

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

Алиса хочет хочет отправить как можно большее число ананасов. Капитан Полосков решил ей помочь и с радостью согласился слетать на своем космическом корабле. Но есть один нюанс: на некоторых космических маршрутах можно дозаправить корабль, не превышающий максимально установленный вес. А заправлять корабль в пути нужно всегда, иначе он просто не долетит. Поэтому если корабль заполнить ананасами по максимуму, то, его не получится дозаправить в пути и поэтому не удастся воспользоваться самым коротким маршрутов, и придётся лететь через другие планеты. Может случиться даже так, что корабль не успеет долететь до Шешинеры вовремя, и ананасы испортятся.
Итак, сколько же ананасов можно погрузить в космический корабль, чтобы доставить груз вовремя?

Входные данные
Программа получает на вход несколько строк. В первой строке находятся числа n (1 <= n <= 500) и m - количество планет и количество космических маршрутов между планетми, соответственно. В следующих m строках записана информация о маршрутах. Каждый маршрут описывается в отдельной строке следующим образом. Сначала указаны номера планет, которые соединяются космическим маршрутом, потом время, которое тратится на перелет по этому маршруту, и, наконец, максимальный космического корабля, который можно заправить на этом маршруте. Известно, что все космические маршруты соединяют различные планеты, причем для каждой пары планет есть не более одного маршрута, непосредственно их соединяющий. Все числа разделены одним или несколькими пробелами.

Планеты нумеруются числами от 1 до n. Планеты Земля имеет номер 1, а планета Шешинера - номер n. Время перелета по маршруту задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что один ананас весит 100 грамм, а пустой корабль - 3 тонны.

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

Примеры

№	Входные данные	Выходные данные
1	3 3 1 2 10 3000220 2 3 20 3000201 1 3 1 3000099	2

Обход в ширину

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

Игрушечный лабиринт#38829

Игрушечный лабиринт представляет собой прозрачную плоскую прямоугольную коробку, внутри которой есть препятствия и перемещается шарик. Лабиринт можно наклонять влево, вправо, к себе или от себя, после каждого наклона шарик перемещается в заданном направлении до ближайшего препятствия или до стенки лабиринта, после чего останавливается. Целью игры является загнать шарик в одно из специальных отверстий – выходов. Шарик проваливается в отверстие, если оно встречается на его пути (шарик не обязан останавливаться в отверстии).

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

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

В первой строке входного файла записаны числа N и M – размеры лабиринта (целые положительные числа, не превышающие 100). Затем идет N строк по M чисел в каждой – описание лабиринта. Число 0 в описании означает свободное место, число 1 – препятствие, число 2 – отверстие.

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

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

Примеры

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

Обход в ширину

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

Подматрица - 1#38791

У Фили есть квадратная матрица A размера N×N, но она кажется ему слишком большой. Ему гораздо больше нравятся матрицы размера k×k (k<N).
Филя хочет получить матрицу нужного размера взяв некоторую подматрицу исходной матрицы.
Подматрицей k×k матрицы A в данном случае Филя считает матрицу B такую, что b_i,j=a_i+x,j+y, для всех i, j от 1 до k. Из данного определения можно заметить, что подматрица исходной матрицы задается парой чисел (x, y).
Для того, чтобы выбрать наиболее интересную для себя подматрицу, Филя хочет узнать, сколько есть способов выбрать из исходной матрицы две различные (характеризующие пары (x, y) отличаются хотя бы в одной позиции) равные подматрицы k×k. Две матрицы Q и P размера k×k считаются равными, если для любых i,j:1≤i,j≤k выполняется q_i,j=p_i,j.
Если условия равенства не выполняется, матрицы считаются неравными.

Входные данные
В первой строке входного файла содержатся два натуральных числа N и k - размеры исходной и нужной матрицы.
(1<=k<=N<=10). В следующих N строках заданы через пробел по N натуральных чисел ai,j - элементы исходной матрицы (1<=a_i,j<10).

Выходные данные
В единственной строке выходного файла выведите одно число - количество способов выбрать из исходной матрицы две различные равные подматрицы размера k×k.

Примеры

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

Словари

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

Ништячки юных программистов#38784

БЕСКОНЕЧНЫЙ ВВОД PYTHON?
На летних сборах по программированию за каждую решенную задачу давали некоторое количество фанфиков. В течении смены юные программисты могли тратить эти фанфики на покупку различных ништячков. По окончании смены у организаторов скопился большой список, каждая строка которого представляет собой запись вида Программист ништячок количество, где Программист - имя юного программиста (строка без пробелов), ништячок - наименование купленного ништячка (строка без пробелов), количество — количество приобретенных единиц ништячка.

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

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

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

Примеры

№	Входные данные	Выходные данные
1	Ivanov paper 10 Petrov pens 5 Ivanov marker 3 Ivanov paper 7 Petrov envelope 20 Ivanov envelope 5	Ivanov: envelope 5 marker 3 paper 17 Petrov: envelope 20 pens 5

Словари

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

Выпуклая оболочка#38676

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

Входные данные
Первая строка содержит количество точек N, 1≤N≤10000. Каждая из последующих N строк содержит два целых числа – координаты x_i и y_i. Все числа по модулю не превосходят 10⁴.

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

Примеры

№	Входные данные	Выходные данные
1	4 0 0 3 4 3 1 6 0	16.0000000000 12.0000000000

Многоугольники. Выпуклые оболочки

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

Карты на троих#38656

Молчун, Ворчун и Пилюлькин играют в карточную игру на троих. Правила игры следующие.
Сначала у каждого из трех игроков есть колода, состоящая из некоторого количества карт.
В колоде Пилюлькина N карт, в колоде Молчуна M карт, а в колоде Ворчуна K карт. На каждой карточке написана буква p, m или v. Порядок карт в колодах не может быть изменен. Игроки ходят по очереди. Пилюлькин ходит первым.
Если в колоде текущего игрока есть хотя бы одна карта, сбросьте верхнюю карту в колоде.
Затем следующий ход переходит к игроку, имя которого начинается с буквы на сброшенной карте.Например, если на карте написано «p», следующий ход переходит Пилюлькину.
Если колода текущего игрока пуста, игра заканчивается, и текущий игрок выигрывает игру.
Есть 3^{N + M + K} возможных вариантов раскладки начальных колод трех игроков.
Сколько из этих шаблонов приведет к победе Пилюлькина? Поскольку ответ может быть большим, выведите его по модулю 1000000007 (= 10⁹ +7).

Входные данные
На вход подается три целых числа N, M и K (2<=N, M, K <=3*10⁵).

Выходные данные
Выведите количество победных для Пилюлькина шаблонов по модулю 1000000007 (= 10⁹ +7).

Примеры

№	Входные данные	Выходные данные	Пояснение
1	1 1 1	17	Если карта Пилюлькина - p, то Пилюлькин выиграет независимо от карты Молчуна и Ворчуна. Таких вариантов 3 × 3 = 9. Если карта Пилюлькина - m, Пилюлькин выиграет только тогда, когда карта Молчуна - p, или когда карта Молчуна - v, а карта Ворчуна - p. Всего таких шаблоно 3 + 1 = 4. Если карта Пилюлькина - v, Пилюлькин выиграет только тогда, когда карта Ворчуна - p, или когда карта Ворчуна - m, а карта Ворчуна - p. Всего таких шаблонов 3 + 1 = 4. Таким образом, всего 9 + 4 + 4 = 17 шаблонов, которые приведут к победе Пилюлькина.
2	4 2 2	1227
3	1000 1000 1000	261790852

Комбинаторика

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

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

Сегодня на уроке Петя узнал про бессуффиксные коды. Множество строк называется бессуффиксным кодом, если
- Все строки в множестве различны
- Не существует такой пары различных строк, что одна строка является суффиксом другой
Строка 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 cbaa dbca caa abca baa	3 baa caa abca
4 2 aa cba aa bba	3 aa bba cba

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

Суффиксный массив

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

Следующая#38637

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

Входные данные
В первой строке входных данных содержится число N (1 <= N <= 10000). Во второй строке находится перестановка (последовательность натуральных чисел от 1 до N, разделенных пробелами).

Выходные данные
Требуется вывести искомую перестановку.

Примеры

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

Перестановки

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

Симпатичные таблицы#38633

Рассмотрим таблицу размера MxN, в клетках которой стоят целые неотрицательные числа. Скажем, что таблица является симпатичной, если для всех i сумма чисел ее i-ой строки не превышает R_i, и для всех j сумма чисел ее j-го столбца не превышает Cj.

Вам задана таблица Z размера MxN, в некоторых клетках которой уже стоят целые неотрицательные числа. Найдите симпатичную таблицу с максимальной суммой элементов такую, что она совпадает с Z на тех клетках, в которых в Z стоят числа.

Входные данные
Первая строка входных данных содержит числа M и N (1 <= M, N <= 20). Следующая строка содержит M целых неотрицательных чисел - R₁, R₂, ..., R_M. Далее идет строка, содержащая N целых неотрицательных чисел C₁, C₂, ..., C_N. Все вводимые ограничения не превышают 106. Следующие M строк содержит по N целых чисел, которые задают Z. Если на некотором месте в таблице Z отсутствует число, то на этом месте во входных данных стоит -1.

Выходные данные
Выведите найденную таблицу – M строк по N чисел. Если решения не существует, выведите единственное число -1.

Примеры

№	Входные данные	Выходные данные
1	2 2 1 10 1 10 -1 -1 -1 1	0 1 1 1

Алгоритм Форда-Фалкерсона

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

Минимизация#38629

Имеется последовательность длины N: A₁, A₂, ..., A_N. Изначально эта последовательность представляет собой перестановку 1, 2, ..., N. В этой последовательности Алиса может выполнить следующую операцию:
1) выбрать K последовательных элементов в последовательности;
2) затем заменить значение каждого выбранного элемента минимальным значением среди выбранных элементов.
Алиса хочет уравнять все элементы в этой последовательности, повторяя указанную выше операцию некоторое количество раз.
Найдите минимальное количество необходимых операций.
Можно доказать, что при ограничениях этой проблемы эта цель всегда достижима.

Входные данные
В первой строке задаются два целых числа N и K (2<=K<=N<=100000). Во второй строке задается последовательность целых чисел A₁, A₂, ..., A_N- перестановка чисел от 1 до N (каждое число в последовательности различно, 1<=A_i<=N).

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

Примеры

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

Вывод формулы

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

Симпатичные узоры возвращаются#38608

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

Теперь компания BrokenTiles является ведущим производителем симпатичных узоров в мире! Для составления плана исполнительному директору Васе по-прежнему необходимо знать, сколько клиентов могут рассчитывать на узор данных размеров.

Так как масштабы буквально мировые, N <= 10¹⁰⁰. Однако Вася не любит большие числа, поэтому просит выдать ответ по модулю P.

Входные данные
В первой строке входных данных содержатся три положительных целых числа, разделенные пробелом – N, M и P (1 <= N <= 10¹⁰⁰, 1 <= M <= 5, 1 <= P <= 10 000).

Выходные данные
Выведите количество различных симпатичных узоров N x M по модулю P .

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

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

Binary to hexadecimal#38590

Напишите программу, переводящую число из двоичной системы счисления в шестнадцатеричную

Входные данные
Программа получает на вход строку, состоящую из нулей и единиц, длина которой не превосходит 4000 символов. Первый символ строки всегда единица. Данная строка является двоичной записью некоторого числа.

Выходные данные
Необходимо записать в шестнадцатеричном виде и вывести данное число с использованием цифр 0, ..., 9 и букв A, ..., F без лидирующих нулей.

Примеры

№	Входные данные	Выходные данные
1	10100	14

Разные системы счисления

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