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

Гость из прошлого#39059

Коля Герасимов очень любит кефир, и в своём 1984 году он освоил все тонкости покупки этого чудесного напитка. Но однажды, как вам, наверное, известно, он попал в далёкий 2084 год, где покупка кефира представляет собой более сложный процесс.

Будущее будущим, а кушать хочется всегда, поэтому Коля отправился в местную молочную лавку. В 2084 году кефир продают в литровых пластиковых бутылках по a копеек за штуку и в литровых бутылках из стекла по b копеек за штуку. При этом пустую стеклянную бутылку можно сдать и получить назад c (c < b) копеек, а пластиковую бутылку сдать нельзя.

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

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

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

Пояснения к примерам

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

Примеры

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

Жадный алгоритм Задачи на моделирование

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

Наша Таня громко плачет#39057

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

Сегодня рабочий день системного администратора Миши начался со звонка секретаря Тани, которая в очередной раз не справилась с редактированием документа. Миша моментально пришёл к Тане и узнал, что в результате ошибки в папке на ее компьютере оказалось n копий документа, над которым она сейчас работает. Других документов в папке нет. Таня просит Мишу удалить лишние копии, чтобы у неё осталась ровно одна копия нужного файла.

Таня работает в операционной системе Bububuntu, в которой есть две команды, позволяющие удалять файлы. Первая команда удаляет один произвольный файл с компьютера. На выполнение этой команды Миша тратит A секунд. Вторая команда рассчитана как раз на случай, подобный Таниному, и позволяет уменьшить количество копий файла в k раз. В силу технический особенностей Bububuntu эта команда работает, только если количество файлов в папке делится на k без остатка. На выполнение этой команды Миша тратит B секунд.

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

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

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

В первой строке содержится целое число n ( 1 <= n <= 2*10⁹) - количество копий документа в папке у Тани.
Во второй строке содержится целое число k ( 1 <= k <= 2*10⁹) - количество раз, в которое уменьшает количество файлов вторая команда.
В третьей строке содержится целое число A ( 1 <= A <= 2*10⁹) - количество секунд, которое Миша тратит на выполнение первой команды.
В четвёртой строке содержится целое число B ( 1 <= B <= 2*10⁹) - количество секунд, которое Миша тратит на выполнение второй команды.

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

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

Примечание

В первом тестовом примере оптимальная стратегия Миши такова:

За 3 секудны удалить один файл, в результате чего в папке останется 8 файлов. Обратите внимание, что Миша не мог использовать вторую команду, потому что 9 не делится на 2 .
За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 4 файла.
За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 2 файла.
За 1 секунду уменьшить число файлов в 2 раза. После этого в папке останется 1 файл и цель Миши будет выполнена.

На выполнение этих четырёх операций Миша потратит 6 секунд. Можно показать, что Миша не сможет удалить лишние файлы меньше, чем за 6 секунд.

Во втором тестовом примере Мише выгодно 4 раза удалить один файл. Так как на одно удаление Миша тратит 2 секунды, на выполнение всего задания Миша потратит 4·2 = 8 секунд. Кроме того, Миша мог бы удалить лишние файлы, один раз воспользовавшись второй командой, но, так как её выполнение занимает 20 секунд, Мише это не выгодно.

Примеры

№	Входные данные	Выходные данные
1	9 2 3 1	6
2	5 5 2 20	8
3	19 3 4 2	12

Динамическое программирование Задачи на моделирование

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

Счастливого Нового Года!#38924

В каком-то другом мире сегодня 31 декабря. Дед Кокованя решил приготовить многомерный бургер, который так любит Дарёна. Бургер уровня L (L - целое число, большее или равное 0) готовится следующим образом:

Бургер нулевого уровня - это котлета.
Бургер с уровнем L (L >= 1) - это булочка, бургер с уровнем (L-1), котлета, бургер с другим уровнем (L-1) и еще одна булочка, уложенные вертикально в указанном порядке, считая снизу.

Например, бургер уровня 1 и бургер уровня 2 выглядят как БКККБ и ББКККБКБКККББ (повернутые на 90 градусов), где Б и К обозначают булочку и котлету.

Бургер, который приготовит дед Кокованя, - это бургер уровня N. Дарёна всегда съедает только Х слоев нижней части бургера (слой - это котлета или булочка). Сколько котлет она съест?

Входные данные
Программа получает на вход 2 целых числа через пробел: N и X (1 <= N <= 50, 1 <= X <= (общее количество слоев в бургере N-го уровня)).

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 7	4	В самых нижних 7 слоях бургера второго уровня ( `ББКККБКБКККББ`) находятся 4 котлеты.
2	1 1	0
3	50 4321098765432109	2160549382716056	Бургер 50-го уровня довольно толстый настолько, что количество его слоев не укладывается в 32-битное целое число.

Перебор Рекурсивный перебор Рекурсия

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

Раскраска в три цвета#38919

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

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

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

Входные данные
В первой строке вводятся два целых числа n и m – количество кружков и количество линий, которые нарисовал Петя, соответственно (1 ≤ n ≤ 1 000, 0 ≤ m ≤ 20 000).
Следующая строка содержит n символов из множества {'R', 'G', 'B'} – i-й из этих символов означает цвет, в который раскрашен i-й кружок ('R' – красный, 'G' – зеленый, 'B' – синий).
Далее в m строках задается по два целых числа – пары кружков, соединенных отрезками.

Выходные данные
Выведите одну строку, состоящую из n символов из множества {'R', 'G', 'B'} – цвета кружков после перекраски. Если решений несколько, выведите любое.
Если решения не существует, выведите слово "Impossible''.

Примеры

№	Входные данные	Выходные данные
1	4 5 RRRG 1 3 1 4 3 4 2 4 2 3	BBGR
2	4 5 RGRR 1 3 1 4 3 4 2 4 2 3	Impossible

Обход в глубину Простые задачи на перебор

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

Число#38848

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

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

Формат входных данных
Входные данные состоят из одной или более строк, каждая из которых содержит последовательность цифр. Количество строк не превышает 100, каждая строка содержит от 1 до 100 цифр. Гарантируется, что хотя бы в одной строке первая цифра отлична от нуля.
Последняя строка входного потока содержит число -1 - признак окончания данных.

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

Алгоритмы на строках Использование сортировки

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

Удаление клеток#38830

Из прямоугольного листа клетчатой бумаги (M строк, N столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.

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

В первой строке находятся числа M и N, в следующих M строках - по N символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка. 1 <= M, N <= 100.

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

Вывести одно число.

Примеры

№	Входные данные	Выходные данные
1	5 10 ##..#####. .#.#.#.... ###..##.#. ..##.....# .###.#####	5

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

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

Breaking News#38805

Жизнь завода по производству олимпиадных задач монотонна и однообразна: каждый день происходит одно и то же, вечера похожи как две снежинки и каждое утро всё начинается сначала - ничего не меняется на заводе по производству олимпиадных задач.
В частности, давно известно, когда в течение дня пара сотрудников встречается между собой.
При встрече сотрудники делятся друг с другом новостями.
Утром перед работой сотрудник номер 1 узнал нежелательную новость. Конечно же, он делится с ней при встрече со всеми остальными сотрудниками и они тоже узнают новость и начинаются делиться ей с другими. Если встречаются два сотрудника и один из них знает новость, то начиная с этого момента второй из них также знает новость. Ни один сотрудник не может встречаться с двумя или более сотрудниками одновременно (из соображений секретности). Пара сотрудников может встречаться несколько раз в течение дня.
Вы можете помешать ровно одной встрече за весь день. Выберите такую встречу, отмена которой приведёт к тому, что как можно меньше сотрудников завода узнают новость.

Входные данные
В первой строке входного файла задано два целых числа N (2 ≤ N ≤ 1000) и D (1 ≤ D ≤ 100000) — количество сотрудников и встреч соответственно. В следующих D строках заданы описания встреч. Каждое описание встречи состоит из трех
чисел A_i, B_i и T_i (1 ≤ A_i, B_i ≤ N, 1 ≤ T_i ≤ 10⁹) — пара номеров сотрудников и время встречи.

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

Примеры

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

Деревья Обход в глубину

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

Сортировка точек#38689

Выведите все исходные точки в порядке возрастания их расстояний от начала координат.

Создайте структуру Point и сохраните исходные данные в массиве структур Point.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 10³.

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

Примеры

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

Использование сортировки Структуры Элементарная геометрия

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

Метро Давилона#38655

Давилон - самый крупный город на Луне. На Давилоне есть собственная система метро, состоящая из N станций и M железнодорожных линий. Станции пронумерованы от 1 до N. Каждой линией управляет компания. У каждой компании есть идентификационный номер. I-я (1<=i<=M) линия соединяет станцию pi и qi двунаправленно. Промежуточной станции нет. Этой линией управляет компания ci . Можно делать пересадки на станции, где доступно несколько линий. Система оплаты проезда, используемая в этой системе метро, немного странная. Когда пассажир использует только те линии, которые обслуживаются одной и той же компанией, тариф составляет 1 сантик (валюта Давилона). Каждый раз, когда пассажир переходит на линию, которой управляет компания, отличная от текущей линии, с пассажира взимается дополнительная плата за проезд в размере 1 сантик. В случае, если пассажир, перешедший с линии компании А на линию другой компании, снова переходит на линию компании А, дополнительный тариф взимается снова. Незнайка сейчас на станции 1 и хочет добраться до станции N на метро. Найдите минимально необходимый тариф.

Входные данные
В первой строке задается два целых числа N (2<=N<=10⁵) и M (0<=M<=2*10⁵). В каждой из следующих M строк записаны по 3 числа: pi, qi и ci; 1<=pi<=N (1<=i<=M), 1<=qi<=N, 1<=ci<=10⁶, pi ≠ qi.

Выходные данные
Выведите минимальный требуемый тариф. Если добраться до станции N на метро невозможно, выведите -1.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 1 2 1 2 3 1 3 1 2	1	Используйте линии компании 1: 1 → 2 → 3. Стоимость проезда 1 сантик.
2	8 11 1 3 1 1 4 2 2 3 1 2 5 1 3 4 3 3 6 3 3 7 3 4 8 4 5 6 1 6 7 5 7 8 5	2	Сначала используйте линии компании 1: 1 → 3 → 2 → 5 → 6. Затем используйте линии компании 5: 6 → 7 → 8. Стоимость проезда 2 сантика.
3	2 0	-1

Алгоритмы на графах Кратчайшие пути в графе

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

Числовые печеньки - 2#38634

У Громозеки N печенек. На i-й (1<=i<=N) печеньке написано целое число xi. Он выбирает одну или несколько из этих печенек, так чтобы среднее значение целых чисел, записанных на выбранных печеньках, было равно А.
Какими способами он может сделать свой выбор?

Входные данные
В первой строке вводятся два целых числа N (1<=N<=50) и A (1<=A<=50). Во второй строке N целых чисел - xi (1<=xi<=50).

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

Примеры

№	Входные данные	Выходные данные	Примечение
1	4 8 7 9 8 9	5	Ниже приведены 5 способов выбрать печеньки так, чтобы в среднем было 8. 1) Выберите 3-ю печеньку. 2) Выберите 1-ю и 2-ю печеньки. 3) Выберите 1-ю и 4-ю печеньки. 4) Выберите 1-ю, 2-ю и 3-ю печеньки. 5) Выберите 1-ю, 3-ю и 4-ю печеньки.
2	3 8 6 6 9	0
3	8 5 3 6 2 8 7 6 5 9	19
4	33 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3	8589934591	Ответ может не соответствовать 32-битному целому числу.

Динамическое программирование Комбинаторика

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

Издевательство#38632

Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
- Издевается! - подумал Борман.
- Кольцевая! - догадался Штирлиц.

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

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

Входные данные
В первой строке задается число N (3 <= N <= 100). В последующих строках содержится матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

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

Примеры

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

Простые задачи на перебор Способы задания графа

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

Генератор#38624

Даны два натуральных числа N и K. Требуется вывести все цепочки x₁, x₂, ..., x_N такие, что xi - натуральное и 1 ≤ x_i ≤ K.

Входные данные
Вводятся два натуральных числа N и K (N, K ≤ 6).

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

Примеры

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

Размещения с повторениями Разные комбинаторные структуры

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

Симпатичные узоры#38607

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узоров из черных и белых плиток, каждая из которых имеет размер 1 х 1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника N х M метров. Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во-первых, каждый новый клиент, очевидно, захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во-вторых, этот узор должен быть симпатичным.

Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2 х 2 метра, полностью покрытого плитками одного цвета. Для составления финансового плана директору Васе необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!

Входные данные
Вводятся два положительных целых числа N и M (1 ≤ N · M ≤ 30).

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

Примеры

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

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

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

Две кнопки#38583

Алиса и Боб управляют роботом. У каждого из них есть по одной кнопке, которая управляет роботом. Алиса начала удерживать кнопку через A секунд после запуска робота и отпустила кнопку через B секунд после запуска. Боб начал удерживать кнопку через C секунд после запуска и отпустил кнопку через D секунд после запуска. Сколько секунд Алиса и Боб удерживали свои кнопки одновременно?

Входные данные
На вход 4 целых числа: A, B, C и D (\(1<=A<B<=100\), \(1<=C<D<=100\)).

Выходные данные
Выведите продолжительность времени (в секундах), в течение которого Алиса и Боб удерживали свои кнопки одновременно.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	0 75 25 100	50	Алиса начала удерживать кнопку через 0 секунд после запуска робота и отпустила ее через 75 секунд после запуска. Боб начал удерживать кнопку через 25 секунд после запуска и отпустил ее через 100 секунд после запуска. Следовательно, время, когда они оба удерживали свои кнопки, составляет 50 секунд от 25 секунд после запуска до 75 секунд после запуска.
2	0 33 66 99	0	Алиса и Боб не удерживали кнопки одновременно, поэтому ответ - ноль секунд.
3	10 90 20 80	60

Отрезки Пересечение множеств

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

"Сортировка" с конфеткой#38576

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

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

Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.

Входные данные
Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.

1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.

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

Примеры

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

Задачи на моделирование Сортировка "пузырьком"

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

Построение#38569

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

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

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

Входные данные
Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны.

Выходные данные
В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений.

Примеры

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

Обход в глубину Топологическая сортировка

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

Пожиратель карт#38535

Ушан решил сыграть в карточную игру. У него есть колода, состоящая из N съедобных карт. На i-й карте сверху написано целое число A_i. Ушан выполняет описанную ниже операцию ноль или более раз, так что значения, записанные на оставшихся карточках, будут попарно различны.
Найдите максимально возможное количество оставшихся карт. Здесь N нечетное, что гарантирует сохранение хотя бы одной карты.
Операция: вынуть из колоды три произвольные карты. Из этих трех карт съешьте две: одну с наибольшим значением, а другую с наименьшим значением. Затем верните оставшуюся одну карту в колоду.

Входные данные
В первой строке записано нечетное число N (\(3<=N<=10^5\)). Во второй строке записаны N чисел A_i(\(1<=A_i<=10^5\))

Выходные данные
Выведите максимально возможное количество оставшихся карт.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	5 1 2 1 3 7	3	Оптимальное решение - выполнить операцию один раз, вынув две карты с 1 и одну карту с 2. Одна карта с 1 и другая с 2 будут съедены, а оставшаяся карта с 1 будет возвращена в колоду. Тогда значения, написанные на оставшихся картах в колоде, будут попарно различными: 1, 3 и 7.
2	15 1 3 5 2 1 3 2 8 8 6 2 6 11 1 1	7

Конструктив Сортировка подсчетом

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

Чет-нечет#38474

Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите N-й элемент этой последовательности.

Входные данные
Одно целое число N (1 ≤ N ≤ 10¹⁰⁰).

Выходные данные
Выведите одно целое число - N-й элемент последовательности.

Примеры

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

"Длинная" арифметика Бинарный поиск по ответу

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

Взвешивание камней#38473

Джек нашел N камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий ≤ 2 и так далее, самый тяжелый получил номер N.

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

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

Входные данные
Первая строка содержит целое число N (1 N ≤ 100000).

Каждая из следующих N строк содержит по два целых числа: R (1 ≤ R ≤ N) и S (1 ≤ S ≤ 2). R - номер камня, который будет положен на чашу S. Все R будут различны.

Выходные данные
Выведите N строк - по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 1 2 1 4 2 5 1	< > > ? >

Алгоритмы сортировки Дерево отрезков, RSQ, RMQ Жадный алгоритм

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

Agar.io#38466

В многопользовательской игре Agar.io игроки управляют бактериями. У каждой бактерии есть размер — целое положительное число. Если встречаются две бактерии разного размера, то бактерия большего размера поглощает меньшую бактерию. При этом меньшая бактерия исчезает, а размер большей бактерии увеличивается на размер меньшей бактерии. Если встречаются две бактерии равного размера, то ничего не происходит. Побеждает игрок, чья бактерия останется на игровом
поле одна.
В игре участвуют n игроков, вам даны размеры их бактерий. Определите, какие из игроков имеют возможность выиграть в этой игре.

Формат входных данных
Программа получает на вход целое число n, 1 ≤ n ≤ 10⁵ — количество игроков. Следующие n строк содержат по одному числу a_i — размеры бактерий, 1 ≤ a_i ≤ 10⁹. Числа a_i заданы в порядке неубывания.
Формат выходных данных
Программа должна вывести n чисел равных «0» или «1», по одному числу в строке. Если i-е число равно 0, то это означает, что i-й игрок (размер бактерии которого первоначально был равен
a_i) ни при каких обстоятельствах не может выиграть в этой игре. Если i-е число равно 1, то это означает, что i-й игрок имеет возможность выиграть в этой игре.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 1 3 4	0 0 1 1	В примере из условия 4 бактерии размерами 1, 1, 3, 4. Бактерии размером 1 никого не могут съесть, поэтому не могут выиграть. Бактерия размером 4 может съесть всех. Бактерия размером 3 может съесть по очереди две бактерии размером 1. Тогда её размер станет 5, после этого она сможет съесть бактерию размером 4 и выиграть. Ответ: 0, 0, 1, 1.

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

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