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

Наибольшее произведение трех чисел - поиск сортировкой#45242

Дано целое число N<=10³ и N целых чисел. необходимо найти три числа, произведение которых максимально.

Если таких троек чисел несколько, выведите любую из них.

Входные данные
В первой строке задано целое число 3 <= N <= 10³ - количество элементов в списке.
Во второй строке заданы N целых элементов списка, не превосходящих по модулю 30000.

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

Примеры

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

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

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

Распределение продуктов#45058

В Сильвертауне расположены n розничных магазинов. В логистический центр города доставили m типов товаров с различным количеством, которые необходимо распределить по всем розничным магазинам. Логистическому центру необходимо распределить все товары по магазинам, следуя следующим правилам:

- Каждому магазину распределяется не более одного типа товара, но любое его количество.
- После распределения каждому магазину предоставляется некоторое количество товаров (возможно нулевое).

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

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

Входные данные
Первая строка входных данных содержит два натуральных числа, записанных через пробел: n и m (1 <= m <= n <= 10⁵) - количество розничных магазинов и количество типов товаров. Во второй строке содержится m целых чисел q_i - количество i-го типа товара (0 <= i < 10⁵, 1 <= q_i <= 10⁵).

Выходные данные
Выведите минимально возможное x.

Примечание
В первом тестовом примере оптимальным распределением будет следующее:
- 11 продуктов типа 0 распределяются по первым четырем магазинам в следующих количествах: 2, 3, 3, 3
- 6 продуктов типа 1 распределяются по двум другим магазинам в следующих количествах: 3, 3
Максимальное количество товаров, предоставляемых в любой магазин, составляет max(2, 3, 3, 3, 3, 3) = 3.

Примеры

№	Входные данные	Выходные данные
1	6 2 11 6	3
2	7 3 15 10 10	5
3	1 1 100000	100000

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

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

Вычисление выражения с вычислениями#45000

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются целые числа, знаки арифметических операций, круглые скобки, вызовы функций ( sin , cos , abs , sqrt ) и имена переменных (только однобуквенные). Результат операции деления – вещественное число.

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

Первая строка содержит правильную запись арифметического выражения. В следующих нескольких строках записаны значения всех переменных, использованных в выражении. Каждая из этих строк имеет формат:

<имя переменной>=<значение>

Каждое имя переменной состоят из одной строчной буквы латинского алфавита.

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

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

Примеры

№	Входные данные	Выходные данные
1	cos(z+abs(sqrt(r*sin(x+4)))) r=5 z=10 x=3	0.729

Деревья

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

Вычисление выражения с функциями#44999

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются целые числа, знаки арифметических операций, круглые скобки и вызовы функций ( sin , cos , abs , sqrt ). Результат операции деления – вещественное число.

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

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

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

Примеры

№	Входные данные	Выходные данные
1	12+cos(sqrt(12+sin(2)))	11.100

Деревья

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

Вычисление простого выражения со скобками#44998

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются только целые числа, знаки арифметических операций (+-*/) и скобки произвольной вложенности. Результат операции деления – целое число.

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	(5+20)(98-34)/(58-23)	94

Деревья

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

Максимальная ширина#44960

У вашего одноклассника, которого вы не очень любите за его занудство, но уважаете за его ум, были обнаружены две строки: строка t длины m и строка s длины n. Последовательность индексов p₁, p₂, ..., pm, где 1<=p₁<p₂<…<p_m<=n, называется хорошей , если s_pi=t_i для всех i от 1 до m. Шириной последовательности называется величина \(\max_{i = 1}^{m - 1} \left(p_{i + 1} - p_i\right)\), то есть максимальная разность между соседними элементами последовательности p.

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

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

Первая строка входных данных содержит два числа n и m (2<=m<=n<=200000) - длины строк s и t соответственно.

Во второй строке входных данных задана строка s, состоящая из строчных букв английского алфавита, а в третьей строке задана строка t, состоящая из строчных букв английского алфавита.

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

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

Выведите одно число - максимальную ширину хорошей последовательности.

Примечание

В первом примере из условия существуют две хорошие последовательности с шириной 3: это {1,2,5} и {1,4,5}.

Во втором примере из условия хорошая последовательность максимальной ширины — это {1,5}.

В третьем примере из условия есть лишь одна хорошая последовательность — это {1,2,3,4,5}.

В четвёртом примере из условия есть лишь одна хорошая последовательность — это {1,2}.

Примеры

№	Входные данные	Выходные данные
1	5 3 abbbc abc	3
2	5 2 aaaaa aa	4
3	5 5 abcdf abcdf	1
4	2 2 ab ab	1

Алгоритмы на строках реализация

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

MEX(A)#44939

Определим функцию mex следующим образом: mex(A) — это минимальное положительное целое число, которое отсутствует в множестве A.

Например, mex множества {1, 2, 3, 5, 100} равен 4, а mex множества {2, 3, 4, 5} равен 1.

У вас есть множество чисел A, состоящее из n целых положительных чисел, и положительное число k. Затем вы k раз произвели следующую операцию: добавили в множество A ещё одно число, равное mex(A), тем самым, каждый раз увеличивая размер множества A на один.

По заданному множеству A и числу k определите последнее число, которое было добавлено в множество.

Входные данные
В первой строке заданы два целых числа n и k (1<=n<=100000, 1<=k<=10⁹) — количество чисел в множестве и количество операций добавления числа.
Вторая строка содержит n различных целых чисел a₁, a₂, ..., a_n (1<=a_i<=100000) — элементы множества A.

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

Примечание
В первом примере mex множества {1, 2, 4, 5} равен 3, после добавления mex в множество, оно станет равным {1, 2, 3, 4, 5}.

Примеры

№	Входные данные	Выходные данные
1	4 1 4 2 1 5	3
2	7 10 1 3 20 2 7 45 5	15

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

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

Остановки автобуса#44938

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

Выйдя из метро, Василий очень торопится домой, но ждать автобус на остановке Василий не любит. Так как автобус Василий не ждет никогда, то, подойдя к остановке и не увидев автобуса, он идет дальше вдоль проспекта. В случае же, если Василий заметит автобус, то он либо возвращается на остановку, либо продолжает свой путь к следующей остановке.
Василий идет со скоростью U, автобус едет со скоростью V. Найдите минимальное расстояние L, которое должно просматриваться перед нулевой остановкой, чтобы он мог идти со своей скоростью в сторону дома, не опасаясь, что автобус его обгонит между остановками.

Входные данные
В первой строке входных данных находятся три числа N, U и V (N <= 1000, U и V – положительные вещественные), вторая строка содержит N вещественных чисел – X₁, X₂,... X_n (0 < X1 < X2 < … < Xn < 10⁶), разделенных пробелами.

Выходные данные
В выходной файл ваша программа должна вывести число L с точностью до 10^-4.

Примеры

№	Входные данные	Выходные данные
1	1 1 10 2	9.0000
2	5 1 10 1 2 4 8 16	28.0000

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

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

Эстафета#44937

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

Рассмотрим следующий пример. Пусть на сборах 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две команды по три человека в каждой. Тогда одним из вариантов является такой:
1 команда: учащиеся с ростом 225, 205, 225
2 команда: учащиеся с ростом 160, 190, 170
При этом число неуспешности первой команды будет равно 20, а число неуспешности второй — 30. Максимальное из чисел неуспешности будет 30, и это будет наилучший возможный результат.

Входные данные
Первая строка входных данных содержит три натуральных числа N, R и C - количество учащихся на сборах, количество команд и количество человек в каждой команды (1 <= R·C <= N <= 100 000).
Далее вводятся N целых чисел — рост каждого из N учеников. Рост ученика - натуральное число, не превышающее 1 000 000 000.

Выходные данные
Выведите одно число - наименьше возможное значение максимального числа неуспешности сформированных команд.

Примеры

№	Входные данные	Выходные данные
1	8 2 3 170 205 225 190 260 130 225 160	30

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

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

Автомобиль "Пантера"#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средняяВойти и решать

Автомобиль "Пантера" - 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средняяВойти и решать

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

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

Засада на переговорах#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✗ 48900средняяВойти и решать

Очередные операции над массивом#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средняяВойти и решать

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

Последняя ненулевая факториала#42251

Для заданного натурального N найдите последнюю ненулевую цифру числа N!.

Входные данные
Программа получает на вход целое число N (0 <= N <= 10⁶).

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

Примеры

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

Остатки теория чисел Цикл for

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

Номер числа Фибоначчи#42242

Дано натуральное число A > 1. Определите, каким по счету числом Фибоначчи оно является, то есть выведите такое число n, что f_n=A. Если A не является числом Фибоначчи, выведите число -1.

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

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

Примеры

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

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

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