Язык программирования

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

Человека можно представить в виде таблицы размера N × M, заполненной некоторыми целыми числами. Сумма чисел в строке таблицы символизирует то, каким человека видят люди (чем больше сумма, тем более просветленным в этой области дзен считается человек). Сумма чисел в столбце символизирует реальные познания человека (чем она меньше, тем меньше человек знает, причем если сумма чисел отрицательна, то представления человека ложны). Нужно заполнить таблицу любыми целыми числами так, чтобы сумма чисел в каждой строке таблицы была положительной (то есть человек внешне казался абсолютно просветленным), а сумма чисел в как можно большем количестве столбцов была отрицательной (то есть представления человека о дзен на самом деле были по большей части ложными).

Помогите монаху дзен приблизиться к просветлению и решить предложенную мастером задачу.

Входные данные
Вводятся числа N (1 ≤ N ≤ 100) и M (1 ≤ M ≤ 100) — количество строк и столбцов в таблице. Числа разделены пробелом.

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

Примеры

№	Входные данные	Выходные данные
1	3 4	3 8 13 -40 21 -17 -4 18 12 6 -10 13 -5
2	3 5	4 1 2 3 4 5 5 4 3 2 1 -7 -8 -7 -8 40

Алиса и Боб — очень опытные шпионы. Лучше всего им удается находить пароли для доступа к различным секретным данным. Вот и в этот раз Алиса получила от Боба сообщение, в котором говорилось, что ключом является число и далее шло само это число. Также Боб писал, что число-ключ должно делиться на 9. Когда Алиса попробовала ввести полученный пароль, то оказалось, что он не подходит. Алиса очень доверяет Бобу, и поэтому она решила, что Боб мог ошибиться только в одной цифре пароля. Поскольку у Алисы не так много времени, она решила не выяснять у Боба правильный ответ, а перебрать все числа, которые могли бы быть паролем, т.е. все такие числа, которые могут быть получены из того числа, которое прислал Боб, заменой ровно одной из его цифр и делятся на 9. За помощью Алиса обратилась к вам. Напишите программу, которая предложит Алисе все возможные варианты пароля.

Входные данные
Во входных данных содержится единственное число P (1 ≤ P ≤ 10⁹) — то число, которая Алиса получила в сообщении от Боба. Гарантируется, что оно не начинается с нуля.

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

Примеры

№	Входные данные	Выходные данные
1	256	756 216 252

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

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

Входные данные
В первой строчке вводится N — количество слов в cловаре (1 ≤ N ≤ 103). В следующих N строчках вводятся слова — строки длиной не более 255 символов, состоящие только из маленьких латинских букв. Слова отсортированы в алфавитном порядке.

Выходные данные
Выведите искомый пароль. Если подходящих паролей несколько, выведите тот, который идёт в словаре позже всех остальных.

Примеры

№	Входные данные	Выходные данные
1	7 arhimed computer contest informatics programming python team	python

Как непросто быть школьником! Именно такие мысли чаще всего посещают Петю после уроков математики. Сегодня учительница рассказывала, что такое простые числа. Петя впервые услышал о них. Оказывается, простое число — это такое натуральное число, которое имеет ровно два различных натуральных делителя, то есть делится без остатка только на единицу и на само себя. После урока Петя и его друг Сережа придумали такую игру: один называет два числа A и B, а другой говорит, сколько нулей на конце произведения всех простых между A и B включительно. Петя заметил, что Сережа отвечает на вопрос намного быстрее, чем он сам, и очень просит вас ему помочь. Напишите для Пети программу, которая будет отвечать на вопросы Сережи.

Входные данные
На вход подается два числа A, B (1 ≤ A ≤ B ≤ 10⁹), разделенных пробелом. Гарантируется, что между A и B есть хотя бы одно простое число.

Выходные данные
Выведите количество нулей, на которое заканчивается произведение всех простых чисел на отрезке от A до B.

Примеры

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

Саша и Лиза — две самые обычные девочки, которые живут в Москве и очень любят Санкт-Петербург. На каникулы они запланировали обширную экскурсионную программу в северной столице, осталось только купить билеты. Девочки знают, что быстрее всего добраться до Санкт-Петербурга можно на скоростном поезде «Сапсан». В каждом вагоне есть N рядов, в каждом из которых по 4 места, которые нумеруются так:

Саша и Лиза выбрали вагон, в котором они планируют ехать. Оказалось, что в этом вагоне уже продано M билетов и известно, какие места уже заняты. Девочки решили купить билеты таким образом:

• если есть два места рядом, то они покупают их (например, 1 и 2 или 3 и 4)
• если двух мест рядом нет, то они пытаются купить места рядом через проход (например, 2 и 4)
• если нет и таких мест, то они покупают любые два свободных места.

Помогите Саше и Лизе определить, какие места им стоит купить. Гарантируется, что в выбранном вагоне есть как минимум два свободных места.

Входные данные
В первой строке входных данных содержатся числа N — количество рядов в вагоне (1 ≤ N ≤ 10⁵) и M — количество проданных билетов (1 ≤ M ≤ 4N - 2). В следующей строке записаны M различных чисел — номера мест, на которые билеты уже проданы.

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

Примеры

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

Дано алгебраическое выражение, состоящее из натуральных чисел, переменных (a, b, c, ..., z) записанных строчной латинской буквой, знаков арифметических операций  + ,  - ,  *  (умножение) и  *  *  (возведение в степень). При этом если после числа идет переменная, то знак умножения может быть пропущен.

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

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

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

Примеры

№	Входные данные	Выходные данные
1	2x+5	1 0
2	x**y**2z*3*5	3 2

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

Каждый игрок похвастал, сколько у него тузов. Определите, сколько игроков заведомо солгали.

Например, они сказали 1, 1, 1, 2. Следовательно, заведомо солгал 1 игрок. (Какие-то трое могли сказать правду, но все четверо правду сказать не могли, так как тузов всего 4).

Входные данные
Вводятся 4 числа (от 0 до 9 каждое), разделенных пробелом – количество тузов по словам первого, второго, третьего и четвертого игроков.

Выходные данные
Выведите одно число – минимальное количество игроков, которые заведомо солгали. Если все одновременно могли сказать правду, выведите число 0.

Примеры

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

Представьте число 2011 в виду суммы K последовательных простых чисел (то есть простых чисел, между которыми нет других простых чисел). Например, число 31 можно представить в виде суммы трех посдедовательных простых чисел следующим образом: 7 + 11 + 13 = 31.

Входные данные
Вводится одно натуральное число K (от 1 до 2011).

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

Если разложить в сумму K слагаемых невозможно, выведите NO SOLUTION (заглавными буквами).

Примеры

№	Входные данные	Выходные данные
1	3	661 673 677
2	2	NO SOLUTION

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

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

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

Примеры

№	Входные данные	Выходные данные
1	2011	2022
2	1	7

Магическим квадратом называют таблицу, в которой записаны числа 123…  по одному разу, так что сумма чисел в каждой строке и в каждом столбце равные. Мы расскажем вам об одном из методов построения магических квадратов (его называют сиамским). Он годится только для построения квадратов с нечетной стороной (3355…) .

Поставим число 1 в верхнюю клетку центрального столбца. Далее будем двигаться по диагонали вправо-вверх, расставляя в клетки последовательно числа 234… . Если мы вышли за пределы таблицы вверх, то нужно перейти к нижней клетке того же столбца и продолжить с нее. Если мы вышли за правую границу, нужно перейти к левой клетке той строки, куда мы должны были попасть. Если же мы одновременно вышли и вверх, и вправо, то нужно перейти в левую нижнюю клетку квадрата.

Если в следующей клетке на нашем пути уже стоит число, то вместо хода “вправо-вверх” нужно сделать ход “вниз” (опять же, если мы при этом выйдем за границы квадрата, нужно перейти к верхней клетке того же столбца). Примеры для квадратов 33 и 55 показаны на рисунках.



Входные данные
На вход подается одно натуральное нечетное число N, не превосходящее 30 – размер квадрата.

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

Примеры

№	Входные данные	Выходные данные
1	3	8 1 6  3 5 7  4 9 2
2	5	17 24 1 8 15  23 5 7 14 16  4 6 13 20 22  10 12 19 21 3  11 18 25 2 9

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

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

Во второй строке в том же формате вводится список имен школьников в том порядке, в котором они стоят по кругу. Считать начинают с первого школьника. Детей не менее двух, а длина строки не превосходит 100.

Выходные данные
Выведите имя школьника, которому предстоит водить.
 

№	Входные данные	Выходные данные
1	To be or not to be John Mary Ann Kate	Mary
2	Na zolotom kryltse sideli Vasya Vasya Vasya	Vasya

Вася, Петя и Коля играли в теннис навылет (проигравший пропускал следующую партию, уступая свое место третьему). Вася утверждает, что сыграл x партий, Петя – что сыграл y партий, Коля – z партий.

Определите, могло ли такое быть.

Входные данные
Вводятся три целых неотрицательных числа x, y, z, не превосходящих 1 000.

Выходные данные
Выведите YES (заглавными буквами), если такое могло быть, и NO в противном случае.

Примеры

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

Подсчитайте количество натуральных чисел на отрезке от a до b, сумма цифр которых четна.

Входные данные
Вводится два натуральных числа a и b, не превосходящие миллиарда (a ≤ b).
Выходные данные
Выведите одно число – количество чисел, больших либо равных a и меньших либо равных b, имеющих четную сумму цифр.

Примеры

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

На доске размером KxN клеток (K строк, N столбцов) в j-й строке и i-м столбце стоит шахматный конь. Может ли он за один или несколько ходов попасть в клетку в m-й строке и s-м столбце?

Входные данные
Вводятся 6 натуральных чисел: K, N, j, i, m, s (1 ≤ K ≤ N ≤ 100). Клетки (i, j) и (s, m) не совпадают.

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

Примеры

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

Комплект шахматного домино состоит из 32 костяшек 2x1, каждая из квадратов которой окрашен в черный или белый цвет (часть костяшек состоит из двух белых квадратов, часть – из двух черных, а часть из одного белого и одного черного). Комплект такого домино выложен на шахматную доску. Разрешается поворачивать костяшки домино на 180 градусов (менять местами их квадраты), оставляя каждую костяшку на своем месте. Требуется выяснить, можно ли так повернуть часть костей домино, чтобы в каждом горизонтальном ряду были квадраты только одного цвета.


Входные данные
Вводится 8 строк по 8 чисел. Каждое число соответствует номеру доминошки, которая покрывает данную клетку. Число положительное, если квадрат доминошки белый и отрицательное – если черный.


Выходные данные
Требуется вывести одно слово – YES или NO (заглавными буквами).

Примеры

№	Входные данные	Выходные данные
1	1   2   2   7   7   8   8   9   1   3   6  10  10  11  11   9   4   3   6  31  31  24  23  12   4   5   5  30  32  24  23  12  28  29  29  30  32  25  22  13  28  27  27  26  26  25  22  13  18  19  19  20  20  21  21  14  18  17  17  16  16  15  15  14	YES

Примечание:
Доминошки нумеруются числами от 1 до 32 в произвольном порядке.
 

Два бегуна тренируются на кольцевой дорожке легкоатлетического стадиона длиной 400 метров. Они начинают бег из одной точки и бегают по заданиям тренера указанное число минут с указанной скоростью (под скоростью понимается количество метров, которое спортсмен пробегает по дорожке  за минуту). Требуется определить расстояние, на котором окажутся бегуны друг от друга в конце тренировки (расстоянием называется длина более короткой части дуги дорожки между спортсменами).

Входные данные
В первой строке вводится одно число – количество заданий, которые каждый спортсмен получил от тренера (оба спортсмена получают одинаковое количество заданий). В каждой из следующих строк записаны задания для спортсменов в следующем формате:

v₁ t₁ v₂ t₂

где v₁ – скорость  первого игрока (в м/мин), t₁ – время, на протяжении которого спортсмен должен бежать со скоростью v₁; v₂ и t₂ – соответствующие величины для второго игрока. Скорости – положительные числа, если требуется бежать в направлении по часовой стрелке, и отрицательные, если требуется бежать против часовой стрелки.

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

Примеры

№	Входные данные	Выходные данные
1	2 8000 1 8000 1  8000 10 8001 10	10
2	1 50 4 -100 1	100

На одном из московских вокзалов билеты продают N касс. Каждая касса работает без перерыва определенный промежуток времени по фиксированному расписанию (одному и тому же каждый день). Требуется определить, на протяжении какого времени в течение суток работают все кассы одновременно.

Входные данные
Сначала вводится одно целое число N (0 < N ≤ 1000).

В каждой из следующих N строк через пробел расположены 4 целых числа, первые два из которых обозначают время открытия кассы в часах и минутах (часы — целое число от 0 до 23, минуты — целое число от 0 до 59), оставшиеся два — время закрытия в том же формате. Числа разделены пробелами.

Время открытия означает, что в соответствующую ему минуту касса уже работает, а время закрытия — что в соответствующую минуту касса уже не работает. Например, касса, открытая с 10 ч. 30 мин. до 18 ч. 30 мин., ежесуточно работает 480 минут.

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

Выходные данные
Требуется вывести одно число — суммарное время за сутки (в минутах), на протяжении которого работают все N касс.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 1 0 23 0 12 0 12 0 22 0 2 0	120	Первая касса работает с часу до 23 часов, вторая – круглосуточно, третья – с 22 часов до 2 часов ночи следующего дня. Таким образом, все три кассы одновременно работают с 22 до 23 часов и с часу до двух часов, то есть 120 минут.
2	2 9 30 14 0 14 15 21 0	0	Первая касса работает до 14 часов, а вторая начинает работать в 14 часов 15 минут, то есть одновременно кассы не работают.
3	2 14 00 18 00 10 00 14 01	1	Вместе кассы работают лишь одну минуту – с 14:00 до 14:01 (в 14:01 вторая касса уже не работает).

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

Входные данные
Сначала вводится число N (1 ≤ N ≤ 64) – количество выпиленных клеток. В следующих N строках вводятся координаты выпиленных клеток, разделенные пробелом (номер строки и столбца – числа от 1 до 8). Каждая выпиленная клетка указывается один раз.

Выходные данные
Выведите одно число – периметр выпиленной фигуры (сторона клетки равна единице).

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 1 1 1 2 2 1	8	Вырезан уголок из трех клеток. Сумма длин его сторон равна 8.
2	1 8 8	4	Вырезана одна клетка. Ее периметр равен 4.

На вход программы поступает строка текста, в которой могут встречаться:
— прописные и строчные (т.е. большие и маленькие) латинские буквы;
— пробелы;
— знаки препинания: точка, запятая, восклицательный и вопросительный знак;
— символ –, обозначающий в некоторых случаях тире, а в некоторых — дефис.
Слово — это последовательность подряд идущих латинских букв и знаков дефис, ограниченная с обоих концов. В качестве ограничителей могут выступать начало строки, конец строки, пробел, знак препинания, тире. Тире отличается от дефиса тем, что слева и справа от знака дефис пишутся буквы, а хотя бы с одной стороны от тире идет либо начало строки, либо конец строки, либо пробел, либо какой-либо знак препинания, либо еще одно тире.
Напишите программу, определяющую, сколько слов в данной строке текста.

Входные данные
Вводится строка длиной не более 200 символов.

Выходные данные
Выведите одно число — количество слов, которые содержатся в исходной строке.
 
Примеры

№	Входные данные	Выходные данные
1	Hello , world!	2
2	www.olympiads.ru	3
3	Gyro-compass - this is a ...	4

Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:
1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.

Входные данные
Сначала вводится число N — количество элементов исходной последовательности (1 ≤ N ≤ 100). Далее идут N чисел — элементы этой последовательности, натуральные числа от 1 до 9.

Выходные данные
Выведите сначала число M — минимальное количество элементов, которое надо дописать к последовательности, а потом M чисел (каждое — от 1 до 9) — числа, которые надо дописать к последовательности.

Примеры

№	Входные данные	Выходные данные
1	9 1 2 3 4 5 4 3 2 1	0
2	5 1 2 1 2 2	3 1 2 1
3	5 1 2 3 4 5	4 4 3 2 1