Страница: << 146 147 148 149 150 151 152 >> Отображать по:
#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 баллов.

#112805
Пирожные
  

Сегодня у Скруджа день рождения!

В подарок он получил целый стол пирожных. Так как у миллионеров не очень много свободного времени, Скрудж хочет съесть как можно больше пирожных за \(T\) секунд.

Стол с пирожными можно представить как бесконечную прямую. Каждое пирожное задается на этой прямой своей координатой \(x_i\). Для того, чтобы перейти от пирожного \(i\) к пирожному \(j\) Скрудж тратит \(|x_i - x_j|\) секунд. Также, для каждого пирожного Скрудж прикинул время \(t_i\) в секундах, за которое он сможет его съесть. Если несколько пирожных располагаются в одной точке, то Скруджу не надо перемещаться от одного у другому, но он может есть их только по очереди.

Изначально Скрудж стоит в точке с координатой \(0\). Помогите Скруджу выяснить какое максимальное количество пирожных он может успеть съесть за время \(T\).

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

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

В каждой из следующих \(n\) строк дано по два целых числа \(x_i\) и \(t_i\) (\(1 \le x_i, t_i \le 10^9\)) — координата \(i\)-го пирожного и время, за которое Скрудж может его съесть. Пирожные даны в порядке неубывания координаты, то есть для любых \(i\) и \(j\), таких, что \(i \lt j\) верно, что \(x_i \le x_j\).

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

В единственной строке выходного файла выведите максимальное количество пирожных, которые Скрудж может успеть съесть за время \(T\).

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

cakes.in
3 10
1 4
2 5
3 3
cakes.out
2
cakes.in
3 10
1 2
2 2
3 3
cakes.out
3
cakes.in
8 100
1 21
3 10
4 3
5 19
8 8
9 32
50 1
100 1
cakes.out
5
Комментарий

В первом примере Скруджу нужно перейти от точки с координатой \(0\) к точке с координатой \(1\), съесть первое пирожное, потом перейти к точке с координатой \(3\) и съесть третье пирожное.

Система оценивания

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

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

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

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

#112806
Счета дядюшки Скруджа
  
Счета дядюшки Скруджа
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
accounts.in
вывод
accounts.out

Дядюшка Скрудж известен своей жадностью. Когда-то давно он завел аж \(n\) банковских счетов. На каждый из этих счетов ежедневно приходит фиксированная положительная сумма в \(b_i\) долларов. Таким образом, через \(t\) дней на \(i\)-м счету находится \(t\times{}b_i\) долларов.

Сегодня Билли, Вилли и Дилли решили проучить своего дедушку. Они украли из его бухгалтерии всю информацию о числах \(b_i\). Теперь дядюшка Скрудж даже не сможет посмотреть сумму на каждом из счетов, ведь число \(b_i\) является также паролем для \(i\)-го из них. Но ребята понимают, что это слишком жестокая шутка над Скруджем, поэтому они решили дать ему шанс и сделали \(m\) подсказок.

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

Теперь Скрудж может попытаться восстановить числа \(b_i\) по имеющимся подсказкам. Он в отчаянии: для него это слишком сложная задача, поэтому он попросил вас помочь ему.

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

В первой строке входного файла даны два целых числа \(n\), \(m\) (\(1 \le n \le 100\,000, 1 \le m \le 100\,000\)) — количество счетов дядюшки Скруджа и количество подсказок Билли, Вилли и Дилли. В следующих \(2 m\) строках описаны подсказки дяде Скруджу: сначала идет целое число \(k_i\) (\(1 \le k_i \le n\)) — количество счетов, для которых ребята записали их состояние в некоторый день, в следующей строке идут \(2 k_i\) целых чисел \(c_{i,j}\), \(x_{i,j}\) (\(1 \le c_{i,j} \le n, 1 \le x_{i,j} \le 10^{18}\)) — номер счета и сумма на нем. Гарантируется, что для каждой подсказки \(c_{i,j}\) различны.

Гарантируется, что сумма \(k_i\) не превосходит \(3\cdot 10^5\).

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

В первой строке выведите «NO», если решения не существует и «YES» в противном случае. Если решение существует, следующая строка должна содержать \(n\) целых чисел \(b_i\) (\(1 \le b_i \le 10^{18}\)) — сколько долларов приходит на \(i\)-й счет ежедневно. Если решений, удовлетворяющих всем подсказкам, несколько, выведите любое.

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

accounts.in
3 2
2
1 6 2 9
1
1 8
accounts.out
YES
2 3 1
accounts.in
5 3
2
1 4 2 6
2
2 12 3 8
3
2 9 3 6 4 3
accounts.out
YES
2 3 2 1 1
accounts.in
3 2
2
1 6 2 9
2
1 9 2 6
accounts.out
NO
Комментарий

В первом примере номер дня для первой подсказки равен \(3\), для второй \(4\), считая от дня отрытия счетов. Во втором примере номер дня для первой подсказки равен \(2\), для второй \(4\), для третьей \(3\), считая от дня отрытия счетов. В третьем примере решения не существует.

Система оценивания

Первая группа тестов состоит из тестов, для которых выполняется ограничение \(x_{i,j} \le 100\,000\). Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет \(50\) баллов.

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

#112810
Контрольная работа
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
512 megabytes

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

В классе стоит один ряд парт, за каждой из них (кроме, возможно, последней) на контрольной будут сидеть ровно два ученика. Ученики знают, что варианты будут раздаваться строго по порядку: правый относительно учителя ученик первой парты получит вариант 1, левый — вариант 2, правый ученик второй парты получит вариант 3 (если число вариантов больше двух) и т.д. Так как K может быть меньше чем число учеников N, то после варианта K снова выдаётся вариант 1. На последней парте в случае нечётного числа учеников используется только место 1.

Петя самым первым вошёл в класс и сел на своё любимое место. Вася вошёл следом и хочет получить такой же вариант, что и Петя, при этом сидя к нему как можно ближе. То есть между ними должно оказаться как можно меньше парт, а при наличии двух таких мест с равным расстоянием от Пети Вася сядет позади Пети, а не перед ним. Напишите программу, которая подскажет Васе, какой ряд и какое место (справа или слева от учителя) ему следует выбрать. Если же один и тот же вариант Вася с Петей писать не смогут, то выдайте одно число  - 1.

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

В первой строке входных данных находится количество учеников в классе 2 ≤ N ≤ 109. Во второй строке — количество подготовленных для контрольной вариантов заданий 2 ≤ K ≤ N. В третьей строке — номер ряда, на который уже сел Петя, в четвёртой — цифра 1, если он сел на правое место, и 2, если на левое.

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

Если Вася никак не сможет писать тот же вариант, что и Петя, то выведите  - 1. Если решение существует, то выведите два числа — номер ряда, на который следует сесть Васе, и 1, если ему надо сесть на правое место, или 2, если на левое. Разрешается использовать только первые N мест в порядке раздачи вариантов.

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

Входные данные
25
2
1
2
Выходные данные
2 2
Входные данные
25
13
7
1
Выходные данные
-1

Примечание

В первом примере вариантов 2, поэтому наилучшее место для Васи находится сразу за Петей. Во втором примере Петя будет единственным, кто получит вариант 13.

Система оценки

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

Подзадача 1. N ≤ 100. Оценивается из 52 баллов.

Подзадача 2. N ≤ 109. Оценивается из 48 баллов.

Страница: << 146 147 148 149 150 151 152 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест