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

21946#21946

Графическое изображение, показывающее соотношение каких-либо величин называется

1. графиком
2. таблицей
3. картинкой
4. диаграммой

Комбинаторика

1 000средняяВойти и решать

Магические порталы#21903

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

Из-за свойств магии, определяющей работу порталов, каждый портал можно использовать только в одну сторону. Для каждой пары городов A и B известно, можно ли воспользоваться порталом для перемещения напрямую из A в B или из B в A.

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

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

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

Для получения этой информации король планирует запросить в министерстве транспорта соответствующий отчет. Король может запросить либо частичный, либо полный отчет. Содержимое отчета зависит от параметра L, для частичного отчета L = k + 1, для полного отчета L = 1.

Отчет содержит для каждого целого числа m, такого что m ≥ L, число таких пар городов A и B, для которых выполняются следующие условия:
- исходно магический портал позволяет перемещаться напрямую из города A в город B;
- если изменить направление перемещения этого магического портала на противоположное, чтобы он позволял напрямую перемещаться из города B в город A, то количество совершенных городов в королевстве станет равным m.

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

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

Формат входного файла
Первая строка входного файла содержит два целых числа: n — количество городов в королевстве (2 ≤ n ≤ 2000) и p, равное либо 0, если требуется вывести частичный отчет, либо 1, если требуется вывести полный отчет. Последующие n строк содержат по n символов, каждый из которых может быть «+», «–» или «.», и i-я из этих строк описывает магические порталы, соединяющие i-й город с другими городами.
В i-й строке j-й символ равен «+», если магический портал позволяет напрямую перемещаться из i-го города в j-й, равен «–», если магический портал позволяет напрямую перемещаться из j-го города в i-й, и равен «.», если i = j.
Формат выходного файла
Первая строка выходного файла должна содержать одно целое число k — количество совершенных городов в королевстве.
Если требуется частичный отчет (p = 0), то вторая строка выходного файла должна содержать (n – k) целых неотрицательных чисел, разделенных пробелами, где i-е из этих чисел должно быть равно количеству пар городов, изменение направления портала между которыми на противоположное приводит к тому, что количество совершенных городов в королевстве станет равным (k + i). Если при этом k = n, то вторая строка может отсутствовать, либо быть пустой.
Если требуется полный отчет (p = 1), то вторая строка должна содержать n целых неотрицательных чисел, разделенных пробелами, где i-е из этих чисел должно быть равно количеству пар городов, изменение направления портала между которыми на противоположное приводит к тому, что количество совершенных городов в королевстве станет равным i.

Пример:

Ввод	Вывод
5 0 .-+++ +.+++ --.+- ---.+ --+-.	1 0 0 0 3
5 1 .-+++ +.+++ --.+- ---.+ --+-.	1 7 0 0 0 3

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

В приведенных примерах изначально совершенным является только город 2.
Изменив направление порталов, соединяющих пары городов (2, 3), (2, 4) или (2, 5), можно сделать все города совершенными. Изменение направление любого другого портала делает совершенным один город.

Алгоритмы на графах Задача на реализацию Циклы

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

Вырубка леса#21901

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

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

Фермер Николай хочет понять, за сколько дней лесорубы срубят все деревья, и он сможет засеять кукурузное поле. Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Входные данные: на вход подаётся пять целых чисел, разделенных пробелами: A, K, B, M и X (\(1 <= A,\ B <= 10^9\) , \(2 <= K,\ M <= 10^{18}\), \(1 <= X <= 10^{18}\)).

Входные данные: выведите одно целое число — искомое количество дней.

Примеры

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

Пояснение к примеру
В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:
- 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
- 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
- 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
- 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
- 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
- 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
- 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.

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

✓ 682✗ 1 746600лёгкаяВойти и решать

21883#21883

Введите с клавиатуры целое число X (|X| ≤ 10⁹).
В первых трех строках выведите это число на экран в двоичной, восьмеричной, 16-ричной системах счисления.
В следующих двух строках выведите, поместится ли это число в ячейке типа byte и ячейке типа short ("YES"/"NO").
Запрещается использовать циклы и знания о том, сколько именно байт/бит памяти занимают переменные типа int, byte, short.
Пример ввода:

123

Пример вывода:

1111011
173
7B
YES
YES

Пример ввода:

40000

Пример вывода:

1001110001000000
116100
9C40
NO
NO

Разные системы счисления Строки Целые числа

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

Вычисление арифметических выражений#21882

Постфиксная запись представляет собой такую запись алгебраического выражения, в которой сначала записываются операнды, а затем – знак операции. Например, для выражения a + b * c постфиксная запись будет a b c * +.

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

Входные данные
На вход подается символьная строка. Знак / в записи означает целочисленное деление.

Выходные данные
Выведите на экран результат выражения.

Примеры

№	Входные данные	Выходные данные
1	5 3 + 7 4 - *	24

Разбор выражений Стек

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

Удаление#21845

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

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

После удаления из последовательности трех элементов все остальные сдвигаются на нужные места. Например, из последовательности {1, 2, 3, 4, 5} можно получить последовательность {2, 4}.

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

В первой строке записано целое число n (4 ≤ n ≤ 10⁶) — количество элементов в исходной последовательности. Во второй строке записаны n разделенных пробелами целых чисел — члены последовательности, разделенные пробелами. Все числа в последовательности по модулю не превышают 10⁹.

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

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

Примеры тестов

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

4
1 2 3 4

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

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

5
1 2 3 4 5

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

-4

Примечание

Тесты разделены на группы, но оцениваются отдельно

n ≤ 81 — 20 баллов
n ≤ 300 — 10 баллов
n ≤ 5000 — 20 баллов
Без дополнительных ограничений — 50 баллов

Динамическое программирование: два параметра

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

Три числа#21843

Вам дано три числа a, b и c. Вы должны в таком порядке приписать эти числа друг к другу, чтобы в результате получилось минимальное число. Например, если a = 12, b = 5, c = 3, приписыванием можно получить числа 1253, 1235, 3125, 3512, 5123, 5312. Минимальным, среди этих чисел является 1235.

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

В первой строке через пробел записаны три целых числа a, b и c (1 ≤ a, b, c ≤ 100).

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

Выведите минимальное число, которое можно получить, приписав a, b и c друг к другу в каком-нибудь порядке.

Примеры тестов

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

12 3 5

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

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

2 21 3

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

Перестановки реализация

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

Твоя игра#21837

В интеллектуальном шоу «Твоя игра» принимают участие 3 человека. Им даются 5 тем, каждая из которых содержит по 5 вопросов стоимостью 100, 200, 300, 400 и 500 баллов. Если игрок правильно отвечает на вопрос, то к его текущей сумме прибавляется стоимость вопроса, если же он допускает ошибку, то от его суммы стоимость вопроса отнимается. При этом у игрока может оказаться отрицательная сумма баллов.

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

Формат входных данных

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

В следующих строках содержится информация о сыгранном вопросе. Сперва идёт имя участника, отвечавшего на вопрос, а через пробел — полученная им сумма баллов. Если количество баллов положительно, то ответ оказался правильным, если же отрицательно, то игрок ошибся. Гарантируется, что разыгранное количество вопросов каждой стоимости (100, 200, 300, 400 и 500) не превосходит 5. Также гарантируется, что во время игры будет разыгран хотя бы один вопрос.

В последней строке находится надпись «GAME OVER», означающая, что игра окончена и больше вопросов не будет.

Формат выходных данных

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

Ввод:

Artur Dmitry Fedor

Artur -500

Dmitry 400

Fedor 100

Artur 400

Fedor 200

Fedor 100

Artur 500

GAME OVER

Вывод:

-500 0 0

-500 400 0

-500 400 100

-100 400 100

-100 400 300

-100 400 400

400 400 400

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

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

Число с максимальным количеством делителей#21834

Напишите функцию, вычисляющую количество делителей числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальным количеством делителей
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно число, в котором количество делителей максимально среди всех чисел, если таких чисел несколько, то необходимо вывести число, которое встретилось в последовательности раньше

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).

Пример

Ввод	Вывод
5 22790 94 66 18 18	22790
2 21 46	21

Алгоритмы обработки Задачи на процедуры и функции Простые числа и разложение на множители

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

Друзья#21825

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

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

В первой строке входного файла INPUT.TXT заданы два числа: N и S (1 <= N <= 100; 1 <= S <= N), где N - количество человек в клубе, а S – номер конкретного человека. В следующих N строках записано по N чисел - матрица смежности, состоящая из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что люди с номерами i и j – друзья, а 0 – выражает неопределенность.

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

В выходной файл OUTPUT.TXT выведите количество гарантированных друзей у человека с номером S, помня о транзитивности дружбы.

Пример

Ввод:

3 1

0 1 0

1 0 1

0 1 0

Вывод
2

графы Поиск компонент связности

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

Z-функция#21824

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

Входные данные
В первой строке вводится k - количество запросов (\(k <= длина( S)\)), строка S и строка T. Далее вводится k запросов, запрос на количество вхождений i-го префикса строки S в строку T.

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

Вывести k строк с ответами на запросы.

Примеры

№	Входные данные	Выходные данные
1	2 ali balimali 3 0	2 8

Z-функция. Префикс-функция

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

Pref-функция#21823

Дана строка S. Найдите сумму значений префикс-функции для всех заданных позиций строки S.

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

В первой строке входного файла записана строка S (\(1 <= |S| <= 150 000\)) и k (количество заданных позиций).

Далее идут k чисел - позиции, значения префикс-функции которых надо сложить.

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

В выходной файл выведите одно число - сумму значений префикс-функции для всех заданных позиций строки S.

Примеры

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

Z-функция. Префикс-функция

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

Крестики-нолики#21821

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

Рассмотрим кратко правила игры. Игра происходит на бесконечном клетчатом поле, два игрока делают ходы по очереди, первый игрок ходит крестиками, а второй — ноликами. В свой ход игрок

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

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

за один ход. Петя называет ход оптимальным, если для этого хода выполнено одно из двух:

• этот ход приводит к немедленной победе Пети;

• не существует хода, который приводит к немедленной победе Пети, но если Петя сделает этот ход, то Вася не выиграет следующим ходом и, вне зависимости от ответного хода Васи, у Пети

будет следующий ход, который приведет к его немедленной победе.

Помогите Пете найти количество оптимальных ходов.

Формат входных данных

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

Следующие n строк содержат по m символов, каждый из которых равен одному из следующих:

«.» (точка), «X» (заглавная латинская буква «икс») или «0» (ноль). При этом «.» обозначает пустую клетку, «X» обозначает крестик, а «0» обозначает нолик. Гарантируется, что на поле находится

равное число крестиков и ноликов, и ни один игрок еще не одержал победу.

Формат выходных данных

Выведите одно число — количество оптимальных ходов Пети.

Примеры

№	Входные данные	Выходные данные
1	5 3 ... 000 XXX ... ...	2
2	4 4 ..0. .XX0 .0X. ....	0
3	5 6 ...... .XXX.. .0000. ..X... ......	0

Двумерные массивы Задача на реализацию Простые игры

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

Преобразование последовательности#21820

Учительница математики очень не любит Колю и всегда заставляет его отвечать у доски самые

сложные задачи.

Вот и сегодня она написала на доске последовательность из n целых неотрицательных чисел

чисел a₁, a₂, . . . , a_n и вызвала Колю к доске. За одно действие учительница разрешает Коле

стереть любое число и на его место записать число на единицу больше. Учительница требует от

Коли за минимальное число действий добиться того, чтобы где-нибудь в этой последовательности

встречались подряд в возрастающем порядке числа от 1 до h.

Помогите Коле понять, за какое минимальное число действий ему удастся добиться того, что для

некоторого i будет выполнено a_i = 1, a_i+1 = 2, . . . , a_i+h−1 = h, или выясните, что это невозможно и

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

Формат входных данных

Первая строка входного файла содержит два натуральных числа: n и h (1 ≤ h ≤ n ≤ 200 000).

Вторая строка содержит n чисел a_i — исходные значения элементов выписанной последовательности

(0 ≤ a_i ≤ n).

Формат выходных данных

В единственной строке выходного файла выведите минимальное количество действий, за которое

Коля сможет выполнить задание, или −1 в случае, если выполнить его невозможно.

Примеры
Ввод

4 3

1 1 0 2
Вывод
3

Ввод

3 2

1 3 2
Вывод
-1

В первом примере Коле надо дважды увеличить на 1 третье число и один раз — четвертое. Тогда

последовательность примет вид 1, 1, 2, 3, для i = 2 выполнено искомое условие.

Во втором примере получить в последовательности подряд 1 и 2 невозможно.

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

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

Регистрация на олимпиаду#21818

Петя и Вася проводят олимпиаду по программированию. На нее пришло так много участников,

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

Для того, чтобы зарегистрироваться, каждый участник называет свои имя, фамилию и отчество,

а Петя и Вася заносят эту информацию в общую электронную таблицу. Так как участников много,

а времени на организацию так мало, Петя и Вася не успели договориться о формате записи данных

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

сначала его фамилию, затем имя, а затем — отчество, а Вася — сначала имя, затем отчество, а

затем — фамилию.

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

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

к следующему виду:

• для всех участников сначала написана фамилия, затем имя, а затем — отчество;

• участники в таблице упорядочены лексикографически по фамилии.

Петя и Вася заметили, что фамилии у всех участников различны, а вот каждое имя встречается

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

участников, аналогично никакие фамилия и отчество не совпадают.

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

Формат входных данных

В первой строке задано число n (2 ≤ n ≤ 1000) — общее число записей в электронной таблице.

Далее, в n строках записано по три слова s_1,i, s_2,i, s_3,i. Каждое из слов содержит от 1 до 20 латинских

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

одной из записей, сделанных Петей или Васей. Слова разделены одним пробелом.

Формат выходных данных

Выведите n строк — электронную таблицу, в которой для каждого участника идет сначала

фамилия, потом имя, потом отчество, причем все записи отсортированы лексикографически.

Лексикографический порядок соответствует порядку в словарях: слова сначала сравниваются

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

алфавите, то это слово лексикографически меньше другого. Если же расхождение так и не найдено,

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

лексикографически меньше.

Пример
Ввод

Ivanov Ivan Ivanovich

Ivan Borisovich Petrov

Sergey Ivanovich Sidorov

Pavlov Sergey Borisovich

Вывод

Ivanov Ivan Ivanovich

Pavlov Sergey Borisovich

Petrov Ivan Borisovich

Sidorov Sergey Ivanovich

Использование сортировки Строки

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

НОД и НОК#21815

Сережа очень любит математические задачи. Недавно на математическом кружке ему рассказали, что такое НОД и НОК.

НОД двух натуральных чисел a и b — это их наибольший общий делитель, то есть такое максимальное число x, что a делится на x и b делится на x. Например, \(НОД(24, 18) = 6\). А НОК целых чисел a и b — это их наименьшее общее кратное, то есть такое минимальное число x, что x делится на a и x делится на b. Например, \(НОК(24, 18) = 72\).

Сережа сразу заметил, что может существовать несколько пар чисел с одинаковыми НОД и НОК. Теперь он заинтересовался вопросом: если заданы числа a и b, насколько близко друг к другу могут быть два числа, у которых такие же НОД и НОК.

Помогите ему по заданным двум числам a и b найти такие числа x и y, что \(НОД(a, b) = НОД(x, y)\), \(НОК(a, b) = НОК(x, y)\), а их разность \(y - x\) минимальна.

Входные данные
В первой строке входного файла находятся два натуральных числа a и b (\(1 <= a, b <= 10^9\)).

Выходные данные
Выведите два натуральных числа x и y (\(1 <= x <= y\)), таких, что \(НОД(a, b) = НОД(x, y)\), \(НОК(a, b) = НОК(x, y)\), а их разность \(y - x\) минимальна.

Примеры

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

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

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

Игра#21814

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

Ребята выяснили, что Петя может закинуть кольцо на столбик только, если высота этого столбика не меньше l₁ и не больше r₁. На слишком высокий или слишком низкий столбик он закинуть кольцо не может. Зато, если столбик имеет подходящую высоту, бросок гарантированно заканчивается успехом. Аналогично, Вася может закинуть кольцо только на столбики с высотой не меньше l₂ и не больше r₂ и гарантированно закидывает кольцо на любой такой столбик.

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

Формат входных данных

В первой строке входного файла находятся два целых числа n и m — количество столбиков и колец, соответственно (1 ≤ m ≤ n ≤ 10⁵). Следующие две строки содержат числа l₁, r₁ и l₂, r₂ — минимальную и максимальную высоту столбиков, на которые могут кидать колечки Петя и Вася, соответственно (1 ≤ l₁ ≤ r₁ ≤ 10⁹, 1 ≤ l₂ ≤ r₂ ≤ 10⁹). В последней строке содержится n чисел, описывающих высоту столбиков, высота каждого столбика является целым положительным числом и не превышает 10⁹.

Формат выходных данных

В выходной файл выведите «Petya», если выиграет Петя, «Vasya», если выиграет Вася, или «Draw», если при оптимальной игре оба мальчика закинут на столбики равное число колец.

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

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

Дюна#21813

Географ Григорий Георгиевич исследует образование песчаных дюн. Он выбрал очень длинную дюну и разбил его на огромное число участков, которые пронумеровал от 1 до 10⁹.

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

Порыв ветра номер i имел силу x_i и действовал на участки с l_i-го по r_i-й. В результате этого порыва высота участка номер l_i увеличилась на xi, высота участка номер l_i + 1 уменьшилась на xi, следующего — снова увеличилась на x_i, и так далее до участка номер r_i, включительно.

Зная всю информацию о всех n порывах ветра, Григорий Георгиевич хочет узнать установившуюся в итоге высоту некоторых интересующих его m участков. Помогите ему.

Формат входных данных

В первой строке входного файла содержатся два натуральных числа n и m (1 ≤ n,m ≤ 1000) — количество порывов ветра и количество участков, итоговая высота которых интересует Григория Георгиевича.

В каждой из следующих n строк содержится описание очередного порыва ветра — три целых числа l_i, r_i, x_i (1 ≤ l_i ≤ r_i ≤ 10⁹; 1 ≤ x_i ≤ 1000).

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

порядке.

Формат выходных данных

Для каждого из m запросов выведите одно целое число — высоту соответствующего участка.

Пример
Ввод:

2 6

1 6 7

3 7 2

8
Вывод

-7

-9

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

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

Завоевание#21812

Лорд Петир собирает армию для похода на соседнее королевство. Он хочет, чтобы в его армию вошли все воины каждого из n городов его королевства. Петир выяснил, что в i-м городе ищут работу a_i воинов, которых он может завербовать в свою армию.

Исходно в армии Лорда нет ни одного воина. Чтобы воин вошел в армию, Петир может заплатить этому воину. Для вербовки одного воина из i-го города, необходимо заплатить ему c_i золотых монет. При этом воины из больших городов ценят свою работу дороже, поэтому если для i-го и j-го города выполнено a_i < a_j , то ci ≤ c_j . Однако есть еще один способ добиться того, чтобы воины присоединились к армии. Если в какой-то момент оказывается, что в армии Лорда Петира уже строго больше воинов, чем осталось в некотором городе, то все воины этого города бесплатно присоединяются к армии Лорда.
Помогите Лорду Петиру выяснить, какое минимальное количество золотых монет он должен заплатить воинам, чтобы все воины из всех городов оказались в его армии.

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

В первой строке входного файла находится целое число n (1 ≤ n ≤ 1000) — количество городов, в которых Лорд Петир намерен набирать себе воинов. В следующих n строках входного файла находится по два целых числа a_i и c_i (1 ≤ a_i ≤ 100, 1 ≤ c_i ≤ 10 000) — количество воинов в i-м городе и число монет, которое необходимо заплатить одному воину в этом городе, чтобы он присоединился к армии. Для всех пар i и j выполнено условие, что если a_i < a_j , то c_i ≤ c_j .

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

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

Примеры

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

В приведенном примере Лорду необходимо действовать следующим образом. Сначала он платит 2 монеты воину из второго города, и 3 монеты воину из третьего города, чтобы они присоединились

к его армии. Теперь в армии Лорда 2 воина, а в городах осталось 1, 1 и 3 воина, соответственно. Воины из первого и второго городов бесплатно присоединяются к армии Лорда Петира, в его армии становится 4 воина, после чего и оставшиеся 3 воина из третьего города бесплатно присоединяются к его армии.

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

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

Шахматы#21811

Кроме школы и математического кружка, Вася ходит на шахматный кружок. Но играть в шахматы на обычной доске 8 × 8 ему кажется не очень интересным. Недавно он придумал свою версию шахмат, в которой игра происходит на доске, имеющей другую форму. Васина доска состоит из n столбцов, i-й из которых содержит ai клеток. Нижние клетки всех столбцов образуют один горизонтальный ряд, причем длины столбцов упорядочены слева направо по невозрастанию. На рисунке ниже приведен пример доски, в которой три столбца, содержащих 5, 2 и 1 клетку, соответственно.

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

Формат входных данных

В первой строке входного файла задано целое число n — количество столбцов доски

(1 ≤ n ≤ 1000). Следущая строка содержит n чисел a1, a2, . . . , an — количество клеток в столбцах

(1 ≤ ai ≤ 1000, a1 ≥ a2 ≥ . . . ≥ an).

Формат выходных данных

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

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

Примеры
Ввод

5 2 1

Вывод

1 5

2 1

Отрезки Разбор случаев реализация

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