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

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

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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.

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

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

Примеры

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

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

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

Количество элементов в дереве#44646

Подсчитайте количество элементов в получившемся дереве и выведите это количество.

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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.

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

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

Примеры

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

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

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

Высота дерева#44645

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

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

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

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

Выведите единственное число – высоту получившегося дерева.

Пример соответствует следующему дереву:

Примеры

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

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

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

Сортировка строк#44617

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

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	4 5 21 22 23 24 25 26 12 18 29 33 11 37 31 14 39 16 17 18 5 20 1	26 12 18 29 33 21 22 23 24 25 16 17 18 5 20 11 37 31 14 39

Алгоритмы сортировки Двумерные массивы

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

Автомобиль "Пантера"#44581

Однажды утром Глеб с ужасом осознал, что проспал, а пары в «Высшем университете» начинаются уже скоро. Опоздать было бы не так страшно, если бы он их и не вёл. К счастью, автомобиль Глеба «Пантера» довольно мощный: для упрощения будем считать, что за одну секунду он может сначала или увеличить скорость на 1, или уменьшить скорость на 1, или не менять её, а после этого его автомобиль проезжает x метров, где x - его текущая скорость в метрах в секунду. Потом он снова принимает решение об изменении скорости. Начальная скорость автомобиля преподавателя в момент, когда он только выезжает из дома, равна нулю. Путь до университета от его дома не близкий: нужно проехать d метров.

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

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

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

Вводится одно целое число - d (1 <= d <= 10¹⁸), расстояние до университета.

Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

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

Примечание

В первом тесте из условия Глебу выгодно действовать следующим образом:

Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
Не менять скорость, проехать один метр; скорость 1 м/с, проехал 2 метра от дома.
Уменьшить скорость на один; скорость 0 м/с, проехал 2 метра от дома.

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

Во втором тесте из условия Глебу выгодно действовать, например, так:

Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
Увеличить скорость на один, проехать два метра; скорость 2 м/с, проехал 3 метра.
Увеличить скорость на один, проехать три метра; скорость 3 м/с, проехал 6 метров.
Уменьшить скорость на один, проехать два метра; скорость 2 м/с, проехал 8 метров.
Уменьшить скорость на один, проехать один метр; скорость 1 м/с, проехал 9 метров.
Не менять скорость, проехать один метр; скорость 1 м/с, проехал 10 метров.
Уменьшить скорость на один; скорость 0 м/с, проехал 10 метров.

Таким образом, он потратит 7 секунд, и его конечная скорость будет равно 0 м/с.

Примеры

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

Бинарный поиск по ответу

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

Массив сумм#44508

Юля выписала на доску n последовательных натуральных чисел a, a+1, …, a+n−1 и написала под каждым из них сумму его цифр в десятичной записи, под i-м числом было выписано sum_i.

После этого Юра стёр исходные числа и оставил только их суммы цифр. От вас требуется восстановить первое число в исходной последовательности a.

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

В первой строке содержится одно целое число n (2 <= n <= 100000) - длина исходной последовательности.

В следующей строке содержатся n целых чисел sum₁, sum₂, …, sum_n (1 <= sum_i<= 90) - суммы цифр чисел исходной последовательности.

Гарантируется, что для всех тестов существует подходящее a, такое что 1 <= a <= 10¹⁸.

Выходные данные
Выведите одно число a (1 <= a <= 10¹⁸) - первое число исходной последовательности. В случае, если существует несколько подходящих a, можно вывести любое.

Примечание

В первом тестовом примере сумма цифр 1 равняется 1, сумма цифр 2 равняется 2, сумма цифр 3 равняется 3, что соотносится с массивом sum, поэтому a = 1 подходит под условие задачи.

Во втором тестовом примере сумма цифр 77 равняется 14, сумма цифр 78 равняется 15, сумма цифр 79 равняется 16, сумма цифр 80 равняется 8, сумма цифр 81 равняется 9, что соотносится с массивом sum, поэтому a = 77 подходит под условие задачи.

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3	1
2	5 14 15 16 8 9	77

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

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

Автомобиль "Пантера" - 2#44505

Глеб, обеспокоенный за знания своих студентов, хочет попасть в университет как можно раньше, чтобы успеть подготовиться к проведению лекции. К сожалению, у проезда на парковку университета установлен датчик движения: если скорость проезжающего транспортного средства будет превышать s, то администрация университета выпишет нарушителю дисциплинарное взыскание. Конечно, Глеб не хочет его получить, поэтому при въезде в университет, когда автомобиль проехал все d метров его скорость x должна быть не больше s.

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

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

В двух строках заданы два целых числа - d, s (1 <= d <= 10¹⁸, 0 <= s <= 10¹⁸), расстояние до университета и ограничение на конечную скорость.

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

Примечание

В первом тесте из условия Глебу выгодно действовать следующим образом:

Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
Не менять скорость, проехать один метр; скорость 1 м/с, проехал 2 метра.

Таким образом, он потратит 2 секунды, и его конечная скорость будет равно 1 м/с, что не превышает s.

Во втором тесте из условия Глебу выгодно действовать, например, так:

Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
Увеличить скорость на один, проехать два метра; скорость 2 м/с, проехал 3 метра.
Увеличить скорость на один, проехать три метра; скорость 3 м/с, проехал 6 метров.
Уменьшить скорость на один, проехать два метра; скорость 2 м/с, проехал 8 метров.
Уменьшить скорость на один, проехать один метр; скорость 1 м/с, проехал 9 метров.
Не менять скорость, проехать один метр; скорость 1 м/с, проехал 10 метров.
Уменьшить скорость на один; скорость 0 м/с, проехал 10 метров.

Таким образом, он потратит 7 секунд, и его конечная скорость будет равно 0 м/с, что не превышает s.

Примеры

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

Бинарный поиск по ответу

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

Самолёт#44309

В салоне самолёта в одном ряду находится n кресел. Для удобства прохода и обсуживания пассажиров вдоль салона делается один или два прохода. Например, в салоне самолёта Sukhoi Superjet 100 в ряду 5 кресел и один проход (с одной стороны прохода два кресла, с другой стороны — три), а в самых больших современных самолётах — 10 кресел и два прохода (по три кресла по бокам салона у иллюминаторов и четыре кресла между проходами).

Предположим, что в будущем появятся самолёты большего размера, поэтому количество проходов придётся увеличить. Определите, какое минимальное число проходов должно быть в самолёте, в одном ряду салона которого находится n кресел. По бокам салона (у иллюминаторов) может находиться не более 3 кресел, а между двумя проходами — не более 4 кресел. При этом в салоне должен
быть хотя бы один проход.
Входные данные
Программа получает на вход одно натуральное число n, не превосходящее 2 · 10⁹ , — количество кресел в одном ряду салона.
Выходные данные
Программа должна вывести единственное целое число — минимальное количество проходов, которое должно быть в салоне самолёта с n креслами в одном ряду.

Примеры

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

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

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

Заказ в магазине#44273

Решив запастись ручками на весь новый учебный год, Игорь подсчитал, что ему нужно M ручек.
В его любимом интернет-магазине есть удобная функция — он может сразу добавить в заказ упаковку из любого числа ручек от 1 до N. Правда, оказалось, что нельзя добавить в заказ две упаковки одного размера. Например, если Игорю нужно купить M = 12 ручек, а максимальное число ручек в упаковке N = 10, то Игорь может добавить в заказ упаковку из 7 ручек и упаковку из 5 ручек, но не сможет добавить две упаковки из 6 ручек.
Сформируйте заказ на M ручек, используя минимальное число различных упаковок.

Входные данные
Первая строка входных данных содержит число N — максимальный размер одной упаковки (1 ≤ N ≤ 10⁹ ). Вторая строка входных данных содержит целое число M — необходимое количество ручек в заказе (1 ≤ M ≤ 10⁹ ).

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

Примеры

№	Входные данные	Выходные данные
1	10 12	5 7
2	2 5	0

Вывод формулы Жадный алгоритм

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

Схема дорог#44035

Дед Мороз составляет схему дорог, по которой можно будет кратчайшим образом посетить N городов. Для простоты он пронумеровал все города номерами 1,..., N. Города соединены M количеством дорог. I-я дорога (1<=i<=M) соединяет город A_i и город B_i. Прежде чем построить оптимальный маршрут Дед Мороз хочет знать с какими городами связан каждый город. Помогите Деду Морозу.
Выведите N строк следующим образом.

Пусть d_i - количество городов, непосредственно связанных с городом i (1<=i<=N), и этими городами будут города a_i,1, ..., a_i,di,перечисленных в порядке возрастания.
I-я строка (1<=i<=N) должна содержать d_i+1 целое число: d_i, a_i,1,...,a_i,di в указанном порядке, разделенные пробелами.

Входные данные
Первая строка входных данных содержит два целых числа, разделенных одним пробелом N и M (2 <= N <= 10⁵, 1 <= M <= 10⁵). Далее следует M строк, каждая из которых содержит 2 числа A_i и B_i(1 <= A_i < B_i <= N, 1 <= i <= M).
Если i≠j, то (A_i, B_i)≠(A_j, B_j). Все числа целые.

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

Примеры

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

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

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

Добраться до игрушек#44034

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

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

Дед Мороз знает, что вход в фабрику сегодня расположен у двери с числом X. Также известно, что в коридоре, рядом с числом Y находится дверь, перекрывающая проход по коридору. Чтобы ее открыть необходимо взять ключ, который располагается на стене на полке в коридоре рядом с числом Z.

Определите сможет ли Дед Мороз сам добраться до двери к игрушкам. Если сможет, определите минимальное расстояние, которое необходимо будет пройти Деду Морозу. Если не сможет, то выведите -1.

Входные данные
Программа получает на вход строку, содержащую 3 различных ненулевых числа: X, Y, Z (-10³ <= X, Y, Z <= 10³).

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

Примеры

№	Входные данные	Выходные данные
1	10 -10 1	10
2	20 10 -10	40
3	100 1 1000	-1

Простые задачи на перебор Условный оператор

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

Эффективные сборы#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—Войти и решать

Громозека и валерьянка#43474

Громозека очень любит валерьянку. На его родной планете Чумароза можно купить за k чумриков (местная валюта) первую упаковку валерьянки, за 2·k чумриков - вторую и так далее (иными словами, за i-ю упаковку надо заплатить i·k чумриков). Громозека хочет купить w упаковок валерьянки. У него есть n чумриков. Сколько чумриков ему придется взять в кредит в чумарозском банке, чтобы купить w упаковок валерьянки?

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

В первой строке записано три положительных целых числа k, n, w (1 <= k, w <= 1000, 0 <= n <= 10⁹), стоимость первой упаковки, изначальное количество чумарозиков у Громозеки и количество упаковок валерьянки, которые он хочет купить.

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

Выведите единственное целое число - количество чумарозиков, которое Громозеке необходимо взять в кредит в банке. Если брать кредит не надо, выведите 0.

Примеры

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

Задача на реализацию Простые задачи на перебор Цикл for Циклы

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

Секретная последовательность#43349

Алиса оставила для своего отца профессора Селезнева секретную последовательность a[1..n]. Чтобы ее не прятать, она решила написать ее на самом видном месте, но в другом порядке следования чисел. Профессор Селезнев знает, что Алиса переписала секретную последовательность в следующем виде:

первым числом слева записано число a₁;
первым числом справа записано число a₂;
вторым числом слева (после a₁) записано число a₃;
вторым числом справа (то есть перед числом a₂) записано число a₄;
все остальные числа записаны аналогичным образом.

То есть, если бы секретная последовательность была a = [1, 2, 3, 4, 5, 6], то профессор бы увидел следующую последовательность [1, 3, 5, 6, 4, 2]. Профессор Селезнев очень торопился и успел только сохранить в компьютер последовательность, которую увидел. Напишите программу, которая покажет профессору исходную секретную последовательность.

Входные данные
Первая строка содержит размер последовательности n (1 <= n <= 300), записанной Алисой для своего отца. Вторая строка содержит n чисел a_i (1 <= a_i <= 10⁹) - саму последовательность.

Выходные данные
Выведите исходную последовательность, которую Алиса выписывала для отца.

Примеры

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

"Два указателя"Задача на реализацию Одномерные массивы

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

Порадомой#43137

В один осенний день чебаркульская сборная по американскому футболу возвращалась на поезде домой после дружеского матча с командой Чебоксар. Подъезжая к очередной реке, главные тренеры футболистов — Алексей Юрьевич и Михаил Леонидович — заметили, что мост через реку на их пути не выглядит слишком надёжно, и, если несколько вагонов с суммарной массой больше W тонн будут целиком находиться на нём, переправа обязательно рухнет. Вагоны, которые находятся на мосту не полностью, не учитываются в суммарной массе.
Алексей Юрьевич, как самый ответственный тренер, точно знает, сколько весит каждый из вагонов поезда: i-й вагон от начала состава имеет массу ai тонн. Михаил Леонидович же имеет идеальное зрение, а потому может сказать, что длина моста равняется длине ровно p вагонов.
Крушения допустить никак нельзя, а потому тренеры приняли волевое решение: отцепить минимальное число вагонов (возможно, все) с конца состава, чтобы поезд смог проехать опасное место. Помогите им и скажите, сколько вагонов придётся оставить до переправы.
Входные данные
В первой строке входных данных через пробел записаны три целых числа n,p и W — количество вагонов в поезде, длина моста в вагонах и максимальная нагрузка в тоннах, которую он выдерживает (1 <= n <= 10⁵, 1 <= p <=10⁵, 0 <= W <=10¹⁴).
Во второй строке через пробел записаны n целых чисел a_i — веса вагонов в порядке их следования от начала состава (1 <= a_i <= 10⁹).
Выходные данные
Выведите единственное число — минимальное количество вагонов, которое надо отцепить от хвоста поезда, чтобы тот смог безопасно проехать по мосту.

Примеры

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

Замечание
В данном тесте мост обрушится, только если на него заедут 3 и 4 вагон одновременно, а это значит, что достаточно отцепить лишь последний вагон.

Задачи на моделирование Префиксные суммы(минимумы, ...)

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

Чебаркульские спортсмены#43136

Алексей Юрьевич и Михаил Леонидович — тренера чебаркульской сборной по американскому футболу. Сегодня им нужно заполнить очень важную анкету на чемпионат мира, в которой необходимо указать всех членов команды в порядке возрастания их силы.
Для решения этой непростой задачи были собраны все игроки сборной, и каждый из спортсменов сказал несколько (возможно ноль) фраз вида: «Я сильнее, чем игрок k» (k может отличаться от высказывания к высказыванию, ни один спортсмен не говорил одинаковых фраз). Когда опрос был окончен, тренера поняли, что теперь могут однозначно упорядочить спортсменов по силе, соответствуя всем высказываниям.
Сразу после того, как Алексей Юрьевич и Михаил Леонидович написали ответ организаторам олимпиады, они задумались, а что было бы, если бы футболисты отвечали иначе? Ведь далеко не во всех случаях можно восстановить единственно возможный порядок игроков.
Теперь им интересно, сколько наборов ответов спортсменов однозначно задают их порядок? Так как это число может быть слишком большим, они просят найти лишь его остаток от деления на 10⁹+7.
Входные данные
Во входных данных записано единственное число n — количество спортсменов в сборной (1 <= n <= 10⁵) .
Выходные данные
Выведите единственное число — количество наборов ответов спортсменов, однозначно позволяющих упорядочить их по силе.

Примеры

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

Замечание
В данном тесте вариантов ответов всего 2: первый сказал, что сильнее второго, второй не сказал ничего, или первый не сказал ничего и второй сказал, что он сильнее первого.

Вывод формулы Комбинаторика

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

Засада на переговорах#43134

Саша Белый и его бригада приехали на переговоры в Сатку. Однако беседа обещает быть жаркой, поэтому Саша хочет спрятать свою братву в засаду. Переговоры будут проходить на квадратном поле размером 2N×2N, и в каждую клетку этого поля Белый может посадить от 0 до 2 братанов. Так как Саша не любит повторяться, то суммарное количество братанов в каждом столбце и в каждой строке квадратного поля должно быть различным.
Как вы знаете, из-за определённых обстоятельств Белый не закончил вуз, поэтому не силён в программировании, и вам нужно срочно помочь ему.
Подскажите Белому, сможет ли он расставить братву с заданным условием, и если сможет, то приведите пример расстановки.
Входные данные
Во входных данных записано единственное целое число N такое, что 2N — длина стороны поля (1 <= N <= 300).
Выходные данные
На первой строке выведите YES, если существует расстановка, что суммарное количество братанов в каждом столбце и в каждой строке квадратного поля различно, и NO в противном случае. Если расстановка существует, то на следующих 2N строках выведите пример. Если существует несколько подходящих расстановок, то можете вывести любую из них.

Примеры

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

Задача на реализацию Конструктив

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

Очередные операции над массивом#43128

Был обычный будний вечер в Магнитогорске. Фил и Космос возвращались на машине домой после тяжёлой рабочей смены. Тут Космос вспомнил, что Белый дал ему задание, которое он благополучно забыл выполнить. Чтобы уберечь Космоса от гнева Саши Белого, помогите ему выполнить задание.
Даны n целых чисел a₁,a₂,...,a_n. Требуется сделать наибольший общий делитель (НОД) всех чисел массива равным 1. За одну операцию можно сделать следующее:
• Выбрать произвольный индекс в массиве 1 <= i <= n;
• Сделать a_i = gcd(a_i,i). Стоимость такой операции равна n − i + 1.
Требуется найти минимальную суммарную стоимость операций, которые нужно будет сделать, чтобы НОД чисел массива стал равен 1.
Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число t (1 <= t <= 5000) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число n (1 <= n <= 20) — длину массива.
Вторая строка каждого набора входных данных содержит n целых чисел a₁,a₂,...,a_n (1 <= a_i <= 10⁹) — элементы массива.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальную суммарную стоимость операций, которые нужно будет сделать, чтобы НОД чисел массива стал равен 1.

Примеры

№	Входные данные	Выходные данные
1	7 1 1 1 2 2 2 4 3 3 6 9 4 5 10 15 20 5 120 60 80 40 80 6 150 90 180 120 60 30	0 1 2 2 1 3 3

Замечание
В первом наборе входных данных НОД всего массива уже равен 1, поэтому операции применять не нужно.
Во втором наборе входных данных выберем i = 1. После этой операции a1 = gcd(2,1) = 1. Стоимость этой операции была равна 1.
В третьем наборе входных данных нужно будет выбрать i = 1, после этого массив a будет равен [1,4]. НОД этого массива равен 1, а суммарная стоимость равна 2.
В четвертом наборе входных данных нужно выбрать i = 2, после этого массив a будет равен [3,2,9]. НОД этого массива равен 1, а суммарная стоимость равна 2.
В шестом наборе входных данных можно выбрать i = 3, после этого массив a будет равен [120,60,1,40,80]. НОД этого массива равен 1, а суммарная стоимость равна 3.

НОД и алгоритм Евклида

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

Длинный плакат#42975

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

Входные данные
В первой строке входных данных записано целое число N, записанное на изначальном длинном плакате. Гарантируется, что в N не менее двух и не более 200 000 цифр (10 ≤ N < 10^{200 000}).
Во второй строке содержится целое число K — количество цифр, которые необходимо вырезать из плаката. Гарантируется, что K не меньше одного и строго меньше количества цифр числа N (1 ≤ K, 10^K ≤ N).
Выходные данные
Выведите максимальное число, которое может получиться на плакате после его укорачивания

Примеры

№	Входные данные	Выходные данные
1	2023 1	223

Замечание
В примере из условия на плакате записано число 2023, из него нужно вырезать одну цифру.
Максимально число, которое можно при этом получить, равно 223.

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

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

Лес#42971

Миша заблудился в лесу и пытается выйти из него. Он проходит A шагов на север, затем B шагов на восток, затем C шагов на юг, D шагов на запад, после чего повторяет свои действия (снова A шагов на север, B шагов на восток, C шагов на юг, D шагов на запад и т.д.).
Оказалось, что для того, чтобы выйти из леса из его первоначальной точки, ему нужно было пройти ровно K шагов в любом из четырёх направлений, то есть первоначально Миша находится в центре квадрата со стороной 2K шагов. Определите, сколько шагов Миша сделает, прежде чем выйдет из леса (впервые окажется на границе леса).

Входные данные
Первые четыре строки входных данных содержат по одному целому положительному числу A, B, C, D — количество шагов, которое Миша делает на север, восток, юг, запад. Пятая строка входных данных содержит целое число K — расстояние от начального расположения Миши до четырёх сторон квадрата (границ леса). Все входные числа не превосходят 10⁹.

Выходные данные
Программа должна вывести одно целое число — количество шагов, которое Миша сделает до выхода из леса. Гарантируется, что входные данные таковы, что Миша когда-нибудь выйдет из леса.
Обратите внимание, что значение ответа может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).

Примеры

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

Замечание
На рисунке изображён пример из условия. Миша делает 1 шаг на север (вверх), 1 шаг на восток (вправо), 2 шага на юг (вниз), 3 шага на запад (влево). От начального расположения Миши до стороны квадрата — 3 шага. Первоначальное расположение Миши и точка выхода из леса обозначены синими кругами. Путь Миши обозначен жёлтой линией. Миша пройдёт 13 шагов, прежде чем впервые окажется на границе леса.

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

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