Дерево называется сбалансированным, если для любой его вершины высота левого и правого поддерева для этой вершины различаются не более чем на 1.
Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. Постройте дерево, соответствующее данной последовательности.
Определите, является ли дерево сбалансированным, выведите слово YES или NO.
7 3 2 1 9 5 4 6 8 0
YES
По данной последовательности постройте дерево, запоминая для каждого элемента его значение и количество его повторений в последовательности.
Вводится последовательность целых чисел, заканчивающаяся нулем. Сам ноль в последовательность не входит.
Выведите на экран содержимое дерева в порядке возрастания, по одному элементу на строку. В каждой строке выводите значение элемента, затем, через пробел, укажите, сколько раз он встречается в исходной последовательности.
7 3 2 1 9 5 4 6 8 0
1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 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
В холле 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
Ценные бумаги на фондовом рынке характеризуются множеством параметров. У них есть цена и ликвидность, также оценивать динамичность изменения цены, среднюю прибыльность, потенциал роста прибыльности и др. показатели. Аналитики трейдовой компании "WebMarket" ввели специальный показатель надежности ценной бумаги и научились эффективно его оценивать. Большое значение этого показателя соответствует малому риску покупки ценной бумаги. Но с ростом надежности обычно падает среднее оцениваемое значение прибыльности.
Для своих клиентов, играющих на рынке ценных бумаг, компания "WebMarket" решила открыть значения этого показателя и более того, автоматизировать покупку ценных бумаг с заданным порядковым номером по значению надежности. Аналитики проанализировали идею, и решили, что наличие такого функционала будет способствовать привлечению новых клиентов на рынок "WebMarket", повышению объемов сделок, а значит, и повышению прибылей "WebMarket". Важно также отметить, что торговля на базе этого показателя может позитивно сказаться на российском фондовом рынке и cделать его более здоровым. Алгоритмы оценки надежности уже написаны, средства выделены, необходимая реклама проведена. Осталось только написать сам код.
Ценные бумаги в базе данных имеют три атрибута:
Каждой новой ЦБ выдается следующий по порядку id и значение её надёжности устанавливается в 0. Если ценная бумага отзывается с рынка, ее id для новых бумаг не используется.
База данных получает запросы, которые позволяют вводить новые ЦБ на рынок, получать текущую информацию о ЦБ, отзывать ЦБ с рынка, менять значение надежности у ЦБ и находить ЦБ, которая стоит на n-м месте, если упорядочить ЦБ по убыванию надежности, а при одинаковых значениях по возрастанию идентификатора.
При добавлении ЦБ с кодом, который раньше встречался, но соответствующая ЦБ была отозвана с рынка, ей назначается новый идентификатор.
Таким образом, на каждый запрос на входе нужно вывести одну строку с результатом.
17 ISSUE aaa FIND 10 ISSUE bbb ISSUE ccc RELIABILITY aaa 10 RELIABILITY bbb 30 RELIABILITY ccc 20 RELIABILITY xxx 20 FIND 1 FIND 2 FIND 0 ISSUE eee ISSUE fff FIND 3 FIND 111 DELETE bbb FIND 0
CREATED 0 0 OK aaa 0 0 CREATED 1 0 CREATED 2 0 OK 0 10 OK 1 30 OK 2 20 BAD REQUEST OK ccc 2 20 OK aaa 0 10 OK bbb 1 30 CREATED 3 0 CREATED 4 0 OK eee 3 0 OK fff 4 0 OK 1 30 OK ccc 2 20