Информатика

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

Юный волшебник Айвен считает последовательность символов магической, если она является палиндромом (то есть читается одинаково как слева направо, так и справа налево). Айвену попалась в руки последовательность символов s. Он хочет удалить из нее любое (возможно нулевое) количество символов, чтобы получить из нее самую длинную магическую подпоследовательность. 
Определите длину самой длинной магической подпоследовательности, которую сможет получить Айвен.

Входные данные
Программа получает на вход последовательность символов s (1<= |s| <= 1000), состоящую из строчных английских букв. 

Выходные данные
Выведите одно число - длину самой длинной магической подпоследовательности.
 
 

Примеры

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

Находясь на планете Малого Арктура, Алиса и Громозека отправились в зоопарк. Этот зоопарк известен тем, что в нем можно увидеть головастов - рептилий, которые обитают только на этой планете. Чтобы получить доступ к рептилиям, им необходимо ввести код на входе в зоопарк. Однако, код постоянно меняется и всегда равен минимальному числу, не меньшему, чем записанное на экране перед входом и состоящему только из цифр 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

Исполнитель “Раздвоитель” преобразует натуральные числа. У него есть две команды: “Вычесть 1” и “Разделить на 2”, первая команда уменьшает число на 1, вторая команда уменьшает число в два раза, если оно чётное, иначе происходит ошибка.

Входные данные
Программа получает на вход два натуральных числа A и B (по одному числу в строке).

Выходные данные
Напишите алгоритм для Развоителя, который преобразует число A в число B и при этом содержит минимальное число команд. Команды алгоритма нужно выводить по одной в строке, первая команда обозначается, как -1, вторая команда как :2.
 
 

Примеры

№	Входные данные	Выходные данные
1	21 2	-1 :2 :2 -1 :2

 

Примеры

№	Входные данные	Выходные данные
1	1	YES
2	4	YES
3	5	NO

Максимус очень любит коллекционировать кристаллы. Среди всех кристаллов у него есть один самый любимый с магической силой равной n. Также у него есть коллекция совершенных кристаллов. Совершенный кристалл - это кристалл, магическая сила которого равна квадрату натурального числа.
У Максимуса выдался свободный вечер, и он задумался: сколько нужно ему совершенных кристаллов, чтобы сумма их магических сил равнялась бы магической силе его любимого кристалла?
Квадратом натурального числа является число, которое получается умножением натурального числа на себя. Например, 1, 4 и 9 - это квадраты натуральных чисел, а 2, 3 и 5 - нет.
Ваша задача - помочь Максимусу найти минимальное количество совершенных кристаллов, сумма магических сил которых равна n.

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

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	12	3	12 = 4 + 4 + 4
2	13	2	13 = 4 + 9

У Максимуса есть коллекция волшебных амулетов, каждый из которых обладает своей магической силой. Список имеющихся у него амулетов отсортирован в порядке неубывания магической силы. Вернувшись из очередного путешествия, Максимус составил список новых амулетов, предварительно отсортировав их по невозрастанию магической силы. Теперь у него два отдельных списка и он хочет объединить их в один упорядоченный по неубыанию список. 
Он хочет сделать это как можно быстрее. Помогите ему отсортировать два этих списка. Максимус просит вас написать программу, которая будет работать за O(len(A)+len(B)). 
 

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

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

Примеры

№	Входные данные	Выходные данные
1	1 5 7 2 4 4 5	1 2 4 4 5 5 7

В числовом массиве из N чисел переставьте местами элемент с индексом first с элементом, который имеет максимальное значение. Если максимальных элементов несколько, то необходимо взять последний из них (максимальный элемент с большим индексом). Индексация элементов начинается с 0.

Входные данные
В первой строке записаны через пробел два числа N - количество элементов одномерного массива и число first. Во второй строке записаны N чисел numsi - элементы массива.

Ограничения
1 <= N <= 105
-109 <= numsi <= 109
0 <= first < N

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

Примеры

№	Входные данные	Выходные данные
1	5 2 1 -2 -1 2 -2	1 -2 2 -1 -2

Прибор автоматической фиксации нарушений правил дорожного движения делает цветные фотографии размером 768х1024 пикселей, используя палитру из 65536 цветов. Для передачи снимки группируются в пакеты по 128 штук. Определите размер одного пакета фотографий в Мбайт.
В ответе запишите только число.
 

Прибор автоматической фиксации нарушений правил дорожного движения делает цветные фотографии размером 768х1024 пикселей, используя палитру из 16777216 цветов. Для передачи снимки группируются в пакеты по 512 штук. Определите размер одного пакета фотографий в Мбайт.
В ответе запишите только число.

Прибор автоматической фиксации нарушений правил дорожного движения делает цветные фотографии размером 768х1024 пикселей, используя палитру из 16777216 цветов. Для передачи снимки группируются в пакеты по 128 штук. Определите размер одного пакета фотографий в Мбайт.
В ответе запишите только число.

Прибор автоматической фиксации нарушений правил дорожного движения делает цветные фотографии размером 768х1024 пикселей, используя палитру из 4096 цветов. Для передачи снимки группируются в пакеты по 1024 штук. Определите размер одного пакета фотографий в Мбайт.
В ответе запишите только число.

Прибор автоматической фиксации нарушений правил дорожного движения делает цветные фотографии размером 768х1024 пикселей, используя палитру из 65536 цветов. Для передачи снимки группируются в пакеты по 1024 штук. Определите размер одного пакета фотографий в Мбайт.
В ответе запишите только число.

Прибор автоматической фиксации нарушений правил дорожного движения делает цветные фотографии размером 768х1024 пикселей, используя палитру из 16777216 цветов. Для передачи снимки группируются в пакеты по 1024 штук. Определите размер одного пакета фотографий в Мбайт.
В ответе запишите только число.

Прибор автоматической фиксации нарушений правил дорожного движения делает цветные фотографии размером 768х1024 пикселей, используя палитру из 65536 цветов. Для передачи снимки группируются в пакеты по 512 штук. Определите размер одного пакета фотографий в Мбайт.
В ответе запишите только число.

 

•  если подъемник проезжает мимо этажа, на котором нажата кнопка вызова, и, при этом,  движется в подходящем направлении, то подъемник останавливается и в него можно зайти.

Примечание

По одну сторону улицы находятся дома с нечётными номерами (1, 3, 5, …), по другую сторону – с чётными (2, 4, 6, …). Дом № 1 находится напротив дома № 2, дом № 3 – напротив дома № 4 и т. д. До соседнего дома нужно идти вдоль по улице одну минуту, неважно, с какой стороны улицы он находится (то есть от дома № 1 нужно идти одну минуту как до дома № 3, так и до дома № 4). До дома, стоящего напротив, идти не нужно.



Громозека вышел на улицу из дома номер A и должен дойти до дома номер B. Определите, сколько минут ему нужно идти вдоль по улице.

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

Входные данные
Программа получает на вход два различных целых положительных числа A и B,не превосходящие 2×10⁹, – номера домов.

Выходные данные
Программа должна вывести одно число – искомое количество минут.

 

Примеры

№	Входные данные	Выходные данные
1	1 8	3

 

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

• Все деньги должны быть распределены.
• Каждый должен получить как минимум 1 рубль.
• Никто не должен получить 4 рубля (это совсем не счастливая сумма).

Определите максимальное количество Счастливчиков, если вы разделите деньги в соответствии с вышеупомянутыми правилами. Если нет способа разделить деньги, верните -1.

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

Ограничения

• 1 <= money <= 200
• 2 <= children <= 30

Выходные данные
Выведите максимальное количество Счастливчиков.
 
 

Примеры

№	Входные данные	Выходные данные
1	20 3	1
2	16 2	2

 

Примеры

№	Входные данные	Выходные данные
1	1
2	5	121
3	562340	3333312222122213312