Страница: << 121 122 123 124 125 126 127 >> Отображать по:
#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
#111652
Купе
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Два юных шамана Егор и Саша отправились на Всероссийский Конкурс Опытных Шаманов Профессионалов. До места проведения ВКОШП можно добраться только на поезде. Всего в вагоне поезда восемь купе по четыре места в каждом. Схема нумерации мест первого купе представлена на рисунке.

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

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

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

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

В первой строке выведите "YES", если друзья попадут в одно купе, и "NO" — иначе. Во второй строке выведите "LOW", если Саша будет ехать на нижнем месте, и "HIGH", если на верхнем. В третьей строке выведите положение места Егора в том же формате

Примечание

В этой задаче всего 50 тестов, каждый оценивается в 2 балла независимо от других.

Примеры
Входные данные
1 2
Выходные данные
YES
LOW
HIGH
Входные данные
1 5
Выходные данные
NO
LOW
LOW
#111653
Открытие
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Прямо с вокзала Егор и Саша отправились на открытие ВКОШП. Так как они прибыли позже всех, то им достались места в последнем ряду.

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

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

  • все номера различны;
  • если расставить все фрагменты в порядке возрастания номеров в n рядов по m штук, то получится целостная картинка.

Но, к сожалению, праздничная церемония, оригинальная музыка и блестящие ведущие так понравились друзьям, что они подумали: "Кто, если не Вы сможете составить список действий, после которых на Pinebook-ах они смогут увидеть картинку целиком?".

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

В первой строке находятся два натуральных числа n и m — количество рядов и количество мест в каждом из них. Далее идут n строк по m чисел в каждом: j-ое число на i-ой строке является номером фрагмента на ноутбуке, стоящем на j-ом месте i-ого ряда.

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

В первой строке выведите число c (0 ≤ c ≤ 5000000) — количество обменов фрагментов изображения между ноутбуками, которые необходимо произвести. Следующие c строк должны содержать информацию о совершенных обменах. В i строке выведите четыре натуральных числа: x1, y1, x2, y2 (1 ≤ x1, x2 ≤ n;1 ≤ y1, y2 ≤ m) — номера рядов и мест компьютеров, между которыми происходит i-ый по счету обмен. Вывод двух одинаковых позиций (x1 = x2 и y1 = y2) будет расцениваться как неправильный ответ!

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

Примечание

Пояснение к первому тесту:

Тесты в этой задаче состоят из пяти групп:

  1. Тесты 1-2. Тесты из условия. Оцениваются в 0 баллов.
  2. Тесты 3-12. Тесты с ограничением 1 ≤ NxM ≤ 100; |aij| ≤ 1000. Группа тестов оценивается в 25 баллов, при этом баллы ставятся только за прохождение всех тестов группы.
  3. Тесты 13-22. Тесты с ограничением 1 ≤ NxM ≤ 1000; |aij| ≤ 10000. Группа тестов оценивается в 25 баллов, при этом баллы ставятся только за прохождение всех тестов 1 и 2 группы.
  4. Тесты 23-37. Тесты с ограничением 1 ≤ NxM ≤ 105; |aij| ≤ 109. Группа тестов оценивается в 25 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2 и 3 группы.
  5. Тесты 38-52. Тесты с ограничением 1 ≤ NxM ≤ 105; |aij| ≤ 1018. Группа тестов оценивается в 25 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2, 3 и 4 группы.

Примеры
Входные данные
2 3
1 8 0
3 5 2
Выходные данные
3
1 1 1 3 
1 2 2 3 
1 2 1 3
Входные данные
1 1
42
Выходные данные
0
#111654
Воспоминания
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

После открытия, как это обычно бывает, всех участников ведут на экскурсию. Естественно, Олимпиада Шаманов-Профессионалов — не исключение.

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

После того, как Егор поделился воспоминаниями с Сашей, тот сразу же сформулировал задачу: а если бы ребят было не четверо, а N человек, и задач предлагалось M? Пусть тогда каждый сразу определил, что он решит все задачи с bi по ei, но не сможет сделать ни одной другой. Смогут ли они вместе решить все задачи, или же найдется такая, которая никому не по зубам?

От нечего делать Егор призадумался: а как же решить такую задачу?

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

В первой строке содержатся два натуральных числа N и M — количество участников и задач соответственно. Далее следуют N строк по два натуральных числа bi и ei в каждой (1 ≤ si ≤ ei ≤ M), которые означают, что i-ый участник решит все задачи с bi-ой по ei-ую.

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

В единственной строке выведите "YES", если участники справятся со всеми задачами, или "NO" в противном случае.

Примечание

Тесты в этой задаче состоят из шести групп:

  1. Тесты 1-2. Тесты из условия. Оцениваются в 0 баллов.
  2. Тесты 3-7. Тесты с ограничением 1 ≤ N, M ≤ 10. Группа тестов оценивается в 15 баллов, при этом баллы ставятся только за прохождение всех тестов группы.
  3. Тесты 8-17. Тесты с ограничением 1 ≤ N, M ≤ 100. Группа тестов оценивается в 15 баллов, при этом баллы ставятся только за прохождение всех тестов 1 и 2 группы.
  4. Тесты 18-27. Тесты с ограничением 1 ≤ N, M ≤ 1000. Группа тестов оценивается в 20 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2 и 3 группы.
  5. Тесты 28-37. Тесты с ограничением 1 ≤ N ≤ 105;1 ≤ M ≤ 1000. Группа тестов оценивается в 20 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2, 3 и 4 группы.
  6. Тесты 38-52. Тесты с ограничением 1 ≤ N ≤ 105;1 ≤ M ≤ 109. Группа тестов оценивается в 30 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2, 3, 4 и 5 группы.

Примеры
Входные данные
2 10
1 4
3 10
Выходные данные
YES
Входные данные
2 10
1 9
2 9
Выходные данные
NO
Страница: << 121 122 123 124 125 126 127 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест