#1051

Пекка развлекается

Темы: ["Длинная" арифметика]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2006, 1 тур, Задача B ]

#1088

Темы: [НОД и алгоритм Евклида] [Цикл for]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2006, Задача F ]

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

Он изготовил трафарет NxN клеток (N — четное), в котором вырезал клеток так, что при наложении трафарета на лист бумаги четырьмя возможными способами (трафарет можно поворачивать, но нельзя переворачивать) каждая клетка листа видна ровно один раз.

Пример такого трафарета показан на рисунке ниже:

С помощью этого трафарета шифруется текст из N² символов следующим образом. Сначала в прорези трафарета вписываются первые букв шифруемого текста (буквы вписываются в вырезанные клетки по строкам сверху вниз, в каждой строке — слева направо). Например, если Петя шифрует слово ОЛИМПИАДА, то оно будет вписано в клетки следующим образом:

О				Л
	И		М
				П
		И			А
Д
			А

Далее трафарет поворачивается на 90 градусов по часовой стрелке, и в вырезанные клетки в том же порядке вписываются следующие букв шифруемого текста. И так далее. Если шифруемый текст состоит меньше, чем из N² символов, то (когда текст кончается) оставшиеся клетки остаются пустыми.

Например, если Петя шифрует текст ОЛИМПИАДА ПО ИНФОРМАТИКЕ 2006 ГОДА при помощи приведенного трафарета, то процесс шифрования будет устроен так. Как зашифровать слово ОЛИМПИАДА, мы уже показали. Для удобства здесь и далее пробел будем обозначать знаком подчеркивания. При втором прикладывании трафарета Пете удастся зашифровать _ПО_ИНФОР:

О	_			Л	П
	И		М	О
		_		П
И		И		Н	А
Д			Ф		О
		Р	А

При третьем прикладывании трафарета Петя зашифрует МАТИКЕ_20:

О	_	М		Л	П
	И		М	О	А
Т		_	И	П
И	К	И		Н	А
Д		Е	Ф	_	О
	2	Р	А		0

При четвертом прикладывании трафарета Петя зашифрует 06_ГОДА. Остальные клетки окажутся пустыми (будем считать, что в них записан пробел, который мы обозначаем подчеркиванием):

О	_	М	0	Л	П
6	И	_	М	О	А
Т	Г	_	И	П	О
И	К	И	Д	Н	А
Д	А	Е	Ф	_	О
_	2	Р	А	_	0

После этого получившийся текст Петя выписывает в строчку:

О М0ЛП6И МОАТГ ИПОИКИДНАДАЕФ О 2РА 0

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

Напишите программу, которая для данного трафарета определит, после какого наименьшего количества процедур шифрования Петя получит исходный текст независимо от содержания текста?

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

Сначала во входном файле записано число N — размер трафарета (2≤N≤150). Затем идет N² чисел (каждое из которых 0 или 1), описывающих трафарет. 1 обозначает вырезанную клетку, 0 — не вырезанную. Гарантируется, что данная последовательность описывает корректный трафарет для данного способа шифрования.

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

В выходной файл выведите одно число — через какое минимальное количество повторов операции шифрования Петя получит исходный текст независимо от его содержания.

Примеры

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

2
1 0
0 0

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

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

6
1 0 0 0 1 0
0 1 0 1 0 0
0 0 0 0 1 0
0 0 1 0 0 1
1 0 0 0 0 0
0 0 0 1 0 0

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

#1153

Две строки

Темы: ["Длинная" арифметика]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2008 (четвертый интернет-этап), восток, Задача A ]

Циклическим сдвигом строки s₀s₁…s_n_-1 на k позиций назовем строку s_ks_k₊₁…s_ns₁..s_k_-1. Например, циклическим сдвигом строки «abcde» на две позиции является строка «cdeab». В этой задаче далее будут рассматриваться только строки, состоящие из десятичных цифр от 0 до 9. Произвольной такой строке, первый символ которой не является нулем, можно сопоставить число, десятичной записью которого она является. Строкам, которые начинаются с нуля, никакое число сопоставляться не будет. Например, строке 123 сопоставляется число сто двадцать три, а строке 0123 не сопоставляется никакое число.

Пусть заданы две строки: s и t. Обозначим как S набор всех циклических сдвигов строки s, а как T – набор всех циклических сдвигов строки t. Например, если s = «1234», то S содержит строки «1234», «2341», «3412», «4123». Обозначим также как NUM(A) набор чисел, соответствующих строкам из набора A.

Требуется написать программу, которая по строкам s и t определит, максимальное число, представимое в виде разности (x – y), где x принадлежит NUM(S), а y принадлежит NUM(T). Например, если s = «25», t = «12», то NUM(S) содержит числа 25 и 52, NUM(T) – числа 12 и 21; их попарными разностями будут: 25 – 12 = 13, 25 – 21 = 4, 52 – 12 = 40, 52 – 21 = 31. Из этих разностей максимальным числом является 40.

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

Первая строка входного файла содержит строку s, вторая строка входного файла – строку t. Обе строки непустые. Они содержат только цифры, из которых хотя бы одна не является нулем. Строки имеют длину не более 3000 символов.

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

В выходной файл выведите искомое число без ведущих нулей.

Примеры

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

25
12

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

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

100
1

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

#1202

Операции

Темы: [Конечные автоматы] [НОД и алгоритм Евклида]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2006, 2 тур, Задача A ]

#1210

Неправильное сложение

Темы: ["Длинная" арифметика]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2009, 2 день, Задача B ]

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

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

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

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

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

Входной файл содержит в одной строке три целых числа a, b и c (1 ≤ a, b, c ≤ 1 000 000). Все числа в строке разделены пробелом.

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

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

В последующих строках выходного файла необходимо вывести все возможные суммы, которые можно получить, складывая числа a, b и c. Суммы следует выводить по одной на строке и в порядке их возрастания.

Разбалловка для личной олимпиады

Тесты 1-2 — из условия. Оцениваются в 0 баллов.

Тесты 3-8 — все входные числа не превосходят 99. Группа тестов оценивается в 24 балла.

Тесты 9-16 — все входные числа не превосходят 9999. Группа тестов оценивается в 32 балла (вместе с предыдущей группой — 56 баллов).

Тесты 17-27 — дополнительных ограничений нет. Группа тестов оценивается в 44 балла (вместе с предыдущими группами — 100 баллов).

Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп. При выставлении баллов за отдельные тесты каждый тест (кроме тестов из условия) оценивается в 4 балла.

Примеры

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

30 239 566

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

YES
7945
71215

О	_	М	0	Л	П
6	И	_	М	О	А
Т	Г	_	И	П	О
И	К	И	Д	Н	А
Д	А	Е	Ф	_	О
_	2	Р	А	_	0

О	_	М	0	Л	П
6	И	_	М	О	А
Т	Г	_	И	П	О
И	К	И	Д	Н	А
Д	А	Е	Ф	_	О
_	2	Р	А	_	0

О	_	М	0	Л	П
6	И	_	М	О	А
Т	Г	_	И	П	О
И	К	И	Д	Н	А
Д	А	Е	Ф	_	О
_	2	Р	А	_	0