--->
30 задач
<---
Источники
Петя, которому три года, очень любит играть с машинками. Всего у Пети N различных машинок, которые хранятся на полке шкафа так высоко, что он сам не может до них дотянуться. Одновременно на полу комнаты может находиться не более K машинок. Петя играет с одной из машинок на полу и если он хочет поиграть с другой машинкой, которая также находится на полу, то дотягивается до нее сам. Если же машинка находится на полке, то он обращается за помощью к маме. Мама может достать для Пети машинку с полки и одновременно с этим поставить на полку любую машинку с пола. Мама очень хорошо знает своего ребенка и может предугадать последовательность, в которой Петя захочет играть с машинками. При этом, чтобы не мешать Петиной игре, она хочет совершить как можно меньше операций по подъему машинки с пола, каждый раз правильно выбирая машинку, которую следует убрать на полку. Ваша задача состоит в том, чтобы определить минимальное количество операций. Перед тем, как Петя начал играть, все машинки стоят на полке.
В первой строке содержаться три числа \(N\), \(K\) и \(P\) (\(1 \leq K \leq N \leq 100000\), \(1 \leq P \leq 500000\)). В следующих \(P\) строках записаны номера машинок в том порядке, в котором Петя захочет играть с ними.
Выведите единственное число: минимальное количество операций, которое надо совершить Петиной маме.
Операция 1: снять машинку 1
Операция 2: снять машинку 2
Операция 3: поднять машинку 2 и снять машинку 3
Операция 4: поднять машинку 3 или 1 и снять машинку 2
3 2 7 1 2 3 1 3 1 2
4
Игорь работает младшим лаборантом в НИИ ихтиологии. Ему вверены \(n\) аквариумов, стоящих в ряд, в каждом из которых живет колония рыбок гуппи. Про каждую колонию заранее известна ее численность.
В лабораторных условиях НИИ ихтиологии колония рыбок гуппи растет по следующему правилу: достигнув популяции в \(f\) рыбок, колония живет в течении \(max(1000 - f, 1)\) секунд, после чего на свет появляется новая рыбка. От начального момента времени до рождения первой рыбки колония размера \(f\) также ждет \(max(1000 - f, 1)\) секунд.
Например, колония с начальным размером 996 будет размножаться следующим образом:
| момент времени | размер колонии | время до очередной рыбки |
|---|---|---|
| 0 | 996 | 4 |
| 4 | 997 | 3 |
| 7 | 998 | 2 |
| 9 | 999 | 1 |
| 10 | 1000 | 1 |
| 11 | 1001 | 1 |
| 12 | 1002 | 1 |
| ... | ... | ... |
Появление на свет каждой новой рыбки Игорь должен фиксировать в специальном журнале. Будем считать, что запись он делает мгновенно, но при этом он должен в момент рождения новой рыбки находиться рядом с аквариумом, в котором это произошло.
На перемещение от одного аквариума к соседнему у Игоря уходит одна секунда. В начальный момент времени Игорь стоит около первого аквариума.
Вычислите, в течение какого наибольшего периода времени Игорь сможет добросовестно выполнять свою работу.
В первой строке входного файла содержится целое число \(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
Напишите программу, которая будет обрабатывать последовательность запросов таких видов:
CLEAR — сделать пирамиду пустой (если в пирамиде уже были какие-то элементы, удалить все). Действие происходит только с данными в памяти, на экран ничего не выводится.
ADD n — добавить в пирамиду число n. Действие происходит только с данными в памяти, на экран ничего не выводится.
EXTRACT — вынуть из пирамиды максимальное значение. Следует и изменить данные в памяти, и вывести на экран или найденное максимальное значение, или, если пирамида была пустой, слово "CANNOT" (большими буквами).
Во входных данных записано произвольную последовательность запросов CLEAR, ADD и EXTRACT — каждый в отдельной строке, согласно вышеописанному формату.
Суммарное количество всех запросов не превышает 200000.
Для каждого запроса типа EXTRACT выведите на стандартный выход (экран) его результат (в отдельной строке).
Задачу следует решить двумя способами. Один — использовать стандартную реализацию пирамиды в STL; она называется priority_queue, для её использования необходимо подключить заголовочный файл queue. Другой способ — реализовать пирамиду самому, использовать разрешено лишь некоторые из следующих заголовочных файлов: iostream, fstream, сstdio, stdio.h, string, string.h, vector.
ADD 192168812 ADD 125 ADD 321 EXTRACT EXTRACT CLEAR ADD 7 ADD 555 EXTRACT EXTRACT EXTRACT
192168812 321 555 7 CANNOT
Задача отличается от задачи «Пирамида (максимум)» исключительно тем, что надо извлекать не максимум, а минимум.
Напишите программу, которая будет обрабатывать последовательность запросов таких видов:
CLEAR — сделать пирамиду пустой (если в пирамиде уже были какие-то элементы, удалить все). Действие происходит только с данными в памяти, на экран ничего не выводится.
ADD n — добавить в пирамиду число n. Действие происходит только с данными в памяти, на экран ничего не выводится.
EXTRACT — вынуть из пирамиды минимальное значение. Следует и изменить данные в памяти, и вывести на экран или найденное минимальное значение, или, если пирамида была пустой, слово "CANNOT" (большими буквами).
Во входных данных записано произвольную последовательность запросов CLEAR, ADD и EXTRACT — каждый в отдельной строке, согласно вышеописанному формату.
Суммарное количество всех запросов не превышает 200000.
Для каждого запроса типа EXTRACT выведите на стандартный выход (экран) его результат (в отдельной строке).
Собственно, это тот случай, когда, не имея под руками справочных материалов, легче реализовать структуру данных самому, чем добиться от стандартной реализации, чтобы она заработала так как надо... Но это все же возможно. Пирамиду с максимумом в корне объявляют просто как
priority_queue<T> the_heap; а пирамиду с минимумом в корне — как
priority_queue<T, vector<T>, greater<T> > the_heap; При этом, второй параметр (vector<T>) задает тип контейнера, в котором будет храниться пирамида (и менять вектор на что бы ни было другое практически никогда не бывает целесообразно), а третий параметр (который, когда ничего не сказано, равен less<T>) задает, какую операцию следует использовать при проверке основного свойства пирамиды в качестве операции «меньше». Когда на место операции «меньше» подставляется операция «больше» — как раз и получается, что упорядоченность пирамиды заменяется на противоположную.
Разумеется, вместо T следует написать тип элементов, которые будем хранить в пирамиде.
ADD 192168812 ADD 125 ADD 321 EXTRACT EXTRACT CLEAR ADD 7 ADD 555 EXTRACT EXTRACT EXTRACT
125 321 7 555 CANNOT
Напишите программу, которая будет находить расстояния в неориентированном взвешенном графе с неотрицательными длинами ребер, от указанной вершины до всех остальных. Программа должна работать быстро для больших разреженных графов.
В первой строке входных данных задано число NUM — количество различных запусков алгоритма Дейкстры (на разных графах). Далее следуют NUM блоков, каждый из которых имеет следующую структуру.
Первая строка блока содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них в пределах от 0 до N–1 каждое и обозначают концы соответствующего ребра, третье — в пределах от 0 до 20000 и обозначает длину этого ребра. Далее, в последней строке блока, записанное единственное число от 0 до N–1 — вершина, расстояния от которой надо искать.
Количество различных графов в одном тесте NUM не превышает 5. Количество вершин не превышает 60000, рёбер — 200000.
Выведите на стандартный выход (экран) NUM строк, в каждой из которых по Ni чисел, разделенных пробелами — расстояния от указанной начальной вершины взвешенного неориентированного графа до его 0-й, 1-й, 2-й и т. д. вершин (допускается лишний пробел после последнего числа). Если некоторая вершина недостижима от указанной начальной, вместо расстояния выводите число 2009000999 (гарантировано, что все реальные расстояния меньше).
1 5 7 1 2 5 1 3 2 2 3 4 2 4 3 3 4 6 0 3 20 0 4 10 1
18 0 5 2 8