Задание А. Двоичные последовательности

Петя и Ваня, два ученика 8 класса,  бросали монетку. Они совершили очень много бросков и результат каждого записывали: ставили 0, если выпала “решка”, и 1, если выпал “орел”. Требуется определить, сколько раз встретилась в данной последовательности комбинация из следующих выбрасываний “решки” и “орла”? Например, комбинация “решка”, “орел”, “решка” (или просто 010) в последовательности 10101 встретится один раз.

Формат входных данных: В первой строке сперва N, затем M (количество бросков и длина искомой комбинации, 1<=M<=100, M<=N<=109). Во второй строке через пробел вводится комбинация, которую ищут игроки. Дальше вводится последовательность бросков.

Формат выходных данных: вывести количество вхождений искомой комбинации в данную последовательность.

Задание B. Удвоение числа

Ученик 8 класса Петя еще плохо умеет работать с числами в разных системах счисления. На этот раз ему задали домашнее задание: удвоить число, записанное в некоторой системе счисления. К сожалению, Петя не самый усердный ученик: он знает число, но забыл указать, в какой системе счисления оно записано. Однако он помнит, что в записи присутствует наибольшая цифра данной системы счисления.

На уроках в 8 классе Пете приходится иметь дело с разными системами счисления, вплоть до системы с основанием 36. Для записи таких чисел применяют цифры от 0 до 9 и буквы латинского алфавита: A означает 10, B - 11, C - 12 … Z - 35. Помогите Пете: запишите результат умножения числа на 2.

Формат входных данных: В первой строке записано число (количество разрядов в чиcле <=250). В записи числа обязательно присутствует максимальная цифра данной системы счисления.

Формат выходных данных: Записать результат умножения в этой же системе счисления.

Задание С. Злостные прогульщики

В Городском  классическом лицее, где учатся восьмиклассники Петя и Ваня, встречаются прогульщики. Мальчики решили автоматизировать учет прогульщиков. Для этого они всю неделю записывали фамилии и имена тех, кто пропустил занятие. К концу недели получился большой список. Теперь необходимо пересчитать, сколько раз в списке встречается каждый прогульщик и указать возле его имени, сколько уроков он пропустил.

Затем мальчики решили распечатать список только тех учеников, кто имеет N и более пропусков. Список должен быть отсортирован от более злостных прогульщиков к менее злостным. Если в списке есть ученики с одинаковым числом пропусков, их необходимо сортировать в алфавитном порядке.

Формат входных данных: В первой строке указано количество записей в списке M (1<=M<=105) и N (1<=N<=M) - количество пропусков, при достижении которого ученик попадает в “черный список”. Далее по строкам записаны фамилии и имена  учеников. Фамилия состоит из латинских букв и не более 25 символов, Имя – не более 15 символов.

Формат выходных данных: Вывести по строкам фамилии и имена учеников из “черного списка”, а также количество пропущенных уроков для каждого прогульщика. Сортировать записи по убыванию количества прогулов. При равном количестве прогулов, сортировать по фамилии и имени в алфавитном порядке. Если таких прогульщиков нет, то вывести сообщение «No truants».

Задание D. Великие стратеги

Два ученика 8 класса, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча из S камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 17 или 30 камней. У каждого игрока есть неограниченное количество камней, чтобы делать ходы. Игра завершается в тот момент, когда количество камней в куче становится не менее N. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет N или более камней.

В начальный момент в куче было S камней. Определите, кто из игроков выиграет при безошибочной игре обоих и на каком ходе?

Игроки придерживаются следующих принципов:

• каждый играет безошибочно, по выигрышной стратегии;
• при прочих равных обстоятельствах, игрок делает такой ход, чтобы противник не мог выиграть как можно дольше.

Формат входных данных: В первой строке водится число S, а во второй - N (1<=S<N<=100).

Формат выходных данных: В первой строке вывести имя победителя. Во второй строке - номер хода игрока, который приведет его к победе при безошибочной игре обоих игроков.

Задание E. Король и пешки

Восьмиклассники Петя и Ваня любят играть в шахматы. А еще они любят разные шахматные головоломки. На этот раз Петя придумал для Вани задачу: на шахматной доске поставил белого короля и N черных пешек. Король бьет пешки и ходит по обычным шахматным правилам (т.е. не вставая на битое поле пешки), но в отличие от обычной шахматной игры, пешки не могут перемещаться по доске после хода короля, но могут “бить” короля со своей позиции, так же как и король может “бить” пешку. Ване надо определить, может ли король с исходной клетки попасть на другую, и если может, то указать кратчайший путь.

Формат входных данных: В первой строке записаны координаты короля, затем координаты клетки, в котору необходимо прийти. Далее идет N -  число пешек (N <=63), а потом N  координат пешек.

Формат выходных данных: Вывести количество ходов короля, а далее сами ходы. Если таких ходов нет, вывести NO. Если вариантов ходов несколько, то вывести любой из них.