Задача 0F. Кривой код ≡

Условие

Вениамин — начинающий спортивный программист. Самой первой задачей в его спортивной карьере оказалось сложение чисел. На вход ему давалось натуральное число n, а затем последовательность a длины n, которая состоит из натуральных чисел. Затем Вениамину нужно было найти сумму чисел из последовательности и вывести двоичное представление этой суммы.

Так как Вениамин начинающий программист, он написал максимально кривой код решения данной задачи. Сначала он все числа последовательности a перевел в двоичное представление, а затем складывал двоичные коды чисел как десятичные числа (Вениамин забыл о том, что он больше не работает с десятичными числами), и только потом перевел полученную сумму в двоичный код.

Зная тест, который получил Вениамин на вход, сможете ли Вы сообщить число, которое вывела программа Вениамина?

Формат входных данных

В первой строке вводится натуральное число n (1 ≤ n ≤ 10⁵). Во второй строке вводится последовательность a из n натуральных чисел (1 ≤ a_i ≤ 10⁹).

Формат выходных данных

Выведите ответ на задачу без ведущих нулей.

Примечание

В первом примере Вениамин вычислял ответ следующим образом:

1. 2₁₀ = 10₂, 7₁₀ = 111₂, 5₁₀ = 101₂
2. 10₁₀ + 111₁₀ + 101₁₀ = 222₁₀
3. 222₁₀ = 11011110₂

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

3
2 7 5

11011110

Задача 0O. Конвертирование тяночек ≡

Условие

Абсолютно все знают, что 2D мир лучше 3D, поэтому в данной задаче Вам нужно будет исправить ошибку режиссёров очередного фильма жанра аниме и перевести тяночку в 2D мир.

В данной задаче есть тяночка и её одежда. Они представлены в виде двух выпуклых многогранников, которые могут между собой пересекаться. К сожалению, для каждого многогранника режиссёры помнят только набор из n точек, каждая из которых имеет координаты (x_i, y_i, z_i), в этих точках находятся все точки, которые являются вершинами многогранника, а также какие-то точки внутри многогранников, некоторые точки могут повторяться (то есть иметь одинаковые координаты). Чтобы перевести тяночку из 3D в 2D, Вам нужно построить проекцию данных многогранников на плоскость, которую Вам сообщат режиссёры (это одна из трех плоскостей: OXY, OYZ или OXZ).

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

Формат входных данных

В первой строке вводятся натуральные числа n₁ и n₂ - количество вершин многогранника тяночки и многогранника одежды соответственно (4 ≤ n₁, n₂ ≤ 100).

В следующих n₁ строках вводятся натуральные числа x_i, y_i и z_i - координаты i-й вершины (1 ≤ x_i, y_i, z_i ≤ 10⁹). Данные вершины относятся к многограннику тяночки.

В следующих n₂ строках вводятся натуральные числа x_i, y_i и z_i - координаты i-й вершины (1 ≤ x_i, y_i, z_i ≤ 10⁹). Данные вершины относятся к многограннику одежды.

В последней строке вводится строка s ∈ {"OXY"; "OYZ"; "OXZ"}, которая показывает, на какую плоскость нужно построить проекцию.

Формат выходных данных

Выведите YES, если условие цензуры выполняется, или NO в противном случае.

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

8 4
1 1 1
1 4 1
1 1 4
1 4 4
4 1 1
4 4 1
4 1 4
4 4 4
1 1 1
6 1 1
1 6 1
1 1 6
OXY

YES

Задача 0R. 52 ≡

Условие

Замечали ли Вы когда-нибудь то, что на электронном циферблате цифры 5 и 2 очень сильно похожи? А точнее, что они зеркальны друг другу?

У Жени есть длинный циферблат, на котором светятся n цифр, причем все цифры являются либо пятёркой, либо двойкой. Женя хочет отрезать какую-либо полоску из этого циферблата (то есть выбрать какое-то количество подряд идущих цифр) и подарить ее Анжелике. Анжелика любит во всем красоту, поэтому она хочет получить в подарок такую полоску, которая имеет четную длину и которая симметрична относительно центра. Более формально, полоска s длины 2k Анжелике понравится, если для любого 1 ≤ i ≤ 2k выполняется одно из двух условий:

1. s_i = 5, s_2k − i = 2
2. s_i = 2, s_2k − i = 5

Помогите Жене! Сообщите, сколькими способами он может отрезать полоску, чтобы подарить ее Анжелике.

Формат входных данных

В первой строке вводится число n — количество цифр на полоске (1 ≤ n ≤ 5 * 10⁵). В следующей строке вводится n цифр, которые показывают, в каком порядке светятся цифры на циферблате.

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

Формат выходных данных

Выведите ответ на задачу.

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

8
52525252

16

5
52525

6

2
52

1

Задача 1. Сила Архимеда ≡

Условие

Паша и Артём оказались на планете X, ускорение свободного падения на которой равно g Н/кг. Также ребята нашли огромное количество жидкости, плотность которой равна ρ кг/м³. Гуляя по планете, Артем нашел n камней, масса i-го камня равна m_i кг, объем i-го камня равен V_i м³.

Паша захотел взять какие-либо камни и превратить их в один (масса/объем итогового камня равна сумме масс/объемов использованных камней) таким образом, чтобы этот камень плавал в жидкости. Помогите Паше! Сообщите ему максимальную массу камня, которую он может собрать из камней, которые нашел Артем.

Формат входных данных

В первой строке вводятся натуральные числа n, g и ρ (1 ≤ n ≤ 1000, 1 ≤ g, ρ  ≤ 10000).

В следующих n строках вводятся натуральные числа m_i и V_i (1 ≤ m_i, V_i ≤ 100).

Формат выходных данных

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

Примечание

Приведем некоторые факты из курса физики:

• Формула для вычисления силы Архимеда: F_A = ρ g V.
• Формула для вычисления силы тяжести: F_T = mg.
• Тело плавает в жидкости, если сила Архимеда не меньше силы тяжести (то есть F_A ≥ F_T).

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

2 10 1000
100 5
1 1

101

Задача 2A. Авторитеты ≡

Условие

На экзамен по информатике пришло n участников, пронумерованных от 1 до n. Среди участников некоторые участники были друзьями, а точнее одни участники были авторитетами для других участников. Для i-го участника известны номера участников, которые являются его авторитетами.

Каждый участник экзамена определил условия, когда он точно завершит свой экзамен. Таким образом, i-й участник покинет пункт проведения экзамена в тот момент времени, который произойдет раньше:

1. С начала олимпиады прошло t_i минут.
2. Некоторые авторитеты участника завершили экзамен, и в кабинете осталось не больше c_i авторитетов.

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

Для каждого участника сообщите, через какое время после начала экзамена он его завершит.

Формат входных данных

В первой строке вводится натуральное число n — количество участников экзамена (1 ≤ n ≤ 10⁵).

В следующих n строках вводятся данные в следующем формате: первое число i-й строки — количество авторитетов i-го участника (обозначим за m_i), остальные m_i чисел — номера участников, которые являются авторитетами для i-го участника (0 ≤ m_i < n). Участники экзамена не очень сильно знают друг друга, поэтому сумма всех m_i не превосходит 2 * 10⁵.

В следующей строке вводится последовательность натуральных чисел t₁, t₂, ..., t_n (1 ≤ t_i ≤ 10⁹).

В последней строке вводится последовательность целых чисел c₁, c₂, ..., c_n ( − 1 ≤ c_i < m_i). Если c_i =  − 1, то i-й участник будет выполнять задания, не обращая внимания на своих авторитетов.

Формат выходных данных

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

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

5
0
1 3
1 1
0
1 4
8 5 3 8 2
-1 0 0 -1 0

8 3 3 8 2 

Задача 2S. Новые ценики ≡

Условие

В DNS Ритейл существует n видов товаров, и продавцы-консультанты очень жалуются на их ценообразование, т.к. им часто нужно перепечатывать ценники.

Цена меняется каждый час следующим образом:

1. Сначала все виды условно расставляются в ряд слева направо по возрастанию их цен. После этого для каждого вида вычисляется его новая цена, равная сумме цен видов справа от неё.
2. А после того, как новая цена стала известна для всех видов, выполняется стандартный алгоритм (legacy-код, который никто не решается поменять), и к каждому виду применяет операцию взятия остатка от деления цены на 10⁹ + 7. Считается, что это делается для того, чтобы не было слишком больших цен.

Сегодня цены на товары равны 1, 2, 3, 4, … , n денежных единиц.

Продавцы-консультанты уже перестали каждый день удивляться новой странной цене на товары. Но им очень интересно, к чему такая система может привести в будущем, поэтому просят вас о не менее странной просьбе: выяснить сумму цен всех видов товаров в тот же день в тот же час ровно через k веков.

Считается, что в дне 24 часа. В каждом году 365 дней (В DNS ритейл не знают что такое високосные года). Век равен 100 годам.

Формат входных данных

В единственной строке входных данных находится два числа: n - количество видов товаров и k - количество веков. (1 ≤ n ≤ 50, 1 ≤ k ≤ 5).

Формат выходных данных

Выведите одно число - сумму цен через k веков.

Пояснение к примерам:

В первом примере понятно, что уже через один час цена единственного вида станет равна нулю, потому что нет товара справа от него. Так что по аналогии и через век цена будет также равна нулю. Во втором примере цены на товар выглядят следующим образом: В начале их цена [1, 2], а через час цены станут равны [2, 0], а еще через час [0, 2] и так далее. И также по аналогии через век сумма цен будет равна 2.

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

1 1

0

2 1

2

3 1

1704755427

Задача 3K. Линейная комбинация функций ≡

Условие

Вам даны n различных функций, i-я функция задана каким-либо многочленом p_i(x) степени d_i. Найдите такие вещественные коэффициенты k_i, что график q(x) = k₁ p₁(x) + k₂ p₂(x) + ...  + k_n p_n(x) является прямой.

Формат входных данных

В первой строке вводится натуральное число n - количество функций (2 ≤ n ≤ 300).

В следующих 2n строках вводятся функции в следующем виде: в первой строке вводится число d_i - степень i-го многочлена (1 ≤ d_i ≤ 300). В следующей строке вводятся d_i + 1 вещественных чисел, j-е число равно c_ij, которое показывает коэффициент перед x^j (обратите внимание, что 0 ≤ j ≤ d_i, а также что  − 100 ≤ c_ij ≤ 100). То есть i-й многочлен имеет вид c_i0 * x⁰ + c_i1 * x¹ + ... + c_idi * x^d_i.

Формат выходных данных

Если невозможно подобрать коэффициенты таким образом, чтобы график функции q(x) являлся прямой, в единственной строке выходного файла выведите IMPOSSIBLE. В противном случае в первой строке выведите POSSIBLE, во второй строке выведите n вещественных чисел, где i-е число равно k_i ( − 10⁶ ≤ k_i ≤ 10⁶). Ваше решение будет принято, если полученная функция на промежутке [ − 100; 100] отходит от некоторой прямой не более, чем на 10^− 3.

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

2
2
5 2 -4
2
-2 -6 8

POSSIBLE
2 1

Задача 5L. Игровой движок ≡

Условие

Всем известно, что игра DOOM 1993 года написана на языке программирования C. Программист Александр очень любит ставить эту игру на самые необычные и непредназначенные для этого устройства, такие как экран микроволновой печи или домашний электронный градусник.

Однако Александр тот ещё олд и считает, что язык C недостаточно старый, поэтому он решил переписать игру на язык Паскаль.

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

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

Формат входных данных

В первой строке входных данных задано два числа H и W - высота и ширина экрана в пикселях. (1 ≤ H, W ≤ 2000).

Во второй строке располагается число N - количество врагов на сцене. (0 ≤ N ≤ 500).

В следующих N строках располагается по 5 чисел. Первые четыре числа x₁, y₁, x₂, y₂ - концы одной из диагоналей прямоугольника в пикселях. После чего идет число d - расстояние до врага. (1 ≤ x₁, x₂ ≤ W,   1 ≤ y₁, y₂ ≤ H,   1 ≤ d ≤ 10⁹).

Каждая из сторон прямоугольников параллельна какой-то стороне экрана.

Враги могут накладываться друг на друга, то есть быть в одной точке на одном расстоянии.

Формат выходных данных

Выведите матрицу A размера H × W, в которой элемент A_{i, j} равен расстоянию до ближайшего врага в пикселе с координатами (i, j). Если в этом пикселе нет врагов, то выведите 0.

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

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

0 0 0 0 0 
0 0 2 2 0 
0 1 1 1 1 
0 1 1 1 1 
0 0 2 2 0 

3 3
2
1 3 2 2 1
2 1 3 2 1

1 1 0 
1 1 1 
0 1 1 

Задача 6E. Mark II ≡

Условие

На сайте drom.ru есть n объявлений о продаже машин марки Mark II. Цены в объявлениях, конечно, разные, и иногда бывает прямо слишком большой разброс.

Аналитики дрома решили, что надо заняться регулировкой цен. Они придумали стратегию:

• Выбирается объявление a с наименьшей ценой. Если таких объявлений несколько, то выбирается объявление с наименьшим номером.
• После чего выбирается объявление b по номеру следующие за объявлением a. Если a — последнее объявление, то b — первое.
• Цену объявления a увеличивают на единицу, а цену объявления b уменьшают на единицу.
• Эту процедуру продолжают, пока не купят какую-либо машину. Известно, что машину покупают, когда её цена становится меньше или равной k.

Машину могут купить и в самом начале, до какого-либо изменения цен.

Формат входных данных

В первой строке располагаются два числа n и k — количество объявлений и минимальная цена покупки. (2 ≤ n ≤ 10⁵,   0 ≤ k ≤ 10⁹).

Во второй строке располагаются n чисел a_i, где a_i — цена в объявлении с номером i. (0 ≤ a_i ≤ 10⁹).

Формат выходных данных

Выведите номер объявления, машину с которого купили. Если вдруг таких объявлений несколько, выведите объявление с наименьшим номером. А если таких объявлений вовсе нет, то выведите -1.

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

2 1
2 2

2

3 0
1 3 1

-1

5 5
8 7 6 5 4

4

Задача 6N. Доска объявлений ≡

Условие

Farpost — самый популярный классифайд Дальнего Востока, где ежедневно публикуются миллионы объявлений.

Быть в топе на Фарпосте — задача со звёздочкой. Один из факторов, который на это влияет — рейтинг продавца (по оценкам покупателей).

Представим, что вы берёте проект на практике в Фарпосте и хотите помочь продавцам скорректировать их поведение на сайте для достижения высокого рейтинга.

Вам нужно проанализировать рейтинг продавца за последние N дней.

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

Кажется не очень сложным, да?)

Но из-за защиты персональных данных пользователей (в том числе и продавцов) вы не можете напрямую получить рейтинг продавца. Такие данные есть только у наших сотрудников.

Зато у вас есть возможность отправить небольшое количество запросов в систему.

Запросы могут быть только 2 видов:

1. «? rating» - где rating это произвольное целое значение рейтинга на ваш выбор. В ответ вы получите целое число, где первые N битов указывают было ли у продавца в i день рейтинга не меньше, чем rating.
2. «! k i₁ i₂ ... i_k» - отправить ответ, где k - целое число, количество правильных изменений тренда. А i₁, ..., i_k - номера дней, в которых произошёл правильный разворот тренда.

Чтобы вас не забанили как бота, вы можете отправить не более 90 запросов.

Формат входных данных

В первой строке входных данных идет целое число N.

Формат выходных данных

В запросе с ответом, позиции экстремумов должны идти по возрастания. Так же обращаю внимание, что номера дней: 0 ≤ i_j < N.

Каждый вопрос и вывод ответа должны заканчиваться символом перевода строки, а также необходимо выполнять сброс буфера flush()

Примечание

i позиция называется правильным разворотом, если h_i − 1 > h_i < h_i + 1 или h_i − 1 < h_i > h_i + 1.

Напоминаем, что биты нумеруются справа налево.

Ограничения

1 ≤ n ≤ 31

 − 10¹⁷ ≤ h_i ≤ 10¹⁷

|h_i − h_i − 1| ≤ 1, где h_i - целое число, значение в i день на графике.

Описание 1 примера:

Первый запрос: во все дни рейтинг больше или равен 97.

Второй запрос: только в первый, второй и четвёртый дни рейтинг больше или равен 99.

Третий запрос: во все дни рейтинг меньше чем 101.

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

7
127
11
0

? 97
? 99
? 101
! 2 2 3

15
32760
0
32765
2016

? 0
? 4
? -1
? 2
! 4 5 6 7 13

Задача 7I. Дерево отрезков ≡

Условие

У Максима есть массив a размера n. Назовём подмассив от i до j правильным, если его размер (j − i + 1) равен степени двойки 2^k для некоторого k. Максим выбирает какой-то правильный подмассив, на котором он строит дерево отрезков.

Дерево отрезков - это структура данных, которая представляет собой иерархическое дерево.

• Каждый узел дерева соответствует определенному отрезку.
• Листья дерева представляют собой базовые отрезки размера 1, то есть непосредственно элементы массива.
• Значение во внутреннем узле равно сумме значений дочерних узлов.
• Если внутренний узел соответствует отрезку от i до j, то левый дочерний узел будет соответствовать отрезку от i до i + j − 12, а правый от i + j + 12 до j.
• Значение в корне дерева равно сумме значений всех элементов массива, на котором строится дерево отрезков.

После этого Максим нумерует вершины дерева следующим образом: У корня будет номер 1, далее у его левого сына номер 2, а у правого номер 3. После этого он нумерует детей вершины номер 2, а потом вершины номер 3. И так далее он проводит эту операцию последовательно по возрастанию номеров вершин.

И уже после нумерации Максим находит его любимое число, характеризующее подмассив - сумму значений в узлах с нечетным номером. Это число Максим называет характеристикой подмассива.

Так как Максим очень любит эти числа, он просит вас найти сумму характеристик всех возможных правильных подмассивов массива a. Так как ответ может быть слишком большим, выведите его по модулю 10⁹ + 7.

Формат входных данных

В первой строке находится одно целое число n - размер массива. (n ≤ 10⁶).

Во второй строке располагается n чисел - значения массива a.

Формат выходных данных

Выведите одно целое число - сумму характеристик всех возможных правильных подмассивов массива a по модулю 10⁹ + 7.

Пояснение к первому примеру:

Всего существует 8 правильных подмассивов:

• [1]: массив размера 1, дерево отрезков из одного элемента, номер которого 1, поэтому его характеристика равна 1.
• [2], [3], [4] - аналогично.
• [1, 2] - массив размер 2, дерево отрезков состоит из 3 узлов, корня и двух дочерних листьев. В корне находится значение 3. Корень имеет номер 1, а также элемент 2 имеет номер 3, поэтому характеристика этого подмассива равна 3 + 1 = 4.
• [2, 3], [3, 4] - аналогично.
• [1, 2, 3, 4] - массив размера 4, дерево отрезков из 7 узлов. Его структура показана на рисунке 1. Из рисунка видно что характеристика этого массива равна 10 + 7 + 2 + 4 = 23.

Итого сумма всех характеристик: (1 + 2 + 3 + 4) + ((3 + 2) + (5 + 3) + (7 + 4)) + (10 + 7 + 2 + 4) = 57.

Дерево отрезков с номерами узлов.

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

4
1 2 3 4

57

3
3 1 330

1000

1
41

41

Задача 8H. Интересные моменты ≡

Условие

Пётр решил приукрасить свою страницу во ВКонтакте. А именно привести в порядок свои фотографии. Так получилось, что некоторые фотографии у него интересные, а некоторые не очень. И вот Петя решил испробовать методику интересных моментов.

Интересный момент возникает, когда пара интересных фотографий идут друг за другом. То есть, например, трое подряд идущих интересных фотографий создадут 2 интересных момента.

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

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

Формат входных данных

В первой строке входных данных располагается число n — количество уже имеющихся фотографий на странице Петра в ВК. (1 ≤ n ≤ 10⁵).

Во второй строке находится последовательность из n нулей и единиц, в которой если на i-й позиции находится единица, то фотография с номером i интересная. И не интересная, если i-й позиции находится ноль.

Далее располагается число q — количество действий Петра (0 ≤ q ≤ 10⁵).

В следующих q строках находится описание действий Петра:

• если строка начинается с символа i, то это означает, что Пётр хочет вставить фотографию. Далее следует два числа p и v. ( − 1 ≤ p ≤ 2 ⋅ 10⁵) — номер фотографии, после которой надо вставить новую. Если p =  − 1, то это означает, что фотографию надо вставить в самое начало. Число v принимает значение 1 или 0 и означает, что новая фотография интересная или не интересная соответственно.
• если строка начинается с символа d, то это означает, что Пётр хочет удалить фотографию. Далее следует одно число p, означающее номер фотографии, которую надо вырвать. (0 ≤ p ≤ 2 ⋅ 10⁵).
• если строка начинается с символа q, то это означает, что Пётр спрашивает вас о количестве интересных моментов на странице. Далее следует два числа l и r. (0 ≤ l ≤ r ≤ 2 ⋅ 10⁵).

Гарантируется, что все заданные номера фотографий существуют на странице (за исключением p =  − 1, но этот случай описан выше).

Нумерация фотографий начинается с нуля.

Формат выходных данных

Для каждого вопроса Петра через пробел выведите количество интересных моментов на странице, начиная с фотографии l и заканчивая фотографией r включительно.

Объяснение примера:

Сначала страница выглядела так: 0111011

Далее тут (0111011) три интересных момента, между 1 и 2 фото, между 2 и 3 фото и между 5 и 6 фото.

Далее тут 01 (11011) два интересных момента.

После этого страница стала выглядеть так: 01101011.

Далее тут (01101011) два интересных момента.

После этого страница стала выглядеть так: 0110111.

Далее тут 0(110111) три интересных момента.

После этого страница стала выглядеть так: 011111.

Далее тут (011111) 4 интересных момента.

После этого страница стала выглядеть так: 11111.

И тут (11111) также 4 интересных момента.

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

7
0111011
10
q 0 6
q 2 6
i 2 0
q 0 7
d 5
q 1 6
d 3
q 0 5
d 0
q 0 4

3 2 2 3 4 4