Темы
    Информатика(2656 задач)
---> 22 задач <---
Источники --> Личные олимпиады --> Индивидуальная олимпиада по информатике и программированию (ИОИП)
    Заключительный этап 2009(4 задач)
    Заключительный этап 2010(4 задач)
    Заключительный этап 2012(4 задач)
    Заключительный этап 2013(5 задач)
    Заключительный этап 2015(5 задач)
Страница: << 1 2 3 4 5 >> Отображать по:
#111582
Гарри Поттер и Зал Пророчеств
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Отряд Дамблдора готовится к полёту в Отдел Тайн Министерства Магии. Так как на их пути за Пророчеством могут встретиться слуги Волан-де-Морта, Гарри с Невиллом решили потренироваться в дуэльных боях.

Они решили провести \(n\) раундов дуэли, а после каждого раунда выпивать восстанавливающее зелье, чтобы не тратить лишних сил. Всего у ребят \(2n\) зелий. После каждого раунда дуэли они выбирают два наиболее близких по мощности восстанавливающих зелья. Из нескольких таких пар они выбирают ту, у которой сумма мощностей наибольшая. Затем Невилл выпивает более мощное зелье из пары, а Гарри - менее мощное.

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

Формат входного файла

Первая строка входного файла содержит одно целое число \(n\) (\(1 \le n \le 100\,000\)) - количество раундов дуэли. Во второй строке входного файла содержится \(2n\) целых чисел \(a_1, a_2, \ldots, a_{2n}\) (\(1\le a_i \le 10^9\)), где \(a_i\) - мощность \(i\)-го восстанавливающего зелья.

Формат выходного файла

В первой строке выведите \(n\) чисел - мощности зелий, которые выпьет Невилл. Во второй строке выведите \(n\) чисел - мощности зелий, которые выпьет Гарри. Зелья надо выводить в том порядке, в котором Невилл и Гарри должны их выпивать.

Примеры
Входные данные
1
3 6
Выходные данные
6
3
Входные данные
2
11 43 56 22
Выходные данные
22 56
11 43
#111583
Гарри Поттер и битва за Хогвартс
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Наступает решающая битва за Хогвартс. Все \(n\) его обитателей собрались в холле для отражения атак противника. Каждый защитник Хогвартса обладает магической силой, которая представляет собой натуральное число от \(1\) до \(n\). Магические силы всех защитников различны.

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

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

Из предмета <<Основы маггловской информатики>> Гарри знает, что если он сделает \(n-1\) такой проход, все бойцы окажутся расположены в порядке возрастания их магической силы. Однако времени мало, поэтому Гарри успеет сделать только \(k\) таких проходов.

Помогите Гарри узнать, в каком порядке бойцы встретят армию противника.

Формат входного файла

В первой строке входного файла находится целое число \(n\) (\(1 \le n \le 200{\,}000\)) - количество защитников Хогвартса и число \(k\) (\(0 \le k \le n-1\)) - количество проходов, которое успеет сделать Гарри. Во второй строке находится \(n\) чисел \(a_i\) (\(1 \le a_i \le n\)) - магические силы бойцов в изначальном строю в порядке слева направо.

Формат выходного файла

В единственной строке выходного файла выведите \(n\) чисел \(b_i\) - магические силы бойцов в строю после \(k\) проходов Гарри.

Примеры
Входные данные
2 1
1 2
Выходные данные
1 2
Входные данные
3 1
2 3 1
Выходные данные
2 1 3
#112802
Кубики
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
ввод
cubes.in
вывод
cubes.out

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

Всего утята собрали \(n\) башенок. В \(i\)-й башенке оказалось \(a_i\) кубиков, поставленных друг на друга. Скрудж заметил, что башенки имеют разную высоту. Ему, как большому любителю порядка, это не понравилось, и он решил исправить ситуацию. Скрудж решил, что он будет перекладывать, добавлять и убирать кубики так, чтобы все башенки оказались одинаковой высоты. За одно действие Cкрудж может переложить кубик с одной башенки на другую, убрать кубик из конструкции, или взять кубик из набора и положить его на какую-нибудь башенку. Кубиков в наборе неограниченное количество. Высота башенки определяется как количество кубиков в ней.

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

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

В первой строке входного файла даны два числа \(n\) (\(1 \leq n \leq 1000\)) — количество башенок. Во второй строке входного файла дано \(n\) чисел \(a_i\) (\(1 \leq a_i \leq 1000\)) — количество кубиков в \(i\)-й башенке.

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

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

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

cubes.in
5
3 2 2 5 4
cubes.out
3
Система оценивания

В этой задаче 25 тестов, каждый тест оценивается независимо в 4 балла.

#112803
Очередь в банк
  
Очередь в банк
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
longqueue.in
вывод
longqueue.out

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

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

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

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

В первой строке входного файла даны два числа \(n, x\) (\(1 \leq n \leq 100\, 000, 0 \leq x \leq 10^9\)) — начальное количество человек в очереди и нижняя граница хорошего настроения.

В следующей строке даны \(n\) чисел \(a_i\) — настроения людей в очереди (\(0 \leq a_i \leq 10^9\)).

В третьей строке входного файла дано число \(m\) (\(1 \leq m \leq 100\, 000\)) — количество событий, которые происходили с очередью. В следующих \(m\) строках дано описание событий. Событие описывается одним из трех способов:

    • 1 a (0 ≤ a ≤ 109) — в конец очереди приходит человек с настроением, равным a.
    • 2 — из очереди уходит человек, перед которым никого не стоит (в нумерации Скруджа он имеет номер 0). После этого Скрудж мысленно уменьшает номера людей в очереди на 1.
    • 3 i — Скрудж хочет узнать, сколько людей с хорошим настроением стоит перед человеком, перед которым в очереди в этот момент стоит i человек.

Гарантируется, что все запросы корректны: если в очереди никого нет, то операция второго типа не выполняется, а количество человек в очереди всегда будет строго больше \(i\) в запросе третьего типа.

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

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

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

longqueue.in
1 2
3
5
1 2
1 1
3 0
3 1
3 2
longqueue.out
0
1
2
longqueue.in
2 2
1 2
7
3 0
3 1
2
3 0
1 3
3 0
3 1
longqueue.out
0
0
0
0
1
Система оценивания

Первая группа тестов состоит из тестов, для которых выполняется ограничение \(n, m \leq 1\, 000\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.

Вторая группа тестов состоит из тестов, для которых выполняется ограничение \(n, m \leq 100\, 000\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 60 баллов.

#112804
Выборы президента
  
Выборы президента
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
parties.in
вывод
parties.out

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

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

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

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

В первой строке входного файла дано целое число \(n\) (\(2 \le n \le 100\,000\)) — число парламентариев.

В следующей строке дано \(n\) целых чисел \(a_i\) (\(0 \le a_i < n\), сумма всех \(a_i\) равна \(n\)) — число голосов, которые получил \(i\)-й парламентарий.

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

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

Если искомое назначение существует, то во второй строке выведите \(n\) целых чисел — 1, если \(i\)-й политик состоит в партии Даков, или 2, если он состоит в партии Маусов.

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

parties.in
5
1 2 0 2 0
parties.out
YES
1 1 2 2 2
Система оценивания

Первая группа тестов состоит из тестов, для которых выполняется ограничение \(1 \le n \le 15\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 баллов.

Вторая группа тестов состоит из тестов, для которых выполняется ограничение \(1 \le n \le 300\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.

Третья группа тестов состоит из тестов, для которых выполняется ограничение \(1 \le n \le 100\,000\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.

Страница: << 1 2 3 4 5 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест