Информатика

Всем известно, что Цезарь пользовался иногда тайнописью, т. е. неким шифром, изобретенным им самим.
Иногда, чтобы сократить время написания, Цезарь использовал упаковку, принцип которой заключается в удалении повторяющихся букв и замены их на числа, определяющих количество повторений.
Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Данная строка может быть представлена как 4AB5C4D.
Напишите программу, которая берет упакованную строчку и восстанавливает по ней исходную строку.
 

Входные данные
Входные данные содержат одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n — количество повторений символа (целое число от 2 до 99), а A — заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.

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

Примеры

№	Входные данные	Выходные данные
1	ABC	ABC
2	O2A3O2AO	OAAOOOAAO
3	A2B3C4D5E6F7G	ABBCCCDDDDEEEEEFFFFFFGGGGGGG

Ученики, посещавшие школы в Древнем Риме решали на занятиях различные задачи. Вот одна из задач:

101=1

8181515=4

1111112=0

8888888=14

1010101=3

7000007=?

Пусть первое число x, а соответствующее ему n.
Напишите программу, которая по числу x определяет n.

Входные данные 
Единственное неотрицательное число x, не превышающее 10¹⁰⁰¹.

Выходные данные
Выведите n.

Примеры

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

Избрав путь политика и полководца, Цезарь имел немного времени для творческой работы, однако написал сочинения разных жанров: эпическую поэму "Геркулес", трагедию "Царь Эдип", поэму "Путешествие", "Записки о галльской войне" и "Записки о гражданской войне". Были изданы сборники его сентенций, речей, писем. Кроме того, великий полководец интересовался филологией.

Отвлекшись от написания поэмы, Цезарь записал одну под другой две строчки и задумался. Затем он посмотрел на написанные строчки и понял, что первая строка (S) может содержать в себе несколько раз вторую строку (T). Гай Юлий Цезарь решил подсчитать все вхождения строки T в строку S. Помогите ему, напишите соответствующую программу.

Входные данные
Первые две строки входных данных содержат строки S  и T, соответственно. Длины строк больше 0 и меньше 50000, строки содержат только строчные латинские буквы.

Выходные данные
Выведите номера символов, начиная с которых строка T входит в строку S, в порядке возрастания (по одному значению в строке).
 

Примеры

№	Входные данные	Выходные данные
1	ababbababa aba	0 5 7

Гай Юлий Цезарь (13 июля, или из других источников, 12 июля 100 или 102 гг. до н. э. — 15 марта 44 г. до н. э.) — древнеримский государственный и политический деятель, диктатор, полководец, писатель. Своим завоеванием Галлии Цезарь расширил Римскую державу. Деятельность Цезаря коренным образом изменила культурный и политический облик Западной Европы и оставила неизгладимый след в жизни следующих поколений европейцев. Гай Юлий Цезарь, обладая блестящими способностями военного стратега и тактика, одержал победу в сражениях гражданской войны и стал единовластным повелителем Pax Romana.

Цезарь часто брал бумагу и писал письма во время гладиаторских боёв. Его спросили, мол, как вы и на гладиаторов можете смотреть и письма писать. На что Цезарь ответил: «Цезарь может делать три дела одновременно: и писать, и смотреть, и слушать».

Юлий Цезарь, чтобы скрыть информацию от врагов, использовал свой способ шифрования текста. Каждая буква заменялась на следующую по алфавиту через K позиций по кругу.

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

Входные данные
В первой строке дана шифровка, состоящая из заглавных латинских букв. Во второй строке число K (\(1 <= K <= 10\)).

Выходные данные 
Требуется вывести результат расшифровки.
 

Примеры

№	Входные данные	Выходные данные
1	XPSE 1	WORD

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

Про каждую задачу известно время ti, которое нужно затратить, чтобы сделать её, а также прибыль pi, которую сделанная задача принесёт компании. Вы хотите включить в план некоторые задачи так, чтобы:

• Суммарное время, затраченное на выполнение задач, включённых в план, не превышало T.
• Суммарная прибыль от выполнения этих задач была максимальна.

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

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

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

В первой строке  находятся натуральные числа T (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) - число единиц времени в месяце и число задач.

Следующие n строк содержат по два натуральных числа ti и pi (1 <= t_i, p_i <= 100 000) - время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.

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

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

 

Примеры

№	Входные данные	Выходные данные
1	10 3 8 100 3 10 3 10	100
2	10 4 5 10 5 20 2 5 2 6	31

Дано N отрезков провода длиной L1, L2, ..., LN сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.
 

Формат входных данных
В первой строке находятся числа N и K. В следующих N строках L1, L2, ..., LN, по одному числу в строке.

Ограничения 

• 1 <= N <= 10 000,
• 1 <= K <= 10 000,
• 100 <= Li <= 10 000 000,
• все числа целые.

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

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

Дана последовательность натуральных чисел, признаком конца которой является число 0 (0 не входит в последовательность). Определите количество строгих локальных максимумов в этой последовательности. 

Числа, следующие за числом 0, считывать не нужно.

Входные данные: Дана последовательность натуральных чисел, признаком конца которой является число 0.
Выходные данные: Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	1 2 1 2 1 0	2

Дана последовательность натуральных чисел, завершающаяся число 0 (0 не входит в последовательность). Определите наибольшую длину монотонного фрагмента последовательности (то есть такого фрагмента, где все элементы либо больше предыдущего, либо меньше).

Числа, следующие за числом 0, считывать не нужно.

Входные данные: Дана последовательность натуральных чисел, завершающаяся число 0.

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

Примеры

№	Входные данные	Выходные данные
1	1 7 7 8 1 0	2

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

Входные данные: Даны два неравных числа: n и m, не превосходящие 31.
Выходные данные: Выведите на экран значение суммы 2ⁿ+2^m.

Примеры

№	Входные данные	Выходные данные
1	1 2	6

Напишите программу, которая обнуляет последние k бит у числа  N. Выведите на экран полученное число.

В программе нельзя использовать арифметические операции, необходимо использовать только битовые операции!
 

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

Дано целое число N и натуральное число k.

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

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

 

Примеры

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

 
 

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

•  Налить воду в первую колбу до края (после этого в ней будет a миллилитров воды)
•  Полностью вылить воду из первой колбы
•  Налить воду во вторую колбу до края (после этого в ней будет b миллилитров воды)
•  Полностью вылить воду из второй колбы
•  Перелить воду из первой колбы во вторую. В этом случае, если во второй колбе достаточно места, чтобы уместить всю текущую воду первой колбы, вода из первой колбы переливается полностью во вторую. Если же во второй колбе места недостаточно, вторая колба заполняется до предела (в ней после этого будет b миллилитров воды), а в первой колбе остается все остальное.

Состоянием колб Вася называет упорядоченную пару (x, y), где x — текущее количество воды в первой колбе, а y— во второй. Вася хочет изучить поставленную самим собой задачу и понять, сколько различных состояний он может получить описанными выше переливаниями.
Входные данные
В единственной строке входного  через пробел записаны два натуральных числа a и b (1 ≤ a, b ≤ 100) — емкости первой и второй колбы соответственно.
Выходные данные
В единственной строке выходного выведите одно число — число различных состояний, которое можно получить описанными в задаче переливаниями воды.
 

Ввод	Вывод
2 5	14

Недавно Вася решил, что все существующие алгоритмы сортировки слишком сложны, и обязательно должен существовать более простой и эффективный алгоритм.
Для начала Вася решил рассмотреть следующий алгоритм: по данному массиву целых чисел a размером n, он создает пустой массив b, а дальше на каждой из n последующих итераций будет брать k-й элемент массива a (или последний, если такого нет), удалять его из a, а затем записывать в конец b. Таким образом, после n итераций Вася планирует в качестве массива b получить отсортированный по возрастанию массив a.
Однако, протестировав на нескольких примерах, Вася понял, что этот алгоритм работает не всегда. Так, например, если исходный массив a=[1,2,3,4] и k=2, то после 4 итераций массив b вовсе не будет отсортированным:
После первой итерации в b добавляется число 2, а массив a равен [1,3,4];
После второй итерации в конец b добавляется число 3, а массив a равен [1,4];
После третьей итерации в конец b добавляется число 4, а массив a равен [1];
На последней, четвертой итерации, в конец b добавляется число 1, а массив a становится пустым;
Таким образом, итоговый массив b будет выглядеть так: [2,3,4,1]. Нетрудно заметить, что он не является отсортированным по возрастанию. Однако, Вася решил так легко не сдаваться и по данному числу k научиться находить такой массив a, содержащий перестановку последовательности натуральных чисел от 1 до n, который будет сортироваться по возрастанию методом, описанным выше. Помогите ему - по данным числам n и k найдите хотя бы один подходящий массив a.

Формат входных данных
В единственной строке содержится два числа n и k - размер массива и номер элемента, берущегося на каждой итерации, соответственно (1≤k≤n≤1000).

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

Ввод	Вывод
5 1	1 2 3 4 5
5 5	5 4 3 2 1

Юлий Цезарь использовал свой способ шифрования текста. Каждая буква заменялась на следующую по алфавиту через K позиций по кругу. Необходимо по заданной шифровке определить исходный текст.

Входные данные:  в первой строке дана шифровка, состоящая из заглавных латинских букв. Во второй строке число K (\(1 <= K <= 10\)).

Выходные данные: требуется вывести результат расшифровки.
 

Примеры

№	Входные данные	Выходные данные
1	XPSE 1	WORD
2	ZABC 3	WXYZ

Петя играет с друзьями в игру, которую иногда называют "Жребий Крижановского". Правила игры следующие: в каждом туре каждый игрок загадывает произвольное натуральное число. После этого игрок, загадавший минимальное число, которое не повторяется, выигрывает в этом туре, причем его выигрыш равен этому числу. Например, если играют 6 человек и были загаданы числа 3, 2, 1, 1, 4 и 2, то выиграл первый игрок, причем его выигрыш равен 3. Если все загаданные числа повторяются, то тур считается ничейным и никто баллов не получает.

Общий выигрыш игрока за игру равен сумме баллов за все сыгранные туры.

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

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

Входные данные
В первой строке вводится число n - количество игроков (2 <= n <= 100). Вторая строка содержит n чисел - баллы игроков перед последним туром (неотрицательные целые числа, не большие 100). Баллы перечислены в том порядке, в котором игроки обычно называют числа (то есть Петины баллы указаны последними). В третьей строке задано (n-1) число - числа, названные игроками в последнем туре (числа не превышают 100), в том порядке, в котором они их называли.

Выходные данные
Выведите число, которое следует назвать Пете.

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

Ввод	Вывод
6 0 0 0 0 0 0 2 3 4 5 6	1
6 8 3 12 5 0 9 2 1 3 1 4	2

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

Входные данные
Вводится одна строка, состоящая только из латинских букв и цифр. Количество символов в строке не превышает 100.

Выходные данные
Выведите слово YES, если указанный пароль является криптостойким, и NO – в противном случае.
 

Примеры

№	Входные данные	Выходные данные
1	e	NO
2	AAAbbb123	YES

Дано слово.
Выведите:
1) в первой строке - это слово в обратном порядке символов (читая справа налево);
2) слово YES, если исходное слово, является палиндромом (слово, которое одинаково читается как слева направо, так и справа налево). В противном случае - NO
 

Примеры

№	Входные данные	Выходные данные
1	mama	amam NO

мчмс