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

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

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

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

Громозека и Алиса - 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средняяВойти и решать

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

Порядочные числа#38953

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

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

Миша настолько любит этот процесс, что он даже заменяет ему счёт овец, когда долго не получается заснуть. Он помнит, что вчера ночью, когда он в уме привёл в порядок число A, у него получилось число B. Но вот беда — он не помнит, какое именно он взял число A! Помогите ему в отыскании этого числа.

Входные данные
На ввод подаётся единственное целое число B (1 ≤ B ≤ 10⁹ )

Выходные данные
Если существует такое число A, что после приведения его в порядок, получается B, то выведите любое такое число. Если же Миша где-то ошибся в расчётах и такого числа не существует, то выведите -1.

Примеры

№	Входные данные	Выходные данные
1	42	29
2	20	-1

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

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

Объединенная армия#38867

Для борьбы с могучими рейнджерами Рита Репульса и Лорд Зедд решили объединить Глиняный и Зедд патрули. Для более эффективного нападения на Энджел Гроув они хотят построить свою армию в две шеренги. Количество солдат в первой шеренге равно количеству солдат во второй.
Рита любит два вопроса:

«Правда ли, что ровно x из твоих соседей из Зедд патруля?»
«Правда ли, что ровно y из твоих соседей из Глиняного патруля?»

Соседями в данном построении являются солдаты слева и справа в той же шеренге, а также солдат, который стоит на той же позиции, но в другой шеренге. Рита выбрала либо один из этих вопросов либо оба, и задала каждому солдату. Всем солдатам были заданы вопросы с одними и теми же значениями x и/или y.
Зордан с помощью своей магической силы все это время наблюдал за процессом построения. Он был очень удивлен тем, что ответы всех солдат были положительными. Однако, он помнит, что солдаты из Зедд патруля всегда говорят правду, а солдаты из Глиняного патруля обязательно солгут хотя бы на один вопрос.
Так как солдаты из Зедд патруля наиболее опасны по мнению Зордана, исходя из ответов, он хочет узнать какое наименьшее и наибольшее количество солдат из Зедд патруля могло быть в объединенной армии. Он обратился к вам за помощью!

Входные данные
В единственной строке входного файла содержатся три целых числа k, x, y — количество солдат в одной шеренге и числа из вопросов (1 ≤ k ≤ 10⁵; -1 ≤ x, y ≤ 3).
Если x = -1, это означает, что Рита не задавала первый вопрос.
Если y = -1, это означает, что Рита не задавала второй вопрос.
Гарантируется, что Рита задала хотя бы один вопрос.

Выходные данные
Если для данных k, x и y не существует ни одного способа построения, выведите -1.
Иначе, первая строка выходного файла должна содержать одно число — наименьшее возможное количество солдат из Зедд патруля в армии.
В следующих двух строках должно содержаться по k символов «0» и «1» — описание шеренг:

«0» означает, что в построении на соответствующей позиции стоит солдат из Глиняного патруля.
«1» — солдат из Зедд патруля.

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

Примеры

№	Входные данные	Выходные данные
1	2 0 -1	2 01 10 2 01 10
2	5 1 2	0 00000 00000 4 01010 01010
3	1 2 2	0 0 0 0 0 0
4	10 0 3	5 0100010010 0001000100 8 0101010100 0010101010

битмаски Динамическое программирование Задача на реализацию

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

Экспресс тест#38798

В данной задаче вам предлагается автоматизировать оценку результата экспресс теста.
Вам дана двухцветная картинка размером 10×20. Для обозначения цветов используются символы «#» и «.». Тест
считается отрицательным, если на картинке изображена одна вертикальная полоска и положительным, если три. В любом
другом случае тест считается испорченным.
Полоской будем считать область картинки 10×k, состоящую из символов «#», где k может быть произвольным. При этом
все соседние клетки с этой областью должны быть «.». Полоска может находиться на границе картинки.

Входные данные
В первой строке входных данных задано число t - число тестов (1 ≤ t ≤ 30). В следующих t⋅10+(t−1) строках заданы картинки
тестов. Соседние картинки разделены пустыми строками. После последней картинки, пустой строки нет.
Каждая картинка состоит из 10 строк по 20 символов, каждый из которых либо «#», либо «.».

Выходные данные
Для каждой картинки выведите результат теста в отдельной строке:
Negative - если тест отрицательный;
Positive - если тест положительный;
Incorrect - если тест испорчен.

Примеры

№	Входные данные	Выходные данные
1	4 .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........#.......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..##......#.....###. ..##......#.....###. ..##......#.....###. ..##......#.....###. ..#.......#.....###. ..#.......#.....###. ..##......#.....###. ..#.......#.....###.	Negative Incorrect Positive Incorrect

№

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

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

4
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........

.........##.........
.........##.........
.........##.........
.........#..........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........

..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.

..#.......#.....###.
..#.......#.....###.
..##......#.....###.
..##......#.....###.
..##......#.....###.
..##......#.....###.
..#.......#.....###.
..#.......#.....###.
..##......#.....###.
..#.......#.....###.

Negative
Incorrect
Positive
Incorrect

Алгоритмы обработки Задача на реализацию Задачи на моделирование

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

Лазерная пушка#38774

У игрока в космической стрелялке есть очень мощная лазерная пушка. Но она неподвижна и может стрелять только в одном направлении. Игрок может расставить на игровом поле двусторонние зеркала, меняющие ход луча, чтобы поражать врагов. Введём декартову систему координат с центром, где расположена пушка, то есть пушка имеет координаты (0; 0). Пушка стреляет в направлении точки (1; 1). Игрок может поставить зеркала в точках с целочисленными координатами. Зеркала могут быть горизонтальными или вертикальными, попадание луча в зеркало меняет траекторию луча по законам отражения света. Некоторые возможные варианты отражения луча от зеркала изображены на рисунке.

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

Входные данные
Программа получает на вход два целых числа X и Y , не превосходящих по модулю 10000, записанные в разных строках — координаты цели. Точка (X; Y) не совпадает с началом координат.

Выходные данные
Программа должна вывести в первой строке число N — необходимое количество зеркал. Следующие N строк должны содержать информацию о каждом зеркале. В i-й строке должны быть записаны через пробелы два целых числа xi и yi и один символ ti , обозначающие координаты (xi ; yi) точки, в которых установлено i-е зеркало, и тип этого зеркала ti . Если ti является символом «V», то i-е зеркало размещено вертикально, если же ti является символом «H», то зеркало размещено горизонтально. Например, строка «-2 5 H» обозначает горизонтальное зеркало в точке (−2; 5). Зеркала можно выводить в любом порядке. Зеркало нельзя размещать в точке (0; 0), также нельзя размещать два зеркала в одной точке. Значения xi и yi не должны по модулю превосходить 100 000. Также, разумеется, нельзя допустить, чтобы отражённый луч попал в пушку. Если вариантов ответа несколько, выведите любой из них. Если поразить цель в соответствии с условиями задачи невозможно, программа должна вывести одно число «-1». Если для поражения цели зеркала не нужны, программа должна вывести одно число «0»

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1	1 3 3 H

Задача на реализацию Разбор случаев Элементарная геометрия

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

Цифры в умножении#38581

Дано целое число N (\(1<=N<=10^{10}\)).
Для двух положительных целых чисел A и B определим \(F (A, B)\) как большее из двух:
- количество цифр в десятичной записи числа A;
- количество цифр в десятичной записи числа B.
Например, \(F (3,11) = 2\), поскольку 3 состоит из одной цифры, а 11 - из двух.
Найдите минимальное значение \(F (A, B)\) среди всех пар положительных целых чисел A и B, таких что \(N = A \cdot B\).

Входные данные
На вход подается целое число N (\(1<=N<=10^{10}\)).

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10000	3	\(F(A,B) \) имеет минимальное значение при \((A,B)=(100,100)\).
2	1000003	7	Есть две пары `A` и `B`, таких чтобы выполнялость условие задачи: \((1,1000003)\) и \((1000003,1)\). Для этих пар, `\(F(1,1000003)=F(1000003,1)=7\)`.
3	9876543210	6

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

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

Квест#38479

Новый квест, в котором участники должны выбраться с территории проведения, представляет собой прямоугольник из N × M комнат. Каждая комната имеет четыре двери, ведущие в соседние комнаты, из комнат на краю прямоугольника двери ведут наружу, через эти двери можно
покинуть территорию проведения квеста.
В начале квеста в каждой комнате находится по человеку, а все двери заперты. После начала квеста организаторы дистанционно открывают в каждой комнате запирающий механизм одной из четырёх дверей. Теперь человек, находящийся в этой комнате, может открыть эту дверь и перейти
в соседнюю комнату, через другие три двери выйти из этой комнаты нельзя. При этом может оказаться так, что дверь, соединяющая две комнаты, будет отпираться только с одной стороны, тогда пройти через эту дверь можно только с той стороны, с которой она будет открываться, проходить
через дверь в обратном направлении нельзя, если в соседней комнате будет отперта не эта дверь, а какая-то другая. Если комната находится на краю территории и из этой комнаты открыта дверь наружу, то, пройдя через эту дверь, участник навсегда покидает территорию квеста.
После начала квеста и отпирания дверей участники начинают перемещаться между комнатами. Каждый участник перемещается в соседнюю открытую комнату и продолжает перемещаться до тех пор, пока не покинет территорию квеста. Однако возможна ситуация, когда некоторые участники будут бесконечно перемещаться между комнатами и никогда не выйдут наружу.
Разработчики квеста попросили Вас составить такой план отпирания дверей, при котором ровно K человек смогут выбраться наружу с территории квеста.
Входные данные
Программа получает на вход три числа N, M, K, 1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ K ≤ NM. N и M – количество строк и столбцов в прямоугольном плане квеста, K – количество человек, которые должны выйти из квеста.
Выходные данные
Программа должна вывести план территории квеста в виде N строк, каждая из которых должна содержать M символов. Символ соответствует тому, какая дверь будет открыта в данной комнате и может быть одной из следующих заглавных английских букв: U (дверь в верхнюю по данному плану комнату), D (дверь в нижнюю комнату), L (дверь в левую комнату), R (дверь в правую комнату). Необходимо вывести один любой подходящий план решения задачи. Если ни одного подходящего плана не существует, программа должна вывести одну строчку «IMPOSSIBLE».».

Примеры

№	Входные данные	Выходные данные	Пояснение
1	1 2 1	IMPOSSIBLE	Территория квеста состоит из 1 строки и 2 столбцов. При любом способе открытия дверей из квеста не сможет выбраться ровно один человек.
2	3 4 5	RDLD ULUR DURU	Территория квеста состоит из 3 строк и 4 столбцов. Из квеста должны выйти 5 человек. На рисунке ниже приведена картинка, соответствующая ответу из примера. Стрелками обозначены открытые двери, точками помечены комнаты, обитатели которых выйдут из квеста.

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

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

38458#38458

Количество конструкторов, которые может определить класс, равно?
A) 1
B) 2
C) Любое число
D) Ни один из упомянутых

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

1 100труднаяВойти и решать

Перевернутые родословные#38385

Учёный Иван Иванович изучает перевёрнутые родословные. Перевёрнутая родословная представляет собой набор людей, про каждого из которых известны либо оба его родителя, либо не известен ни один родитель. Кроме того, известно, что у всех людей из родословной есть ровно один
ребёнок, кроме одного человека, у которого детей вовсе нет. Поэтому, если пронумеровать людей целыми числами от 1 до n, то можно обозначить за s_i номер ребёнка человека с номером i и сказать, что s_i = 0 в случае, если у человека с номером i детей нет.
Будем считать, что человек a входит в родословную человека b, если либо a = b, либо если у b известны родители, и a входит в родословную одного из родителей b.

Будем считать, что произошёл перекос родословной с участием некоторого человека, если известны оба его родителя и количество людей в родословной одного из его родителей хотя бы вдвое больше, чем количество людей в родословной второго родителя.
Иван Иванович посчитал количество перекосов родословной и получил число k, но, конечно же, он делал это вручную и мог ошибиться. Помогите проверить Ивану Ивановичу его вычисления: по числам n и k скажите, существует ли родословная из n людей с k перекосами, и если существует, то приведите пример подобной родословной.

Формат входных данных
В единственной строке заданы два целых числа n и k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — количество людей в родословной и количество перекосов в ней.

Формат выходных данных
В первой строке выведите «YES» (без кавычек), если существует родословная с n людьми и k перекосами, и «NO» (без кавычек) в противном случае.
Если требуемая родословная существует, то во второй строке выведите n целых чисел s1, s2, . . . , sn (0 ≤ s_i ≤ n), задающих номера детей каждого из n человек в родословной. Если искомых родословных несколько, выведите любую.

Примеры

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

Замечание

В первом примере подойдет единственная родословная, которую можно составить из трёх человек (человек и два его родителя).

Во втором примере подойдет следующая родословная:

В этом случае в родословную человека 1 входят пять человек (люди 1, 2, 3, 4, 5), в родословную человека 2 входит один человек (только 2), в родословную человека 3 входят три человека (3, 4, 5), в родословную человека 4 входит один человек (только 4) и в родословную человека 5 входит один
человек (только 5). В этом случае происходит перекос родословной в человеке 1.
В третьем примере можно показать, что не существует родословной из трёх людей с двумя перекосами.

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

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

Подготовка к экзамену#38383

Среди открытого банка задач ЕГЭ по математике есть следующая: по заданным натуральным числам l, r и m вас просят найти целые числа a, b и c, каждое из которых не меньше l и не больше r, и такие, что будет существовать натуральное число n (целое число, большее нуля) такое, что
n · a + b − c = m.
Паша еще только начал готовиться к ЕГЭ и не совсем понимает, как решать подобную задачу. Помогите ему для разных вариантов этой задачи находить подходящие a, b и c.

Формат входных данных
В единственной строке заданы три целых числа l, r и m (1 ≤ l ≤ r ≤ 500 000, 1 ≤ m ≤ 1010).

Формат выходных данных
Выведите три целых числа a, b и c такие, что l ≤ a, b, c ≤ r и существует такое натуральное число n, что n · a + b − c = m. Гарантируется, что такие числа существуют. Если подходящих решений несколько, выведите любое из них.

Примеры

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

Замечание
В первом примере можно выбрать n = 3, тогда n · 4 + 6 − 5 = 13 = m. Так же возможны такие ответы: a = 4, b = 5, c = 4 (при этом n = 3); a = 5, b = 4, c = 6 (при этом n = 3); a = 6, b = 6, c = 5 (при этом n = 2); a = 6, b = 5, c = 4 (при этом n = 2).
Во втором примере n = 1, тогда n · 2 + 2 − 3 = 1 = m. Число n = 0 не могло быть выбрано, так как число n обязательно должно быть натуральным.

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

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

Ирригация#38380

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

Как известно, любому таланту надо дать возможность реализоваться, поэтому мама Миши отправила сына на инновационную олимпиаду по ирригации (ИОИ). На этой олимпиаде школьники со всех концов Берляндии соревнуются в умении доставить воду для поливки растений самыми причудливыми способами. Зная список изобретений Миши, несложно догадаться, что проведение подобной олимпиады весьма затратно, поэтому спустя n первых проведений олимпиады было решено ввести правило, по которому будет определяться место проведения соревнования в следующий год. Город для проведения олимпиады выбирается следующим образом: всего в Берляндии есть m городов, пронумерованных от 1 до m, готовых принять соревнование. Каждый год олимпиада проводится в городе, в котором она проводилась наименьшее число раз. Если таких городов несколько, то олимпиада проводится в городе с наименьшим номером среди городов с минимальным числом проведений олимпиады.

Мишина мама очень волнуется за сына, поэтому её интересует, в каком городе будет проходить олимпиада в определённые годы. Единственная информация, которой располагает мама Миши, — места проведения олимпиады в первые n лет. Помогите маме Миши, и она попросит Мишу не залить вашу квартиру.

Входные данные
В первой строке заданы три целых числа n, m и q (1 ≤ n, m ≤ 500000 , 1 ≤ q ≤ 20) — количество проведений олимпиады до введения правила, количество городов в Берляндии, готовых провести олимпиаду, и число лет, про которые маму Миши интересует место проведения олимпиады, соответственно.

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

В следующих q строках заданы целые числа k_i (n+1 ≤ k_i ≤ 10¹⁸) — номера годов, для которых маму Миши интересует место проведения олимпиады.

Выходные данные
Выведите q целых чисел. В строке с номером i выведите одно целое число — место проведения олимпиады в год k_i.

Примеры

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

Задача на реализацию математика реализация

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

Разделение числа#38379

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

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

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

Входные данные
Первая строка содержит одно целое число l (2 ≤ l ≤ 100000) — длину любимого числа Димы.

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

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

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

Примечание
В первом примере Дима может разрезать число 1234567 на числа 1234 и 567. Их сумма равна 1801.

Во втором примере Дима может разрезать число 101 на числа 10 и 1. Их сумма равна 11.

Примеры

№	Входные данные	Выходные данные
1	7 1234567	1801
2	3 101	11

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

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

Гирьки#38340

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

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

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

Программа получает на вход натуральное число N (2 ≤ N ≤ 10⁸) – максимально допустимую массу ювелирного изделия.

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

Если задача имеет множество решений, необходимо вывести любое из них.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3	2	Пусть x – изделие, массу которого необходимо определить. Нужно на одну чашу весов положить x, а на другую чашу весов – гирьку в 2. Если x будет легче, то x = 1, при равенстве – x = 2, если x тяжелее, то x = 3.
2	5	3 4	Покажем, как при помощи гирек в 3 и 4 определить все массы от 1 до 5. Массы 3 и 4 можно определить при помощи равенств x = 3 и x = 4. Массу 1 можно определить при помощи равенства x + 3 = 4 (на одну чашу кладется изделие и гирька массой 3, на другую чашу – гирька массой 4). Массу 2 можно определить, например, по условию x < 3 (на одну чашу весов кладется изделие, на другую – гирька массой 3), а также проверив при помощи ранее описанного алгоритма, что x ≠ 1 . Массу 5 можно определить при помощи взвешивания x > 4.

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

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

ASCII-графика#38284

Давным-давно большинство персональных компьютеров были оборудованы видеокартами, работавшими только в текстовом режиме. Если программист хотел изобразить картинку на экране, ему приходилось использовать псевдографику или ASCII-графику. Вот пример картинки, нарисованный с ее помощью:

^..^
(OO)
/  \
()()

Вам дан многоугольник, нарисованный с помощью ASCII-графики. Ваша задача состоит в том, чтобы посчитать количество его сторон.
Картинка состоит из символов ‘.’, ‘\’ и ‘/’. Каждый символ изображает единичный квадрат картинки. Символ ‘.’ обозначает пустой квадрат, символ ‘/’ — квадрат с отрезком из левого нижнего угла в правый верхний, а символ ‘\’ — квадрат с отрезком из левого верхнего угла в правый нижний.

Входные данные
Первая строка входных данных содержит два числа h и w — высота и ширина изображения (2 ? h, w ? 100). Следующие h строк, по w символов в каждой, содержат описание многоугольника, нарисованного с помощью ASCII-графики.
Гарантируется, что картинка содержит ровно один многоугольник, не имеющий самопересечений и самокасаний.

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

Примеры

№	Входные данные	Выходные данные
1	4 4 /\/\ \../ .\.\ ..\/	8

Задача на реализацию Элементарная геометрия

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

Свойства объектов - 1#37887

В хранилище Васи находится n объектов, пронумерованных от 1 до n, у каждого из которых есть некоторое количество свойств (возможно, ни одного). Каждое свойство представлено в виде натурального числа от 1 до 10⁹.
Проанализировав устройство своего хранилища, Вася решил, что оно должно поддерживать две операции:
- Удаление устаревшего свойства c. При удалении свойства, оно удаляется у всех объектов, которым принадлежит.
Если указанного свойства не существует, ничего делать не нужно.
- Найти количество оставшихся свойств у объекта с номером r.
Васе очень нужно реализовать эту функциональность, и он обратился к вам за помощью. Помогите ему - напишите программу, которая будет поддерживать обе операции, нужные Васе.

Формат входных данных
В первой строке входного файле содержится число n - количество объектов в хранилище Васи (1 <= n <= 10⁵). В i-й из следующих n строк содержится описание свойств объекта с номером i: сначала дано число ki - количество свойств у i-го объекта, а затем через пробел даны ki чисел pi,j - свойства i-го объекта (0 <= k_i <= 100, 1 <= p_i,j <= 10⁹).
Все объекты пронумерованы от 1 до n в порядке, представленном во входных данных. Гарантируется, что общее количество свойств у всех объектов не превосходит 10⁵. Также гарантируется, что для каждого i все pi,j различны.
В n + 2 строке содержится число q - количество запросов к хранилищу Васи (1 <= q <= 10⁵).
В j-й из следующих q строк содержится информация об j-м запросе:
- c, если из хранилища требуется удалить устаревшее свойство c (1 <= c <= 10⁹);
? r, если требуется найти количество оставшихся свойств у объекта с номером r.

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

Ввод	Вывод
2 3 1 2 4 3 2 3 5 12 - 1 ? 1 ? 2 - 2 ? 1 ? 2 - 5 ? 1 ? 2 - 6 ? 1 ? 2	2 3 1 2 1 1 1 1

Замечание
Свойство 1 есть только у первого объекта, поэтому после его удаления у первого объекта остается 2 свойства, а у второго все еще 3.
Свойство 2 есть у обоих объектов, поэтому оно удаляется у обоих объектов, у первого объекта остается 1 свойство, а у второго - 2.
Свойство 5 есть только у второго объекта, поэтому после его удаления у обоих объектов остается 1 свойство.
Свойства 6 нет ни у одного объекта, поэтому его удаление не меняет количество свойств у объектов.

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

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

Свойства объектов - 2#37886

В хранилище Васи находится n объектов, пронумерованных от 1 до n, у каждого из которых есть некоторое количество свойств (возможно, ни одного). Каждое свойство представлено в виде натурального числа от 1 до 10⁹.
Проанализировав устройство своего хранилища, Вася решил, что оно должно поддерживать две операции:
- Удаление устаревшего свойства c. При удалении свойства, оно удаляется у всех объектов, которым принадлежит. Если указанного свойства не существует, ничего делать не нужно.
- Найти количество удаленных свойств у объекта r
Васе очень нужно реализовать эту функциональность, и он обратился к вам за помощью. Помогите ему - напишите программу, которая будет поддерживать обе операции, нужные Васе.

Формат входных данных
В первой строке входного файле содержится число n - количество объектов в хранилище Васи (1 <= n <= 10⁵). В i-й из следующих n строк содержится описание свойств объекта с номером i: сначала дано число k_i - количество свойств у i-го объекта, а затем через пробел даны k_i чисел pi,j - свойства i-го объекта (0 <= k_i <= 100, 1 <= p_i,j <= 10⁹).
Все объекты пронумерованы от 1 до n в порядке, представленном во входных данных. Гарантируется, что общее количество свойств у всех объектов не превосходит 10⁵. Также гарантируется, что для каждого i все pi,j различны.
В n + 2 строке содержится число q - количество запросов к хранилищу Васи (1 <= q <= 10⁵).
В j-й из следующих q строк содержится информация об j-м запросе:
- c, если из хранилища требуется удалить устаревшее свойство c (1 <= c <= 10⁹);
? r, если требуется найти количество оставшихся свойств у объекта с номером r.

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

Ввод	Вывод
2 3 1 2 4 3 2 3 5 12 - 1 ? 1 ? 2 - 2 ? 1 ? 2 - 5 ? 1 ? 2 - 6 ? 1 ? 2	1 0 2 1 2 2 2 2

Замечание
Свойство 1 есть только у первого объекта, поэтому после его удаления у первого объекта 1 удаленное свойство, а у второго все еще 0.
Свойство 2 есть у обоих объектов, поэтому оно удаляется у обоих объектов, у первого объекта теперь 2 удаленных свойства, а у второго 1.
Свойство 5 есть только у второго объекта, поэтому после его удаления у обоих объектов становится 2 удаленных свойства.
Свойства 6 нет ни у одного объекта, поэтому его удаление не меняет количество удаленных свойств у объектов.

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

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