Соня — одиннадцатиклассница, и в этом году ей надо сдавать единый государственный экзамен по информатике. Она решила начать готовиться заранее и стала решать задачи из вариантов прошлых лет.
В многих заданиях требуется перевести число из одной системы счисления в другую. Соня с легкостью справляется с такими заданиями, но недавно в одном из вариантов ей попалась задача, которая показалась довольно интересной: число \(x\), заданное в десятичной системе счисления, требуется перевести в (−2)-ичную систему счисления.
Формально, записью числа в (−2)-ичной системе счисления называется набор чисел \(a_0, a_1, \dots , a_{n−1}\), каждое из которых равно 0 или 1, причем \(n\) = 1 или \(a_{n−1} \ne 0\) и выполнено равенство:
\(\)x = \sum\limits_{i=0}^{n-1} a_i\cdot (-2)^i\(\)
Например, 3 в (−2)-ичной системе счисления представляется набором (1, 1, 1): действительно, \(1 · (−2)^0 + 1 · (−2)^1 + 1 · (−2)^2 = 1 − 2 + 4 = 3\).
В задаче предлагается перевести в (−2)-ичную систему счисления только одно число, но Соне стало интересно решение этой задачи в общем случае.
После долгих раздумий она обратилась к вам за помощью. Помогите ей перевести заданное число в (−2)-ичную систему счисления.
В единственной строке входного файла записано одно целое число \(x\) — число, которое Соня хочет представить в (−2)-ичной системе
счисления (\(−10^{18} \le x \le 10^{18}\)).
В первой строке выходного файла выведите число \(n\) (\(n \ge 1\)). Во второй строке выходного файла через пробел выведите \(n\) чисел \(a_0, a_1, \dots , a_{n−1}\) — цифры числа \(x\) в (−2)-ичной системе счисления (\(0 \le a_i \le 1\)). Если существует несколько ответов, выведите любой из них.
3
3 1 1 1
-2
2 0 1
После ряда утечек конфиденциальной информации общественность всерьез задумалась о том, какие пароли следует использовать. Например, пароль «11111» — простой и его не следует использовать. Но как определить, хороший ли пароль?
Фондом Стандартизации Бизнес-процессов было проведено исследование, показавшее, что хороший пароль должен быть достаточно длинным и содержать символы разных видов. Исследование показало, что в хорошем пароле должно быть ровно n символов. Пароль должен состоять из заглавных и строчных букв латинского алфавита и цифр и удовлетворять следующим требованиям:
- в пароле должно быть хотя бы \(a\) заглавных букв;
- в пароле должно быть хотя бы \(b\) строчных букв;
- в пароле должно быть хотя бы \(c\) цифр;
- в пароле не должно быть двух одинаковых идущих подряд символов.
Помогите Фонду, напишите программу, которая по заданным параметрам генерирует подходящий пароль.
В первой строке входного файла задано целое число \(n\) — требуемая длина пароля (\(1 \le n \le 100\)).
Во второй строке заданы неотрицательные целые числа \(a\), \(b\) и \(c\) — минимальное необходимое число заглавных букв, строчных букв и цифр, соответственно (\(a + b + c \le n\)).
В единственной строке выведите любой хороший пароль. Допустимо использовать только заглавные и строчные латинские буквы, а также цифры.
8 2 5 1
ABababa0
В Лайнландии есть одна очень важная дорога, имеющая форму прямой на плоскости. Зимой дорогу часто засыпает снегом, и коммунальные службы стараются оперативно ее очищать.
Лайнландские метеорологи предсказали, что сегодня ночью пройдет снегопад. Они даже в точности смогли описать его ход. Ровно в полночь над страной сформируется облако, из которого будет непрерывно падать снег. Можно считать, что облако представляет собой выпуклый многоугольник, если смотреть на него сверху.
Также метеорологи прогнозируют очень сильный и изменчивый ветер. Благодаря этому ветру траекторией движения облака будет ломаная. Движение облака за ночь можно разбить на несколько участков. Каждый участок задается вектором перемещения облака, во время перемещения вдоль участка облако движется прямолинейно, при этом каждая точка облака перемещается на заданный вектор, облако не меняет форму и не поворачивается.
Каждая точка дороги, над которой пролетит облако, будет покрыта снегом. Коммунальные службы хотят как можно быстрее расчистить дорогу от снега. Для этого они хотят знать общую длину дороги, которая окажется покрыта снегом с утра. Помогите им найти эту величину.
Рисунок показывает перемещения облака и покрытую снегом часть дороги в первом примере.
В первой строке содержится описание дороги. Она задается двумя различными точками, которые на ней лежат. Каждая точка описывается двумя целыми числами \(x, y\) (\(−10^8 \le x, y \le 10^8 \)).
Далее следует описание облака в виде выпуклого многоугольника. В первой строке записано целое число \(n\) — количество вершин многоугольника (\(3 \le n \le 10^5\) ). В следующих \(n\) строках содержится описание положения облака в полночь, каждая строка содержит два целых числа \(x_i\) и \(y_i\) — начальное положение \(i\)-й вершины (\(−10^8 \le x_i , y_i \le 10^8\) ). Вершины заданы в порядке обхода многоугольника против часовой стрелки.
В следующей строке задано целое число \(m\) — количество изменений направления ветра (\(0 \le m \le 10^5\) ). В следующих \(m\) строках записано, как изменилось положение облака в течение очередного участка времени. Каждый участок характеризуется двумя целыми числами \(dx_i\) и \(dy_i\) — на сколько переместилось облако по каждой координате за время \(i\)-го участка (\(−10^3 \le dx_i , dy_i \le 10^3\) ). Гарантируется, что хотя бы одно из этих двух чисел не равно нулю.
Выведите одно вещественное число — общую длину дороги, которая покрыта снегом. Ответ будет считаться верным, если он имеет относительную или абсолютную погрешность не более \(10^{−9}\) .
0 3 1 3 4 -4 2 -5 2 -5 1 -4 1 2 6 3 2 -4
4.5
0 0 1 1 5 1 -2 3 -2 3 -1 2 0 1 -1 4 -1 1 1 1 -7 0 0 -20
5.65685424949238
Пруд черепахи Тортиллы сильно изменился с момента последнего посещения Буратино. Теперь он представляет собой прямоугольное поле из \(w\) столбцов и \(h\) строк, в некоторых клетках которого расположены кувшинки. На этих кувшинках в солнечные дни греются многочисленные дети, внуки и правнуки Тортиллы.
На пруду находится набор из n связных кувшинок. Набор кувшинок называется связным, если от любой кувшинки можно дойти до любой другой, переходя по кувшинкам, смежным по стороне.
Черепахи очень любят ходить друг к другу в гости. Когда одна черепаха решает нанести визит другой, она строит некоторый маршрут, проходящий через смежные по стороне кувшинки и соединяющий ее кувшинку с кувшинкой своей знакомой. Однако неподвижный образ жизни черепах накладывает серьезные ограничения на возможные маршруты — перед началом движения черепаха выбирает некоторые два из четырех возможных направлений перемещения (вверх, вниз, влево, вправо) и затем может переходить с кувшинки на кувшинку только в одном из этих двух направлений.
Например, на приведенном ниже рисунке черепахе с кувшинки \(A\), желающей нанести визит черепахе с кувшинки \(B\), нужно выбрать направления вверх и влево, чтобы иметь возможность проложить маршрут. С другой стороны, черепаха с кувшинки C не имеет возможности добраться до кувшинки \(A\), так как на любом пути, соединяющем их кувшинки, потребуется перемещаться по меньшей мере в трех направлениях.
По итогам семейного совещания Тортилла приняла решение последовательно добавить к \(n\) имеющимся кувшинкам \(q\) новых.
Ваша задача — до начала добавлений и после каждого добавления определить, является ли набор кувшинок удобным для черепах. Тортилла гарантирует вам, что после каждого очередного добавления набор кувшинок остается связным.
В первой строке находятся два целых числа \(h\), \(w\) — количество строк и столбцов в клетчатом поле, которым является пруд (\(1 \le h, w \le 10^5\)).
В следующей строке находится целое число n — количество кувшинок в пруду в начальный момент (\(1 \le n \le 10^5\)).
В последующих \(n\) строках находится по два целых числа \(r_i , c_i\) — для каждой кувшинки заданы номера строки и столбца, на пересечении которых она находится (\(1 \le r_i \le h, 1 \le c_i \le w\)).
В следующей строке находится целое число \(q\) — количество кувшинок, которые собирается добавить Тортилла (\(0 \le q \le 100 000\)).
В последующих \(q\) строках в аналогичном формате заданы пары целых чисел \(nr_i\) , \(nc_i\) , обозначающие соответственно номер строки и номер столбца клетки с очередной добавленной кувшинкой (\(1 \le nr_i \le h, 1 \le nc_i \le w\)).
Гарантируется, что никакие две кувшинки во входных данных не совпадают. Гарантируется, что исходно и после каждого добавления набор кувшинок является связным.
Выведите \(q+1\) строку, каждая из которых представляет собой либо слово «YES», либо слово «NO», в зависимости от того, является ли на очередной момент времени система кувшинок удобной для черепах или нет. Первая строка должна содержать ответ для начального расположения кувшинок, каждая из последующих должна содержать ответ после очередного добавления кувшинки.
5 10 8 1 4 2 4 2 5 2 6 1 6 3 5 3 4 4 4 4 1 5 2 7 3 7 3 6
NO YES YES NO YES
3 3 5 1 1 1 2 1 3 2 3 3 3 4 2 1 3 2 3 1 2 2
YES NO NO NO YES
Дед Афанасий решил подлатать забор вокруг своего деревенского участка. В прошлом году он как раз строил сарай, так что доски для ремонта у него остались.
Забор состоит из n сегментов, каждый из которых представляет собой доску высотой \(a_i\) . У деда есть тележка, на которой лежит стопка из m досок, про каждую из которых известна ее длина \(b_i\) .
Дед Афанасий идет вдоль забора и катит перед собой тележку с досками. Если он хочет увеличить высоту текущего сегмента, он может взять доску с тележки и прибить ее сверху. Тогда новая высота сегмента будет равна сумме изначальной высоты сегмента и длины прибитой доски. Дед не хочет прибивать больше одной доски к каждому сегменту забора, чтобы сохранить его прочность.
Собираясь увеличить высоту сегмента забора, Афанасий поступает следующим образом. Он либо использует для увеличения сегмента верхнюю доску с тележки, либо выкидывает одну или несколько верхних досок с тележки и использует следующую доску. Силы у Афанасия уже не те, поэтому он никогда не возвращается назад вдоль забора и никогда не подбирает выкинутые ранее доски.
Перед началом работы дед задумался, какую максимальную высоту может иметь забор после починки. Высотой забора Афанасий считает высоту самого низкого сегмента забора. Помогите деду Афанасию узнать, какую максимальную высоту забора он сможет получить.
В первой строке входного файла находится целое число n — количество сегментов в заборе (\(1 \le n \le 10^5\) ). Во второй строке содержатся n целых чисел \(a_1, a_2, \dots , a_n\) — высоты сегментов забора, перечисленные в том порядке, в котором мимо них пройдет дед Афанасий (\(1 \le a_i \le 10^8 \)).
В третьей строке находится целое число \(m\) — количество досок на тележке (\(1 \le m \le 10^5\) ). В четвертой строке содержатся m целых чисел \(b_1, b_2, \dots , b_m\) — длины досок на тележке, начиная с верхней (\(1 \dots b_i \le 10^8\) ).
В первую строку выходного файла выведите два целых числа \(h\) и \(k\) — максимальную возможную высоту забора и количество досок, которые деду следует использовать при починке. В следующих \(k\) строках выведите по два целых числа \(x_i\) и \(y_i\) , которые означают, что к \(x_i\)-му сегменту забора деду следует прибить доску с номером \(y_i\) .
Если существует несколько способов починить забор требуемым образом, выведите любой из них.
3 10 5 10 1 5
10 1 2 1
6 2 5 4 1 7 5 7 2 3 1 3 2 4 6
5 3 1 2 3 3 4 6