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

Неглухой телефон#46660

Возможно, что Вы когда то играли в игру «Глухой телефон», либо слышали о ней. В этой игре участникам приходится передавать информацию друг другу различными способами: словесно, образно, бывает даже приходится писать левой рукой текст, который другой участник команды должен будет прочитать. Так же известно, что практически никогда передаваемая информация не доходит до конечного адресата. Обозначим за F_i(x) функцию, которая преобразует текст передаваемой информации x в ту, которую получит участник i+1 от участника i. Тогда последний n-й участник получит данные y, которые будут выражаться следующей формулой:

y = F_n-1(F_n-2(…F₂(F₁(x))))

Но Вам необходимо исключить какие-либо внешние факторы, которые могут исказить исходную информацию и Вы должны реализовать программу «неглухой телефон», которая сможет безошибочно доставлять исходные данные, т.е. в нашем случае функция F_i(x) = x для всех i от 1 до n-1.

Входные данные
В первой строке записано число n от 1 до 100, во второй строке - сообщение переданное первым участником (строка длиной не более 255 символов).

Выходные данные
Выведите значение F(n)

Задача на реализацию

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

Башни 2.0#44509

В компьютерной игре есть n башен, высота i-й башни равна a_i метров. Определим расстояние между двумя башнями с индексами i и j как |i−j|. Разрешается прыгнуть с i-й башни на j-ю башню тогда и только тогда, когда не существует такого индекса 1 <= k <= n, такого, что расстояние от i-й до j-й башни не меньше расстояния от i-й башни до k-й башни, и k-я башня имеет большую высоту, чем j-я. Башня j достижима из башни i если существует последовательность корректных прыжков, которая начинается в i-й башне и заканчивается в j-й. Посчитайте для каждой башни количество достижимых из неё башен, включая её саму.

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

Первая строка входных данных содержит одно целое число n (1 <= n <= 500000) - количество башен.

Вторая строка входных данных содержит n чисел a₁, a₂, ..., a_n (1 <= a_n<= 10⁹) - высоты башен.

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

Примечание

В первом примере с 1-й башни можно прыгнуть на башни 1 и 5. Любая другая башня имеет меньшую высоту, чем башня 1, поэтому туда нельзя прыгнуть (в качестве k можно выбрать 1). Множество достижимых из 1-й башни также состоит из башен 1 и 5. Со второй башни можно прыгнуть на башни 1, 2, и 5, они же являются множеством достижимых. С третьей башни можно прыгнуть на башни 2, 3, 5. Однако, башня 1 также является достижимой, поскольку можно сделать два прыжка: 3→2→1. Таким образом, получается 4 достижимые башни. С 4-й башни можно прыгнуть на башни 4 и 5, они же являются единственными достижимыми. Из 5-й башни достижима только она сама.

Во втором примере из 1-й и из 2-й башни достижимы башни 1,2,3,4,5. Из 3-й башни достижимы башни 3,4,5. Из 4-й и 5-й башни достижимы башни 4,5. Из 6-й башни достижимы башни 4,5,6. Из 7-й башни достижимы башни 4,5,6,7.

Примеры

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

Алгоритмы обработки Задача на реализацию Линейные алгоритмы Структуры данных

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

Олимпиада по выживанию#44362

В некоторой стране каждый год проходит олимпиада по выживанию. В финале участвуют по 4 человека от каждой из n провинций. По результатам соревнования составляется рейтинг, в который входят все 4n участников в порядке убывания баллов, равных баллов у участников не бывает. Дипломами награждаются ровно 50 % лучших участников (то есть если общее число участников было равно m, то награждаются m/2 первых участников из общего рейтинга).
После публикации предварительного рейтинга тренеры команд могут подавать апелляции против каких-то других провинций, обвинив участников из этой провинции в нарушении правил олимпиады. Каждый тренер может не подавать аппеляции или подать апелляцию на одну или несколько команд соперников.
Если жюри удовлетворит апелляцию против команды, то все участники из данной провинции будут дисквалифицированы и удалены из таблицы результатов. При этом общее число количество участников уменьшится на 4, а количество призёров олимпиады уменьшится на 2.
Тренеры команд каждой из провинций хотят улучшить результаты участников из своей провинции (то есть сделать так, чтобы количество участников олимпиады из этой провинции, которые стали призёрами, увеличилось хотя бы на одного). Для этого они планируют подать апелляции против команд других провинцией. Для каждой провинции определите, какое минимальное количество аппеляций должно удовлетворить жюри, чтобы количество участников из этой провинции, награждённых дипломами, увеличилось. Обратите внимание на то, что вы должны дать ответ для каждой провинции независимо, то есть без учёта возможных апелляций, поданных другими командами.

Входные данные
В первой строке входных данных содержится одно целое число n (1 ≤ n ≤ 25000) — количество провинций, участвовавших в олимпиаде. Следующие 4·n строк содержат рейтинг участников олимпиады, в порядке от лучшего участника к худшему. В i-й строке содержится число от 1 до n — номер команды i-го по рейтингу участника олимпиады. Гарантируется, что в списке участников каждое число от 1 до n встречается ровно 4 раза.
Выходные данные
Программа должна вывести n строк. В i-й строке необходимо вывести минимальное число апелляций, которое должно удовлетворить жюри, чтобы количество награждённых дипломами участников из i-й команды увеличилось. Если улучшить результаты i-й команды путём подачи апелляций нельзя, то в i-й строке должно быть записано число −1.

Примеры

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

Замечание
В первом примере из условия в олимпиаде участвовали две команды, и рейтинг участников выглядит так: 1, 1, 1, 2, 2, 2, 2, 1. По предварительному рейтингу дипломами награждаются три участника команды 1 и один участник команды 2. Команда 1 не может улучшить свои результаты, так как если команда 2 будет дисквалифицирована, то дипломы будут выданы всего 2 участникам из 4, но первоначально у команды 1 было 3 диплома. А вторая команда может увеличить количество призёров до 2, подав апелляцию против команды 1.
Во втором примере у обеих команд уже есть по 2 диплома, а при удалении одной из команд останется всего 2 призовых места, то есть при подаче апелляции против другой команды у каждой команды количество дипломов не изменится.
В третьем примере участвовали 3 команды и первоначально дипломами награждались участники из команд 3, 3, 2, 2, 1, 3. Команда 1 может улучшить свои результаты, если подаст две апелляции: против команд 2 и 3. Тогда останется только 4 участника (все они из команды 1), из них дипломами будет награждено двое. Команда 2 может улучшить свои результаты, если подаст одну апелляцию против команды 3. Тогда останется 8 участников и дипломами будут награждены 4 из них: 2, 2, 1, 2, — и у команды 2 станет 3 призёра вместо 2. Команда номер 3 не может улучшить свой результат при помощи апелляций.

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

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

Майки и носки#44310

Как известно, осенью и зимой светает поздно и так хочется утром ещё хоть немного поспать, а не идти в школу! Некоторые школьники готовы даже одеваться, не открывая глаз, лишь бы отложить момент пробуждения. Вот и Саша решил, что майку и носки он вполне может вытащить из шкафа на ощупь с закрытыми глазами и только потом включить свет и одеться.
В шкафу у Саши есть два ящика. В одном из них лежит A синих и B красных маек, в другом — C синих и D красных пар носков. Саша хочет, чтобы и майка, и носки были одного цвета. Он вслепую вытаскивает M маек и N пар носков. В первое же утро Саша задумался, какое минимальное суммарное количество предметов одежды (M + N) он должен вытащить, чтобы среди них гарантированно оказались майка и носки одного цвета. Какого именно цвета окажутся предметы одежды, для Саши совершенно неважно.

Входные данные
На вход программе подаются четыре целых неотрицательных числа A, B, C, D, записанных в отдельных строках: A — количество синих маек, B — количество красных маек, C — количество синих носков, D — количество красных носков. Все числа не превосходят 10⁹ . Гарантируется, что в шкафу есть одноцветный комплект из майки и носков.

Выходные данные
Программа должна вывести два числа: количество маек M и количество пар носков N, которые должен взять Саша. Необходимо, чтобы среди M маек и N пар носков обязательно нашлась одноцветная пара, при этом сумма M + N должна быть минимальной.

Примеры

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

Замечание
В примере из условия в шкафу лежит A = 6 синих маек и B = 2 красных маек. Если взять 3 майки, то среди них обязательно найдётся синяя. В другом ящике лежит C = 7 пар синих носков и D = 3 пары красных носков. Если взять 4 пары, то среди них обязательно будет пара синих
носков. Поэтому если взять вслепую 3 майки и 4 пары носков, то среди них обязательно найдётся одноцветный (синий) комплект из майки и носков.

Задача на реализацию Разбор случаев

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

Надпись на табло#44288

Вы получили доступ к одной из камер наблюдения в особо секретной огранизации. В зоне видимости камеры находится табло, с которого вы постоянно считываете информацию. Теперь вам нужно написать программу, которая по состоянию табло определяет, какая буква изображена на нём в данный момент. Табло представляет из себя квадратную таблицу, разбитую на n × n равных квадратных светодиодов. Каждый диод либо включён, либо выключен. Введём систему координат, направив ось OX вправо, а ось OY — вверх, приняв сторону диода равной 1.
На табло могут быть изображены только следующие буквы:
• I — прямоугольник из горящих диодов.
• O — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого есть прямоугольник из выключенных диодов с координатами углов (x3, y3) и (x4, y4). При этом границы выключенного прямоугольника не должны касаться внешнего, то есть x1 < x3 < x4 < x2 и y1 < y3 < y4 < y2.
• C — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого есть прямоугольник из выключенных диодов с координатами углов (x3, y3) и (x4, y4). При этом правая граница выключенного прямоугольника находится на правой границе внешнего прямоугольника, то есть x1 < x3 < x4 = x2 и y1 < y3 < y4 < y2.

• L — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого есть прямоугольник из выключенных диодов с координатами углов (x3, y3) и (x4, y4). При этом правые верхние углы выключенного прямоугольника и внешнего прямоугольника совпадают, то есть x1 < x3 < x4 = x2 и y1 < y3 < y4 = y2.
• H — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого находятся 2 прямоугольника из выключенных диодов с координатами углов (x3, y3), (x4, y4) у первого и (x5, y5), (x6, y6) у второго. При этом выключенные прямоугольники должны иметь одинаковую
ширину, находиться строго один под другим, один прямоугольник должен касаться верхней стороны, а другой прямоугольник должен касаться нижней стороны внешнего прямоугольника, то есть x1 < x3 = x5 < x4 = x6 < x2 и y1 = y3 < y4 < y5 < y6 = y2.

• P — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого находятся 2 прямоугольника из выключенных диодов с координатами углов (x3, y3), (x4, y4) у первого и (x5, y5), (x6, y6) у второго. При этом правый нижний угол первого выключенного прямоугольника должен совпадать с правым нижним углом внешнего прямоугольника, а другой выключенный прямоугольник должен находиться строго выше и не касаться границ других прямоугольников, также левые границы двух выключенных прямоугольников должны совпадать, то есть x1 < x3 = x5 < x6 < x4 = x2 и y1 = y3 < y4 < y5 < y6 < y2.

• Любое другое состояние табло считается буквой X.
По виду табло определите, какая буква на нём изображена.

Входные данные
В первой строке входных данных находится одно число n (1 ≤ n ≤ 10) — сторона табло.
В следующих n строках находятся строки длины n из символов «.» и «#» — строки таблицы.
«.» обозначает выключенный квадратный диод табло, а «#» — горящий.

Выходные данные
Программа должна вывести единственный символ: если данная таблица подходит под одно из описаний букв I, O, C, L, H, P, то выведите её (все буквы — английские). Если же данная таблица не подходит ни под какие условия, то выведите X.

Примеры

№	Входные данные	Выходные данные
1	4 .##. .##. .##. ....	I
2	5 #...# .#.#. ..#.. .#.#. #...#	X

Задача на реализацию

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

Мишины кубики#43718

У маленького Миши есть кубики, на каждом из которых написана одна английская строчная буква. Вчера он выкладывал кубики в два ряда. В первом ряду у Миши n кубиков с буквами, во втором - m кубиков с буквами. Так получилось, что в двух этих рядах нет совпадающих букв. Другими словами, ни одна буква не содержится одновременно в обоих рядах.
Сегодня маленький Миша решил продолжить играть с кубиками. Но теперь он берет один любой кубик из какого-либо ряда и составляет из них третий ряд, добавляя кубик всегда в конец. Маленький Миша никогда не берет более k кубиков подряд из одного и того же ряда. Миша закончил играть тогда, когда у него закончились кубики в каком-то одном ряду (в первом или во втором).
Наблюдавший за игрой папа заметил, что играя таким образом у Миши получилась лексикографически наименьшая строка. По известным двум строкам, которые образуются путем прочтения букв первого и второго ряда и числу k определите строку, которую получил маленький Миша.

Строка x лексикографически меньше строки y только и только тогда, когда выполняется одно из следующих условий:
- x является префиксом y, но x != y;
- в первой позиции, где x и y различаются, в строке x находится буква, которая стоит в алфавите раньше, чем соответствующая буква y.

Входные данные
Программа получает на вход несколько строк. В первой строке записаны три числа: n - количество кубиков в первом ряду, m - количество кубиков во втором ряду, k - целое число(1 <= n, m, k <= 100). Во второй строке записана строка a длиной n - строка, образованная прочтением букв, написанных на кубиках первого ряда. В третьей строке - строка b длиной m - строка, образованная прочтением букв, написанных на кубиках второго ряда.

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

Примеры

№	Входные данные	Выходные данные
1	6 4 2 aaaaaa bbbb	aabaabaa

"Два указателя"Жадный алгоритм Задача на реализацию Использование сортировки Простые задачи на перебор

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

Книжки с полки#43532

Петя обладает обширной библиотекой книг. Сейчас он стоит возле полки с приключенческими рассказами. На ней расположены n книг. Все книги на полке у Пети всегда пронумерованы слева направо. Книга с номером i имеет a_i страниц. На полке, возле которой сейчас стоит Петя, количество страниц в каждой книге различно.

Особенность полок в библиотеке Пети такова, что он может брать только крайнюю книгу с полки (то есть либо самую левую, либо самую правую).

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

Входные данные
В первой строке записано одно целое число n (2 <= n <= 100) - количество книг на полке. Во второй строке находится n целых различных чисел a₁, a₂, ..., a_n (1 <= a_i <= 10⁶) - количество страниц в книге.

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

Примеры

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

Задача на реализацию Одномерные массивы

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

Громозека и валерьянка#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 Циклы

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

Книги Томми#43351

Томми очень любит читать. Он взял из библиотеки n книг (в i-й книге a_i страниц, страницы нумеруются с 1). Томми очень бережно относится к книгам, поэтому каждую из них обернул в обложку. Но, так как у него не оказалось ни одной прозрачной обложки, он пронумеровал книжки от 1 до n и написал номер на обложке каждой книги.

Томми читает уже m дней подряд. Книги он читает строго по порядку, начиная с книги с номером 1. Каждый день он записывает на доску общее число страниц, которые прочитал к текущему дню.

Например, если бы Томми взял 2 книги и, при этом, в в первой книге 3 страницы, а во второй - 5 страниц, то прочитав в первый день 2 страницы, а во второй день - 4 страницы у Томми на доске было бы записано два числа 2 и 6.

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

Входные данные
Программа получает на вход несколько строк. Первая строка содержит два целых числа n и m (1 <= n, n <= 2·10⁵) - количество книг, взятых Томми из библиотеки и количество дней, в течении которых Томми читал книги. Во второй строке следует последовательность a₁, a₂, ... a_n (1 <= a₁<= 10¹⁰), где a_i равно количеству страниц в i-й книге. В третьей строке следует последовательность d₁, d₂, ... d_m (1 <= d_j<=a₁+ a₂+...+ a_n), где d_j равно общему числу страниц, прочитанных Томми к j-му дню. Все d_j заданы в порядке возрастания.

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

Выведите m строк. В каждой строке выведите по два числа - номер книги k (1 <= k <= n) и номер страницы в этой книге s (1 <= s <= a_k), на которой остановился Томми в текущий день.

Примеры

№	Входные данные	Выходные данные
1	3 6 10 15 12 1 9 12 13 15 17	1 1 1 9 2 2 2 3 2 5 2 7
2	2 3 5 10000000000 5 6 9999999999	1 5 2 1 2 9999999994

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

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

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

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

Горнолыжный курорт#43133

Саша Белый недавно устроился подрабатывать на горнолыжный курорт недалеко от Аши. Первым делом ему поручили установить ограждения для лыжной трассы.
Саше дали n ограждений, каждое длиной a_i. Любые два последовательных ограждения скреплены друг с другом, но при этом могут произвольно поворачиваться друг относительно друга.
Саша хочет сделать трассу интересной: по его мнению, трасса должна быть в форме спирали (ограждение под номером i +1 должно быть повернуто на 90 градусов по часовой стрелке относительно ограждения под номером i; при этом никакие ограждения, кроме смежных, не должны касаться друг друга и пересекаться).
К сожалению, не из любых наборов ограждений можно сложить спираль. Помогите Саше для заданного набора определить, возможно ли из него составить спираль.
Входные данные
В первой строке входных данных записано целое число n — количество ограждений (1 <= n <= 10⁵). Во второй строке через пробел заданы n целых чисел a_i — длина i-го ограждения (1 <= a_i <=10⁹).
Выходные данные
Выведите YES, если возможно из данных ограждений сложить спираль, или NO в противном случае.

Примеры

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

Замечание
Обратите внимание на третий пример, спираль может иметь два центра, главное, чтобы ограждения не пересекались. Иллюстрация к третьему примеру:

Задача на реализацию Разбор случаев

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

Ящики#43125

Саша Белый давно планировал переехать в Кыштым. И вот настал день X. Саша собрал все свои вещи в ящики и вынес их на улицу. Ящики были распределены на n стопок, расположенных вдоль одной прямой, следующим образом: a₁ ящиков в первой стопке стоят непосредственно у газели, a₂ ящиков во второй стопке – правее первой на метр, следующие a₃ еще через метр и т.д. Теперь Белому нужно переставить все ящики как можно ближе к газели, а именно, все ящики из второй, третьей и т.д. стопок должны быть переставлены в первую стопку к исходным a₁ ящикам.
Саша за этот день уже очень устал. Но, к счастью, мимо проходили n мальчишек. Ребята согласились перенести ящики. Каждый из них, ввиду своей выносливости, переносит грузы следующим образом:
1. i-й мальчик проходится по стопкам, номера которых делятся на i, справа налево.
2. Он берет из первой стопки на своем пути ровно один ящик (эта стопка обязана быть непустой).
3. Пройдя i метров налево (то есть до следующей стопки, номер которой делится на i), он снова берет один ящик со стопки, рядом с которой он стоит (исходя из этого, в стопке обязательно должен быть хотя бы один ящик), пройдя еще i метров налево он снова берет ящик и так далее.
4. Когда i-й мальчик доходит до стопки с номером i, он кладет все ранее взятые ящики в эту стопку.

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

Входные данные
В первой строке входных данных записано целое число n количество стопок ящиков (1 <= n <= 10⁵).
Во второй строке через пробел записаны n целых чисел di количество ящиков в i-й стопке (1 <= d_i <= 10⁹).
Выходные данные
Выведите YES, если существует способ, при котором ребята перенесут все ящики к газели в первую стопку, или NO, если такого способа нет.

Примеры

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

Замечание
В первом примере сначала второй мальчик пройдется два раза, таким образом перенеся два ящика из четвертой стопки во вторую. После этого шага d = (2,3,3,3,3). Потом первый мальчик пройдется 3 раза, перетащив все ящики в первую стопку.
Во втором примере мальчикам не удастся перенести все ящики в первую стопку.

Вывод формулы Задача на реализацию математика

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

Сериал#42973

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

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

Выходные данные
Программа должна вывести три целых числа i, j, k (1 <= i < j < k <= N) — номера искомых трех серий. Серии нумеруются числами от 1 до N. Если ответов несколько, выведите любой из них. Если ответа не существует, выведите одно число ноль.

Примеры

№	Входные данные	Выходные данные
1	4 1985 2000 1990 2005	1 2 4
2	4 2000 2000 2001 2001	0

Замечание
В первом примере нужно выбрать серии 1, 2, 4, действие которых происходит в 1985, 2000 и 2005 годах соответственно.
Во втором примере выбрать три серии, удовлетворяющие условиям задачи, нельзя.

Задача на реализацию Линейные алгоритмы

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

Подпоследовательность с максимальной суммой#39477

Дана последовательность из N целых чисел. Рассматриваются все её непрерывные подпоследовательности, начинающиеся с первого элемента последовательности. Найдите максимальную сумму подпоследовательности, кратную K, и количество таких подпоследовательностей.

Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 10⁶) и число K (1 <= K <= 100). Далее идет N строк, по одному целому числу в строке. Каждое число не превышает 10000.

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

Примеры

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

Алгоритмы обработки Задача на реализацию Префиксные суммы(минимумы, ...)

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

Громозека и Алиса - 2#39397

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

Входные данные
В первой строке задан, момент времени, в который Громозека и Алиса вошли в первое кафе. Формат времени: часы (число от 00 до 23), далее идет двоеточие, затем минуты (число от 00 до 59). Строка времени записана без пробелов.
Во второй строке записано натуральное число N (2 <= N <= 1000) - количество посещенных кафе (включая кафе из которого они вышли в начальный момент времени и последнее кафе). В третьей строке записано N-1 число: первое показывает время в минутах от входа в первое кафе до входа во второе, второе - время от входа во второе кафе до входа в третье и т.д. Каждое из этих чисел натуральное и не превышает 1000.

Выходные данные
Выведите для каждого кафе время входа Алисы и Громозеки. Формат времени должен быть такой же, как и во входных данных.

Примеры

№	Входные данные	Выходные данные
1	07:00 4 10 5 3	07:00 07:10 07:15 07:18

Задача на реализацию Одномерные массивы Циклы

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

Отслеживание контактов#39388

Фермер Джон продолжает заботиться о здоровье своих коров, последовательно пронумерованных 1…N.
Недавно ФД проверил их всех и выяснил, что некоторые из них больны. Используя видео из амбара, ФД может узнать какие пары коров взаимодействовали распространяя при этом болезнь. ФД собрал список с указанием времени, в которое происходило взаимодействие пар коров в видео (t,x,y), означающем, что в момент времени t корова x взаимодействовала с коровой y. Также ФД знает следующее:

Ровно одна корова была инфицирована изначально (нулевой пациент).
После того, кaк корова инфицирована, она передаёт инфекцию её следующим K взаимодействиям (возможно включая одного и того же партнера несколько раз). После K раз передачи инфекций, она перестаёт передавать инфекцию (осознав что заражает, она начинает тщательно мыть копыта).
Однажды заболев, она остаётся больной.

К несчастью, ФД не знает, какая из его N коров, является "нулевым пациентом", кроме того он не знает значение K!. Помогите ему сузить диапазоны этих неизвестных, основываясь на его данных. Гарантируется, что ответ существует.

Входные данные
Первая строка ввода содержит N (2<= N <=100) и T (1 <= T <= 250). Следующая строка содержит строку длиной N, состоящую из 0 и 1, описывающую текущее состояние N коров ФД, 0 - здорова, 1 - больна. Каждая из последующих T строк описывает запись из списка взаимодействий ФД, и состоит из трёх чисел, t,x,y, где t - положительное целое время взаимодействия (t <= 250), x и y - различные целые в интервале 1…N, указывающее какие коровы взаимодействовали в момент времени T. В один момент времени T происходит не более одного взаимодействия.

Выходные данные
Выведите одну строку, содержащую три целых числа x,y,z, где x - количество различных коров, которые могли быть "нулевым пациентом", y - минимально возможное значение K, подходящее к исходным данным, z - наибольшее возможное значение K, подходящее к исходным данным. Если для K нет верхней границы, выведите "Infinity" для z. Заметим, что возможно K=0.

Примеры

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

Задача на реализацию Задачи на моделирование Перебор

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

Сломанный принтер#39062

Сломанный цветной принтер, печатая цифры, закрашивает все замкнутые области в красный цвет. Например, в цифрах 0, 4, 6, 9 одна замкнутая область. В цифре 8 - 2 замкнутых области. В других цифрах нет замкнутых областей, которые закрашиваются. В принтере красной краски осталось на покраску h замкнутых областей. Найдите минимальное неотрицательное число, напечатав которое в принтере закончится красная краска. Число не должно содержать ведущих нулей. Если в принтере отсутствует красная краска, то он не может напечатать цифру с замкнутой областью.

Входные данные
На вход подается число h (0 <= h <= 510).

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

Примеры

№	Входные данные	Выходные данные
1	15	48888888
2	70	88888888888888888888888888888888888

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

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

Морской бой#39058

Чтобы разнообразить игру «морской бой» Боря решил добавить в неё новый тип кораблей. Эти корабли состоят из двух прямоугольников. Первый прямоугольник имеет ширину w₁ и высоту h₁, а второй прямоугольник - w₂ и h₂ соответственно. Прямоугольники располагаются один над другим и выровнены по левому краю (см. рисунки примеров): введём на поле систему координат так, чтобы левая нижняя клеточка первого прямоугольника имела координаты (1,1). Тогда верхняя правая клеточка первого прямоугольника имеет координаты (w₁,h₁), левая нижняя клеточка второго прямоугольника имеет координаты (1,h₁+1), а правая верхняя клеточка второго прямоугольника имеет координаты (w₂,h₁+h₂).

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

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

Входные данные
В четырёх строках заданы четыре целых числа w₁,h₁,w₂ и h₂ (1<=w₁,h₁,w₂,h₂<=10⁸) - ширина первого прямоугольника, высота первого прямоугольника, ширина второго прямоугольника и высота второго прямоугольника, соответственно.

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

Примечание

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

Во втором примере поле выглядит так:

Примеры

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

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

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

Диадема Клеопатры#38955

Аня — страстный любитель ювелирных изделий. Ее коллекция насчитывает множество бриллиантов, изумрудов и алмазов.

...Срочная новость! Бесценный змеиный рубин Клеопатры был украден!

Три дня назад мир потрясло сенсационное известие: исследовательская экспедиция обнаружила в одном из храмов, построенных во времена великой египетской императрицы Клеопатры, потайную комнату. В ней кроме бронзовой статуи императрицы обнаружилась поразительной красоты диадема, ранее считавшаяся бесследно утерянной! Ученые сообщили, что диадема увенчана алым a-каратным рубином в форме змеиной головы. Однако буквально пару часов назад поступила новость, что бесценное украшение было изувечено: кто-то пробрался в камеру хранения диадемы и вырезал из нее рубин! Полиция устанавливает круг подозреваемых...

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

Купив все N камней, Глеб тут же провел несколько пробных измерений, взвесив некоторые наборы из них, и отправил результаты Ане по электронной почте. Тем временем она проконсультировалась с известным исследователем старины Андрэ Шесто-Мерта по поводу украденной драгоценности и узнала, что по всем имеющимся историческим источникам рубин весил не a карат, как утверждали журналисты, а b карат!

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

Входные данные
В первой строке находятся четыре целых числа N, a, b и K (1 ≤ N ≤ 200, 1 ≤ a, b ≤ 1 000 000, a ≠ b, 1 ≤ K ≤ 1 000).

Далее идут K строк, описывающих взвешивания, проведенные Глебом.

Первое число в i-ом описании — w_i (1 ≤ w_i ≤ 200 000 000), суммарный вес группы камней, участвовавших в i-ом взвешивании.

Второе число — m_i (1 ≤ m_i ≤ N) — количество камней, участвовавших в i-ом взвешивании.

Далее следуют m_i целых чисел, упорядоченных по возрастанию, — номера камней, участвовавших в i-ом взвешивании.

Выходные данные
Если среди купленных Глебом камней змеиного рубина точно нет, выведите строку "Fail" (без кавычек).

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

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

Примеры

№	Входные данные	Выходные данные
1	4 15 17 2 30 2 1 3 47 3 2 3 4	2 2 4
2	3 15 17 3 30 2 1 2 30 2 2 3 47 3 1 2 3	Impossible
3	2 1 2 2 1 1 2 1 1 1	Fail

Примечание
В первом тесте из первого взвешивания мы делаем вывод, что первый и третий камни гарантированно поддельные. С другой стороны, среди второго, третьего и четвёртого камня точно есть настоящий. Значит настоящим может оказаться второй или четвёртый камень.

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

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

Задача на реализацию Разбор случаев

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