Страница: << 1 2 Отображать по:
#2980
Откат
  
Источники: [ Командные олимпиады, ВКОШП, 2010, Задача I ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

На данный момент у Сергея хранятся \(n\) точек восстановления различных серверов, пронумерованных от 1 до \(n\). Точка восстановления с номером \(i\) позволяет произвести откат для сервера \(a_i\). Сергей решил разбить перенос на этапы, при этом на каждом этапе в случае возникновения проблем будут доступны точки восстановления с номерами \(l, l + 1, \ldots, r\) для некоторых \(l\) и \(r\).

Для того, чтобы спланировать перенос данных оптимальным образом, Сергею необходимо научиться отвечать на запросы: для заданного \(l\), при каком минимальном \(r\) в процессе переноса будут доступны точки восстановления не менее чем \(k\) различных серверов.

Помогите Сергею.

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

Первая строка входного файла содержит два целых числа \(n\) и \(m\) (\(1 \le n, m \le 10^5\)), разделенные пробелами — количество точек восстановления и количество серверов. Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) — номера серверов, которым соответствуют точки восстановления (\(1 \le a_i \le m\)).

Третья строка входного файла содержит \(q\) — количество запросов, которые необходимо обработать (\(1 \le q \le 100\,000\)). В процессе обработки запросов необходимо поддерживать число \(p\), исходно оно равно 0. Каждый запрос задается парой чисел \(x_i\) и \(y_i\), используйте их для получения данных запроса следующим образом: \(l_i = \left((x_i + p) \bmod n\right) + 1\),

\(k_i = \left((y_i + p) \bmod m\right) + 1\) (\(1 \le l_i,x_i \le n\), \(1\le k_i, y_i \le m\)). Пусть ответ на \(i\)-й запрос равен \(r\). После выполнения этого запроса, следует присвоить \(p\) значение \(r\).

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

На каждый запрос выведите одно число — искомое минимальное \(r\), либо 0, если такого \(r\) не существует.

Примеры
Входные данные
7 3
1 2 1 3 1 2 1
4
7 3
7 1
7 1
2 2
Выходные данные
1
4
0
6
#3407
Вычислительная ихтиология
  
Темы: [Куча]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

В лабораторных условиях НИИ ихтиологии колония рыбок гуппи растет по следующему правилу: достигнув популяции в \(f\) рыбок, колония живет в течении \(max(1000 - f, 1)\) секунд, после чего на свет появляется новая рыбка. От начального момента времени до рождения первой рыбки колония размера \(f\) также ждет \(max(1000 - f, 1)\) секунд.

Например, колония с начальным размером 996 будет размножаться следующим образом:

момент времениразмер колониивремя до очередной рыбки
09964
49973
79982
99991
1010001
1110011
1210021
.........

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

На перемещение от одного аквариума к соседнему у Игоря уходит одна секунда. В начальный момент времени Игорь стоит около первого аквариума.

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

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

В первой строке входного файла содержится целое число \(n\) (\(2 \le n \le 50\)) - количество аквариумов с рыбками гуппи в НИИ ихтиологии. Каждая из следующих \(n\) строк содержит одно целое число \(a_i\) (\(1 \le a_i \le 2007\)) - численность \(i\)-й колонии.

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

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

Примечание

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

Примеры
Входные данные
3
996
1
994
Выходные данные
7
#3583
Башня
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Петя в очередной раз купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из N столбиков, высота каждого столбика составляет Ai кубиков.

Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятия башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен.

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

Петя успешно справился со своей задачей, но теперь Правительство Флатландии решило защитить свой горный курорт. Правительство уже построило крепость из кубиков (просто кубики были побольше). Теперь вы должны помочь Правительству посчитать неприступность этой крепости. Единственная трудность состоит в том, что у Правительства было очень много денег, и поэтому крепость была построена очень длинная.

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

В первой строке входного файла содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1 ≤ K ≤ N ≤ 100 000). Далее на следующей строке содержатся N целых чисел, обозначающих Ai (1 ≤ Ai ≤ 106).

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

На первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни.

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