Информатика

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

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

Число называется палиндромом, если оно читается одинаково справа налево и слева направо. Например, числа \(121, 66, 98989\) являются палиндромами, а \(103, 239, 1241\) — нет.

После некоторых размышлений Алина поняла, что такое число всегда можно найти. Помогите Алине найти подходящее число!

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(2 \leq n \leq 100\,000\)) — длина числа, которое увидела Алина.

Во второй строке вводится одно положительное целое число длины \(n\). Гарантируется, что оно не содержит ведущих нулей.

Формат выходных данных
Выведите ответ на задачу — положительное целое число без ведущих нулей длины \(n\), такое что его сумма с числом из входных данных будет палиндромом.

Если таких чисел несколько, вы можете вывести любое из них.

В первом примере из условия \(99 + 32 = 131\) — палиндром. Число \(12\) также будет являться ответом, так как \(99 + 12 = 111\).

Во втором примере из условия \(1023 + 8646 = 9669\).

В третьем примере из условия \(385 + 604 = 989\).

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

 

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

Программа получает на вход два натуральных числа N и M, записанных в одной строке через пробел. Числа не превосходят 100.

 

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

Программа должна вывести номер игрока (1 или 2), у которого есть выигрышная стратегия.

Сегодня вечером по телевизору на разных каналах будут показывать n матчей по кёрлингу, причём i-й матч начинается в момент времени l_i и заканчивается в момент времени r_i. 

Василиса хочет посмотреть как можно больше матчей от начала до конца. При этом если какой-то матч заканчивается в момент времени r_i, то она может после него посмотреть любой матч j, который начинается не раньше момента времени r_i, то есть l_j >  r_i (Василиса может моментально переключить каналы в момент окончания матча и начать смотреть новый матч). Также она хочет сделать перерыв длины хотя бы t между какими-то двумя играми, чтобы поужинать, то есть должны найтись два последовательных матча i и j, которые просмотрит Василиса, удовлетворяющие условию l_j - r_i => t. Перерыв не может быть до или после всех просмотренных игр.

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

Формат входных данных
Первая строка входных данных содержит число n  (2 ≤ n ≤ 100 000) -  количество показываемых матчей.
Вторая строка входных данных содержит число t (1 ≤ n ≤ 10⁹) -  минимальная длина перерыва, который должна сделать Василиса.
В следующих n строках содержится по два числа l_i  и r_i  ( 1 ≤ l_i < r_i ≤ 10⁹) -  начало и конец i-го матча.

Формат выходных данных
Программа должна вывести число m - максимально возможное количество матчей, которые просмотрит Василиса. Во второй строке выведите m чисел через пробел - номера матчей, которые должна посмотреть Василиса, в порядке просмотра.
Если Василиса не может составить расписание хотя бы из двух матчей так, чтобы между какими-то двумя матчами был перерыв хотя бы t, то выведите число -1.

Замечание
В первом примере ответом будет последовательность матчей 6, 3, 5. Василиса сначала посмотрит матч 6, 
который заканчивается в момент времени 4, потом переключится на матч 3, который продолжается с 4 до 6. 
Затем она сделает перерыв с 6 по 10, после чего просмотрит матч номер 5 с 10 до 12. Получилось расписание из 3 матчей с перерывом, продолжительность которого равна 4. Заметим, что в данном примере правильным ответом также будет последовательность матчей 6, 4, 5, в этом случае продолжительность перерыва между матчами 4 и 5 будет равна 3.

Во втором примере всего два матча, первый заканчивается в 5, а второй начинается в 9, то есть составить расписание, в котором был бы перерыв продолжительностью не менее t=5, нельзя.
 

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

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

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

Вам необходимо минимизировать количество заданий для печати условий.

Формат входных данных
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 10⁶) - количество задач в олимпиаде.
Вторая строка входных данных содержит целое число n (1 ≤ x_i ≤ 3) - количество страниц в i-й задаче.
Формат выходных данных
Выведите единственное число - минимальное количество последовательных диапазонов, каждый из которых можно напечатать одной командой односторонней или двусторонней печати так, что условия всех задач будут напечатаны в удобном для командной олимпиады виде.

Замечание
В первом примере на олимпиаду предложены 4 задачи, условия которых состоят из 1, 3, 2 и 1 страниц соответственно. Всего необходимо распечатать 7 страниц. Их можно распечатать за два задания: cтраницы 1-2 - односторонней печатью (это единственная страница первой задачи и первая из трёх страниц второй задачи), оставшиеся страницы 3-7 - двусторонней.

Во втором примере на олимпиаду предложены 2 задачи, условия которых состоят из 3 страниц каждая. Всего необходимо распечатать 6 страниц. Их можно распечатать за два задания: cтраницы 1-1- односторонней печатью (это первая из трёх страниц первой задачи), оставшиеся страницы 2-6 - двусторонней. При этом в первой задаче первая страница будет напечатана на одной стороне,  потому что она напечатана односторонней печатью, а во второй задаче последняя страница будет напечатана на одной стороне, потому что в этом задании нечётное число страниц печатается на двух сторонах, поэтому вторая сторона этого листа будет пустой.

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.
Некоторый узел в сети имеет IP-адрес 14.21.90.45. Маской сети 255.255.255.224.
Определите количество IP-адресов компьютеров в этой сети, у которых последний байт в двоичной записи является палиндромом. Последний байт - это последние восемь битов, если считать слева направо. В расчете не учитываются адрес сети и широковещательный адрес.

В ответе укажите только число.

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.
Некоторый узел в сети имеет IP-адрес 143.239.55.145. Маской сети 255.255.255.192.
Определите количество IP-адресов компьютеров в этой сети, у которых последний байт в двоичной записи является палиндромом. Последний байт - это последние восемь битов, если считать слева направо. В расчете не учитываются адрес сети и широковещательный адрес.

В ответе укажите только число.

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.
Некоторый узел в сети имеет IP-адрес 172.61.231.75. Маской сети 255.255.255.240.
Определите количество IP-адресов компьютеров в этой сети, у которых последний байт в двоичной записи является палиндромом. Последний байт - это последние восемь битов, если считать слева направо. В расчете не учитываются адрес сети и широковещательный адрес.

В ответе укажите только число.
 

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.
Некоторый узел в сети имеет IP-адрес 199.130.153.159. Маской сети 255.255.255.224.
Определите количество IP-адресов компьютеров в этой сети, у которых последний байт в двоичной записи является палиндромом. Последний байт - это последние восемь битов, если считать слева направо. В расчете не учитываются адрес сети и широковещательный адрес.

В ответе укажите только число.
 

XOR-cумма массива определяется как побитовое XOR всех его элементов или 0, если массив пуст.

Например, XOR-сумма массива [2,5,6] равна 2 XOR 5 XOR 6 = 1.
Для заданного массива nums, верните сумму всех XOR-сумм для каждого подмножества nums. 

Примечание: подмножества, состоящие из одинаковых элементов, считаются различными и должны подсчитываться несколько раз. 
Массив a является подмножеством массива b, если a может быть получено из b путем удаления некоторых (возможно не удалением никаких) элементов b.
 

Входные данные
Программа получает на вход в первой строке натуральное число n - количество элементов массива nums. Во второй строке записаны n чисел numsi.
 

Ограничения

• 1 <= n <= 12
• 1 <= numsi <= 20

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

Пояснения к тестовым примерам
В первом примере 
В [1,3] существует 4 подмножества:
- Пустое подмножество имеет XOR-сумму 0.
- [1] имеет XOR-сумму, равную 1.
- [3] имеет XOR-сумму, равную 3.
- В [1,3] сумма XOR равна 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Во втором примере
В [5,1,6] 8 подмножеств:
- Пустое подмножество имеет XOR-сумму 0.
- [5] имеет XOR-сумму, равную 5.
- [1] имеет XOR-сумму, равную 1.
- [6] имеет XOR-сумму, равную 6.
- [5,1] имеет XOR-сумму 5 XOR 1 = 4.
- [5,6] имеет XOR-сумму 5 XOR 6 = 3.
- [1,6] имеет XOR-сумму 1 XOR 6 = 7.
- [5,1,6] имеет XOR-сумму 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28


 

В терминологии сетей TCP/IP маскойсети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.
Сеть задана IP-адресом 10.216.237.160 и маской сети 255.255.255.240.
Сколько в этой сети IP-адресов, для которых сумма единиц в двоичной записи IP-адреса нечётна?

В ответе укажите только число.

В терминологии сетей TCP/IP маскойсети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.
Сеть задана IP-адресом 112.246.146.0 и маской сети 255.255.255.0.
Сколько в этой сети IP-адресов, для которых сумма единиц в двоичной записи IP-адреса нечётна?

В ответе укажите только число.

В терминологии сетей TCP/IP маскойсети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.
Сеть задана IP-адресом 190.242.184.0 и маской сети 255.255.255.0.
Сколько в этой сети IP-адресов, для которых сумма единиц в двоичной записи IP-адреса нечётна?

В ответе укажите только число.

В терминологии сетей TCP/IP маскойсети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.
Сеть задана IP-адресом 161.21.209.0 и маской сети 255.255.255.128.
Сколько в этой сети IP-адресов, для которых сумма единиц в двоичной записи IP-адреса чётна?

В ответе укажите только число.

В терминологии сетей TCP/IP маскойсети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.
Сеть задана IP-адресом 93.161.57.192 и маской сети 255.255.255.192.
Сколько в этой сети IP-адресов, для которых сумма единиц в двоичной записи IP-адреса чётна?

В ответе укажите только число.

В терминологии сетей TCP/IP маскойсети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.
Сеть задана IP-адресом 21.10.32.0 и маской сети 255.255.224.0.
Сколько в этой сети IP-адресов, для которых сумма единиц в двоичной записи IP-адреса чётна?

В ответе укажите только число.

В терминологии сетей TCP/IP маскойсети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.
Сеть задана IP-адресом 67.198.113.56 и маской сети 255.255.255.248.
Сколько в этой сети IP-адресов, для которых сумма единиц в двоичной записи IP-адреса чётна?

В ответе укажите только число. 

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети.
Сеть задана IP-адресом 192.168.32.160 и маской сети 255.255.255.240.
Сколько в этой сети IP-адресов, для которых сумма единиц в двоичной записи IP-адреса чётна?

В ответе укажите только число.

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

Входные данные
Программа получает в первой строке два числа: n - количество различных чисел, которые записаны на фишках, num - число, которое загадал Громозека. Во второй строке записаны n различных чисел ci - числа, каждое из которых может быть записано на фишке. На каждой фишке записано только одно число из набора чисел ci. При этом, количество фишек с числом ci не ограниченно. Все фишки с одинаковым числом, считаются одинаковыми. Другими словами, комбинация фишек 2+1 и 1+2 считается одной комбинацией. 

Ограничения

• 1 <= n <= 300
• 1 <= ci <= 5000
• Все значения ci уникальны.
• 0 <= num <= 5000

Выходные данные
Выведите одно число - количество комбинаций, которым Алиса может выиграть Громозеку. Если Алиса не может выиграть, то выведите на экран 0.

Примечание
В первом примере есть 4 способа набрать сумму, равную 5:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
 

Находясь на планете Малого Арктура, Алиса и Громозека отправились в зоопарк. Этот зоопарк известен тем, что в нем можно увидеть головастов - рептилий, которые обитают только на этой планете. Чтобы получить доступ к рептилиям, им необходимо ввести код на входе в зоопарк. Однако, код постоянно меняется и всегда равен минимальному числу, не меньшему, чем записанное на экране перед входом и состоящему только из цифр 3, 6 или 9.
Помогите Алисе и Громозеке определить код доступа к рептилиям.


Входные данные

Ввод содержит одно число n (1 <= n <= 10¹⁸).

Выходные данные

Выведите одно число - код доступа к рептилиям.

Примеры

№	Входные данные	Выходные данные
1	2007	3333
2	97	99

Громозека является одним из ведущих в Галактике космических археологов. Возвращаясь домой с очередной археологической экспедиции, он решил привезти своим четырем детям их любимые печенья. Ему осталось только вбить необходимое количество килограмм на экране терминала, и автомат сразу выдаст ему печенье . Но, вот незадача, на терминале сломались все кнопки с цифрами и буквами. Работают только цифры 0 и 1.  Громозека в задумчивости, как же ему заказать ровно n килограмм. Он придумал, что может сделать несколько заказов таким образом, чтобы каждый заказ мог состоять только из цифр 0 и 1. Вот только Громозека очень торопится, потому что до старта корабля осталось совсем немного времени. Помогите Громозеке определить минимальное число раз, которым ему придется воспользоваться автоматом, чтобы купить ровно n килограмм и порадовать своих детей! 

Например, чтобы купить 12 киллограмм печенья Громозека может воспользоваться автоматом дважды, купив сначала 11 килограмм печенья, затем - 1 килограмм.

Входные данные
Программа получает на вход целое число n (1 <= n <= 10⁹).

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

Примеры

№	Входные данные	Выходные данные
1	1234	4