Задача A. ЕГЭ ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Школьник Игорь с детства любил компьютер. Он любил на нем играть, смотреть фильмы и делать много других приятных вещей. Иногда он даже программировал на нем. И у него была мечта поступить в университет и стать программистом. Но Игорь был не очень усердным учеником, поэтому день сдачи ЕГЭ по информатике наступил для него совершенно неожиданно. А ведь без хорошего балла за ЕГЭ его мечта так и останется мечтой.

На пробном ЕГЭ ему попалось задание, которое он не знал, как решать. Задание требовало выписать семь подряд идущих символов k-ой строки, начиная с ее i-го символа. Строки строились по правилу:

• S₀ = 0
• S₁ = 01
• S₂ = 0110
• S₃ = 01101001
• S_j = S_j−1 +S_j−1, где S означает строку S, в которой все нули заменены на единицы и наоборот.

Игорь просит Вас помочь решить эту задачу.

Первая группа тестов проверяется в момент сдачи задачи на проверку и стоит 60 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие k ≤ 20.

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

Формат входного файла

Во входном файле дано два числа — k и i (3 ≤ k ≤ 63, 1 ≤ i ≤ 2^k − 7).

Формат выходного файла

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

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

3 1

1101001

4 6

0011001

Задача B. Держать строй! ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

В воинской части города Шатров решили провести строевую подготовку по новым правилам. Сначала все солдаты выстраиваются в шеренгу по росту, начиная с самого низкого. Затем они выполняют команды вида: "С a по b — развернись!". Выполнение такой команды происходит следующим образом. Пусть a_pos — номер места в строю, на котором стоит a-й по росту солдат, а b_pos — b-й. Тогда отрезок строя с позиции min(a_pos, b_pos) до позиции max(a_pos, b_pos) должен развернуться. То есть, например, a-й по росту солдат поменяется местами с b-м.

Завтра утром молодой прапорщик Андрей Юрьевич будет проводить строевую подготовку в первый раз за свою службу, и на это придет посмотреть командир его части. Поэтому Андрей Юрьевич выписал вечером все команды на листочек и поручил Вам, как самому умному солдату, узнать до утра, как будет выглядеть шеренга после выполнения всех команд. Также известно, что для любых двух команд i и j (i ≠ j) выполняется ровно одно из следующих условий:

• b_i < a_j
• b_j < a_i
• a_i < a_j, b_j < b_i
• a_j < a_i, b_i < b_j

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

Первая группа тестов проверяется в момент сдачи задачи на проверку и стоит 40 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие n ≤ 1000 и m ≤ 1000.

Вторая группа тестов проверяется после окончания олимпиады и стоит 60 баллов. Баллы за тесты этой группы начисляются пропорционально количеству пройденных тестов.

Формат входного файла

В первой строке входного файла дано количество солдат n (1 ≤ n ≤ 100000) и количество команд m (1 ≤ m ≤ n/2). В следующих m строках даны сами команды. Каждая команда описана двумя числами a_i и b_i (1 ≤ a_i < b_i ≤ n).

Формат выходного файла

В единственной строке выведите через пробел n чисел, где i — число, равное номеру по росту солдата, стоящего на i-м месте.

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

4 2
1 4
2 3

4 2 3 1

Задача C. Выборы ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Недавно в стране прошли выборы, при проведении которых были использованы современные технологии: про каждый бюллетень известно, когда он был положен в урну и кандидат, за которого проголосовал человек, опустивший в урну этот бюллетень. Бюллетени пронумерованы в хронологическом порядке. После подсчета голосов все, кому не лень, захотели проанализировать ход выборов. Ведь не зря же вводилась вся эта система?

Многим стала интересна следующая информация: "сколько голосов было отдано за заданный промежуток времени за кандидата, выигрывавшего на этом промежутке?". Ведь, если за какого-то кандидата в какой-то небольшой промежуток времени голосовали активно, а в остальное — менее активно, то, возможно, в этот промежуток времени была совершена фальсификация. Для ответа на эти запросы даже был создан специальный сайт, на котором каждый посетитель, которому небезразлична судьба страны, мог узнать интересующую его информацию. Однако, количество посетителей оказалось неожиданно большим, и сайт перестал справляться с нагрузками.

Руководством решено было переписать все так, чтобы обслуживать одновременно m пользователей. Вам поручено реализовать программу, отвечающую на вопрос, который ставят пользователи: "Сколько голосов за определенный промежуток времени набрал кандидат, который набрал за этот промежуток больше, чем все остальные?".

Первая группа тестов проверяется в момент сдачи задачи на проверку и стоит 20 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие n ≤ 100 и m ≤ 100.

Вторая группа тестов проверяется в момент сдачи задачи на проверку и стоит 20 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие n ≤ 3 000 и m ≤ 3 000.

Третья группа тестов проверяется в момент сдачи задачи на проверку и стоит 20 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие ∀ a_i:a_i ≤ 5

Четвертая группа тестов проверяется после окончания олимпиады (в CATS проверка осуществляется сразу — прим. перев.) и стоит 40 баллов. Баллы за тесты этой группы начисляются пропорционально количеству пройденных тестов.

Формат входного файла

В первой строке задано количество обработанных бюллетеней n (1 ≤ n ≤ 100 000). Во второй строке через пробел заданы n целых чисел a_i (1 ≤ a_i ≤ 10⁹) — номер кандидата, за которого проголосовал человек, опустивший в урну бюллетень номер i. В третьей строке задано число m (1 ≤ m ≤ 100 000) — количество запросов. В следующих m строках заданы сами запросы в формате l_i r_i (1 ≤ l_i ≤ r_i ≤ n) — наименьший и наибольший номера бюллетеня, которые следует рассматривать при обработке этого запроса.

Формат выходного файла

Для каждого запроса в отдельной строке выведите одно число — количество бюллетеней с номерами не меньше l_i и не больше r_i, голоса на которых отданы самому популярному кандидату на этом отрезке. Самым популярным называется любой такой кандидат, за которого среди бюллетеней с подходящими номерами отдано количество голосов не меньшее, чем за любого другого кандидата среди этих же бюллетеней.

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

6
1 1 2 2 1 1
3
1 6
2 4
2 5

4
2
2

Задача D. Принцесса ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Принцесса Евлампия живет в замке, окруженном забором. Жизнь принцессы тяжела, но при этом и очень интересна. Главным ее развлечением является общение с многочисленными поклонниками, постоянно прибывающими из соседних замков, городов и даже королевств.

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

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

Первая группа тестов проверяется в момент сдачи задачи на проверку и стоит 30 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие n ≤ 100 и m ≤ 100.

Вторая группа тестов проверяется в момент сдачи задачи на проверку и стоит 30 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие n ≤ 100 и m ≤ 10 000.

Третья группа тестов проверяется после окончания олимпиады и стоит 40 баллов. Баллы за тесты этой группы начисляются пропорционально количеству пройденных тестов.

Формат входного файла

В первой строке входного файла находятся два целых числа n и k (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n) — количество вершин в многоугольнике, представляющем забор, и номер вершины, в которой находится дырка. В следующих n строках содержатся пары целых чисел x_i и y_i, описывающих координаты вершин многоугольника в порядке обхода против часовой стрелки.

В следующей строке дано одно целое число m (1 ≤ m ≤ 100 000) — количество поклонников принцессы. В следующих m строках содержатся пары целых чисел x_i и y_i, описывающих координаты начального положения очередного поклонника.

Все координаты не превышают 10⁹ по абсолютной величине.

Формат выходного файла

Для каждого поклонника выведите одно число — ответ на задачу. Ответ должен отличаться от правильного не более, чем на 10⁻⁵.

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

4 2
0 1
0 0
1 0
1 1
2
2 2
-2 0

3.23606797
2.0