--->
90 задач
<---
Источники
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes
В этой задаче вам необходимо организовать структуру данных Heap для хранения целых чисел, над которой определены следующие операции:
a) Insert(k) – добавить в Heap число k (1 ≤ k ≤ 1000000) ;
b) Extract достать из Heap наибольшее число (удалив его при этом).
Входные данные
В первой строке содержится количество команд N (1 ≤ N ≤ 100000), далее следуют N команд, каждая в своей строке. Команда может иметь формат: “0 <число>” или “1”, обозначающий, соответственно, операции Insert(<число>) и Extract. Гарантируется, что при выполенении команды Extract в структуре находится по крайней мере один элемент.
Выходные данные
Для каждой команды извлечения необходимо отдельной строкой вывести число, полученное при выполнении команды Extract.
Примеры
Входные данные
2 0 10000 1
Выходные данные
10000
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes
Рассмотрим последовательность целых чисел длины N. По ней с шагом 1 двигается “окно” длины K, то есть сначала в “окне” видно первые K чисел, на следующем шаге в “окне” уже будут находиться K чисел, начиная со второго, и так далее до конца последовательности. Требуется для каждого положения “окна” определить минимум в нём.
Входные данные
В первой строке входных данных содержатся два числа N и K (1 ≤ N ≤ 150000, 1 ≤ K ≤ 10000, K ≤ N) – длины последовательности и “окна”, соответственно. На следующей строке находятся N чисел – сама последовательность.
Выходные данные
Выходые данные должны содержать N − K + 1 строк – минимумы для каждого положения “окна”.
Примеры
Входные данные
7 3 1 3 2 4 5 3 1
Выходные данные
1 2 2 3 1
Вася разрабатывает новый веб-сервер. В настоящее время он работает над функцией, осебспечивающей поддержку списков контроля доступа. Список контроля доступа позволяет ограничить доступ к некоторым ресурсам веб-сайта, основываяь на основании IP-адреса запрашивающей стороны.
Каждый IP-адрес \(-\) это 4-байтный номер, который записан байт за байтом в десятичной записи. Байты разделены точками следующим образом: <<byte0.byte1.byte2.byte3>> (кавычки добавлены для ясности). Каждый байт записывается как десятичное число от 0 до 255 (включительно) без ведущих нулей. IP-адреса организованы в IP-сети. IP сети описывается двумя 4-байтовыми числами - сетевым адресом и маской сети. И сетевой адрес и маска сети записаны в той же форме, что и IP-адреса. Для того чтобы понять смысл сетевого адреса и маски сети рассмотрим их двоичное представление. Двоичное представление IP адреса, сетевого адреса и маски сети состоит из 32 бит: 8 бит для byte0 (от старших к младшим), затем по 8 бит для byte1, 8 бит для byte2 и 8 бит для byte3.
IP сеть содержит \(2N\) IP-адресов, где \(0 \leq N \leq 32\). В маске сети первые 32–N бита установлены в единицы, и последние \(N\) бит установлены в ноль. Сетевой адрес имеет произвольные \(32–N\) первых бит, а последние \(N\) бит установлен в ноль. IP сеть содержит все IP-адреса, первые \(32-N\) бит которых равны \(32–N\) первых бит сетевого адреса с произвольными \(N\) последними битами. Например, IP сеть с сетевым адресом 194.85.160.176 и сетевая маска 255.255.255.248 содержит 8 IP-адресов, с 194.85.160.176 по 194.85.160.183 (включительно).
IP сети, как правило, обозначается как <<byte0.byte1.byte2.byte3/S>>, где <<byte0.byte1.byte2.byte3>> \(-\) сетевой адрес, \(S\) \(-\) это число бит, установленных в единицу в маске сети. Например, IP сети из предыдущего абзаца обозначается как 194.85.160.176/29. Список контроля доступа содержит упорядоченный список правил. Каждое правило имеет одну из следующих форм:
deny from <IP network> \(-\) запрещает доступ к ресурсу для любого IP из заданной сети.
deny from <IP address> \(-\) запрещает доступ к ресурсу для указанного IP-адреса.
allow from <IP network> \(-\) разрешает доступ к ресурсу для любого IP из заданной сети.
allow from <IP address> \(-\) разрешает доступ к ресурсу для указанного IP-адреса.
Когда кто-нибудь обращается к какому-либо ресурсу, первым делом проверяется IP-адрес обращающегося по списку контроля доступа. Правила проверяются в том порядке, в котором они перечислены, и применяется первое выполняющееся правило. Если ни одно из правил не соответствует IP-адресу запрашивающей стороны, то доступ предоставляется.
По известному списку контроля доступа и списку запросов от IP-адресов, необходимо выяснить для каждого из запросов будет ли предоставлен доступ к ресурсу.
Входные данные
Первая строка ввода содержит число \(N\) \(-\) количество правил в списке контроля доступа (\(0 \leq N \leq 100 000\)). Следующие \(N\) строк содержат правила по одному в строке. IP сеть всегда записывается как <<byte0.byte1.byte2.byte3/S>>. Следующая строка содержит число \(M\) \(-\) количество IP адресов, которые следует проверить (\(0 \leq M \leq 100 000\)). Следующие \(M\) строк содержат по одному IP адресу в строке.
Выходные данные
Для каждого из \(M\) IP-адресов выведите <<A>>, если доступ будет предоставлен, и <<D>> иначе. Все символы следует выводить слитно, не разделяя пробелами.
Примеры
Входные данные
4 allow from 10.0.0.1 deny from 10.0.0.0/8 allow from 192.168.0.0/16 deny from 192.168.0.1 5 10.0.0.1 10.0.0.2 194.85.160.133 192.168.0.1 192.168.0.2
Выходные данные
ADAAA
#934
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
В холле 179 школы, есть информационный стенд размером \(H \times W\) (\(H\) – высота, \(W\) – ширина). На этом стенде размещается информация о кружках, изменениях в расписании, победах в олимпиадах, а также другая важная информация.
Первого сентября стенд был пуст. Одно за другим на нем начали появляться объявления, которые потом не снимались.
Каждое объявление представляет собой полоску бумаги единичной высоты. I-ое объявление представляет собой прямоугольник размером \(1 \times W_i\).
Когда кто-либо вешает объявление на стенд, то он старается повесить объявление как можно выше. Среди возможных верхних мест всегда выбирается самое левое. Если подходящего места для объявления не нашлось, то объявление не вешается на стенд. Ваша задача состоит в том, чтобы для каждого объявления определить, как высоко оно будет располагаться (в каком ряду).
Входные данные
Первая строка содержит три целых числа \(H\), \(W\) и \(N\) (\(1 \leq H, W \leq 10^9\); \(1 \leq N \leq 200 000\)) — размеры стенда и количество объявлений. Каждая из следующих N строк содержит по одному целому числу \(W_i\) (\(1 \leq W_i \leq 10^9\)) — ширину \(i\)-го объявления.
Выходные данные
Для каждого из объявлений (в порядке следования во входном файле) выведите номер ряда, в котором оно будет размещено. Ряды занумерованы от \(1\) до \(H\) сверху вниз. Если объявление разместить нельзя — выведите «–1».
Примеры
Входные данные
3 5 5 2 4 3 3 3
Выходные данные
1 2 1 3 -1
#1049
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2004,
1 день,
Задача C
]
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes
Горнолыжник, готовясь к соревнованиям, нарисовал на бумаге схему горнолыжной трассы для выбора оптимального маршрута спуска. На схеме расположенные на трассе ворота представлены горизонтальными отрезками. Никакая пара ворот не имеет общих точек.
Маршрут должен представлять собой ломаную, начинающуюся в точке старта на вершине горы и заканчивающуюся в точке финиша у ее подножия. Маршрут выбирается таким образом, что y-координата каждой следующей вершины ломаной оказывается строго меньше y-координаты предыдущей вершины. Один из возможных маршрутов представлен на рисунке.
За каждые ворота, через которые не проходит маршрут, лыжнику начисляются штрафные очки. Общий штраф за спуск по маршруту вычисляется как сумма длины маршрута и штрафных очков за непройденные ворота.
Требуется написать программу, которая определяет, какой минимальный общий штраф горнолыжник может получить при прохождении трассы.
Входные данные
В первой строке входного файла задано число N - количество ворот на трассе (0 ≤ N ≤ 500), в следующих двух строках заданы Sx, Sy, Fx, Fy - координаты точек старта и финиша соответственно. В каждой из следующих N строк записаны четыре числа ai, bi, yi, ci - x-координаты левого и правого концов ворот, y-координата ворот и штраф за непрохождение данных ворот (ai < bi, Fy < yi < Sy, ci - целое число, 0 ≤ ci ≤ 10000). Все координаты - целые числа, не превосходящие по модулю 10000.
Выходные данные
В выходной файл выведите наименьший возможный общий штраф за прохождение трассы с точностью не менее 4 знаков после десятичной точки.
Система оценки
Потестовая.
Примеры
Входные данные
4 3 6 3 1 5 7 4 1 4 5 5 10 1 2 4 5 2 5 2 0
Выходные данные
7.8126
Выбрано
:
|