Страница: << 1 2 Отображать по:
#111644
Морской бой
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В рамках Чемпионата Урала планируется проведение турнира стратегий по игре «Морской бой 1D».

Игра проходит на поле, которое представляет собой прямоугольник размером 1 × N клеток. На поле расставляются T кораблей, каждый из которых имеет вид прямоугольника размером 1 × K клеток. Расстановка кораблей на поле является допустимой, если различные корабли не имеют общих клеток и разделены хотя бы одной пустой клеткой. Игровая программа осуществляет выстрелы в клетки поля, а сервер сообщает, является ли выстрел промахом или попаданием в корабль.

В процессе игры про некоторые клетки становится известно, что при любой допустимой расстановке кораблей они принадлежат какому-либо из кораблей. Назовём такие клетки заведомо занятыми.

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

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

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

Задача является интерактивной. После каждого вывода требуется сбросить буфер вывода.

Роль игровой программы исполняет программа жюри. Программа-решение исполняет роль сервера.

Первая строка стандартного ввода программы-решения содержит параметры игры — три числа: N — размер игрового поля, T — число кораблей и K — длина каждого корабля (1 ≤ N ≤ 100 000, 1 ≤ T, 1 ≤ K). Гарантируется, что на поле длины N можно по описанным правилам разместить T кораблей длины K.

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

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

  1. Считать из стандартного потока ввода одно число q — номер клетки, в которую игровая программа осуществляет выстрел (1 ≤ q ≤ N). Игровая программа никогда не делает два выстрела в одну и ту же клетку.
  2. Если клетка q является заведомо занятой, вывести в стандартный поток вывода число 1 и завершить работу.
  3. Если клетка q не является заведомо занятой, вывести в стандартный поток два числа, разделенных пробелом: 0 и количество заведомо занятых клеток после этого выстрела. После этого программа-решение переходит к пункту 1 и продолжает взаимодействие с игровой программой.

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

Примечание

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

  1. Тесты из условия. Подзадача оценивается в 0 баллов.
  2. N ≤ 15. Подзадача оценивается в 30 баллов.

  3. N ≤ 3000. Подзадача оценивается в 30 баллов.

  4. N ≤ 100 000. Подзадача оценивается в 40 баллов.

Примеры
Входные данные
8 2 3
4
1
Выходные данные
4
0 5
1
#111645
Массовый прогноз
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

По результатам голосования составляется список, i-й элемент этого списка равен номеру кандидата, за которого проголосовал i-й избиратель. Для каждого отрезка списка назначается наблюдатель, который подсчитывает голоса на этом отрезке. Таким образом, на выборах работают N(N + 1) / 2 наблюдателей.

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

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

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

Первая строка входного файла содержит два числа N и K (1 ≤ N ≤ 500 000, 1 ≤ K ≤ 500 000). Вторая строка содержит N чисел V1, V2, ..., VN — список голосов избирателей (1 ≤ Vi ≤ K).

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

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

Примечание

Для окончательной проверки решений этой задачи используются 50 тестов. Тесты оцениваются независимо. Каждый тест оценивается в 2 балла. Значения N и K в тестах приведены в таблице.

Тест N K Тест N K Тест N K
1 2 2 18 2000 20 35 90000 1000
2 3 1 19 3000 2000 36 100000 5000
3 5 5 20 5000 2000 37 125000 1
4 10 10 21 7500 200 38 150000 12000
5 20 2 22 10000 10000 39 150000 18
6 30 3 23 15000 1500 40 200000 42000
7 50 20 24 20000 10 41 250000 26000
8 75 75 25 25000 100 42 300000 10000
9 100 2000 26 30000 15 43 350000 102000
10 150 30 27 35000 35 44 400000 12000
11 200 50 28 40000 10000 45 450000 5000
12 300 10 29 45000 10000 46 500000 2
13 400 100 30 50000 10000 47 500000 102000
14 500 2 31 55000 13000 48 500000 102000
15 300 200 32 60000 174 49 500000 102000
16 1000 2000 33 70000 10000 50 500000 501
17 1500 100 34 80000 1000      

Примеры
Входные данные
5 2
1 2 1 2 1
Выходные данные
9
Входные данные
3 7
5 2 6
Выходные данные
3
#111646
Флешмоб
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Для участников олимпиады на главной площади города «У» планируется игра в форме флешмоба. Главная площадь замощена плитками, образующими клетчатое поле.

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

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

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

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

В первой строке входного файла содержится число N — количество участников флешмоба (1 ≤ N ≤ 123 456). Каждая из последующих N строк содержит четыре целых числа x1i, y1i, x2i, y2i — координаты плиток для i-го участника (1 ≤ x1i,  y1i,  x2i,  y2i ≤ 109; либо x1i = x2i, либо y1i = y2i). Участники перечислены в порядке выхода на площадь.

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

Первая строка выходного файла должна содержать число M — минимальное количество призов, которые должны быть разложены на площади. Каждая из последующих M строк должна содержать два числа pxi и pyi — координаты плитки, на которой должен лежать i-й приз.

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

Примечание

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

  1. Тесты из условия. Подзадача оценивается в 0 баллов.

  2. N ≤ 123. Все координаты не превосходят 234. Подзадача оценивается в 21 балл.

  3. N ≤ 2543. Подзадача оценивается в 23 балла.

  4. N ≤ 123 456. Подзадача оценивается из 56 баллов.

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