Страница: << 1 2 3 4 >> Отображать по:

#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

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

#1181

Благозвучное слово

Темы: [Строки] [Цикл for]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Москва, 2008, Задача D ]

Все буквы латинского алфавита делятся на гласные и согласные. Гласными буквами являются: a, e, i, o, u, y. Остальные буквы являются согласными.

Слово называется благозвучным, если в этом слове не встречается больше двух согласных букв подряд и не встречается больше двух гласных букв подряд. Например, слова abba, mama, program — благозвучные, а слова aaa, school, search — неблагозвучные.

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

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

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

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

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

Комментарии к примерам тестов

1. Слово уже является благозвучным.

2. Достаточно добавить одну гласную букву, например, между буквами s и с

Примеры

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

program

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

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

school

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

#1224

Математическое казино

Темы: [Цикл for] [Условный оператор (if)]

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

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

Перед началом каждого раунда программа сообщает, на какую тему будет очередная математическая задача и Саша делает ставку на то, что он ее решит. В самом начале игры Саша всегда делает ставку в 1 мани. Если Саша решает задачу правильно, то он выигрывает раунд и ставка плюсуется к его счету. Если он допускает ошибку в решении, то он проигрывает, и ставка вычитается из его счета. Саша очень самоуверенный и любое неверное решение задачи считает чистой случайностью, поэтому после проигрыша Саша всегда увеличивает ставку в 2 раза. Однако после выигрыша, дабы не вспугнуть удачу, Саша всегда снижает ставку до 1 мани. Наконец, одолев очередную задачу, и выиграв этот раунд, Саша решает закончить игру.

Например, пусть Саша правильно решил первую задачу (выиграл начальную ставку в 1 мани, поставил на следующий раунд 1 мани), затем неправильно решил вторую задачу (проиграл 1 мани и удвоил ставку), неправильно решил и третью задачу (проиграл 2 мани и снова удвоил ставку), но четвертую задачку ему все-таки удалось решить правильно (выиграл 4 мани, сбросил ставку на 1 мани). Затем он правильно решает и пятую задачу (выиграл 1 мани) и заканчивает игру. Итого на его счету после игры: 1 – 1 – 2 + 4 + 1 = 3 мани.

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

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

Первая строка содержит целое число N (0 < N ≤ 2000) — количество задач, которое решал Саша. Во второй строке располагаются N чисел 0 или 1 через пробел: 0, если Саша решил очередную задачку неправильно, и 1 – если правильно.

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

Выведите одно целое число — выигрыш или проигрыш Саши (выигрыш определяется положительным числом, а проигрыш – отрицательным).

Примеры

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

5
1 1 0 1 1

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

#1252

Тестирование

Темы: [Цикл for]

Источники: [ Личные олимпиады, Индивидуальная олимпиада по информатике и программированию (ИОИП), Заключительный этап 2009, Задача A ]

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

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

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

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

Первая строка входного файла содержит число n (1 ≤ n ≤ 100000) вопросов в тесте. Вторая строка входного файла содержит n целых чисел a1, a_{2, . . . , an} — номера правильных вариантов ответов на каждый из вопросов. Третья строка входного файла содержит n целых чисел b₁, b₂, . . . , b_n — номера вариантов, выбранных тестируемым. Для чисел a_{i и b_i верны неравенства 1 ≤ a_{i, b_i ≤ 10.}}

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

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

Примеры

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

4
1 2 3 4
1 2 4 3

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

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

4
1 2 3 4
4 3 2 1

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

#1370

Фибоначчиева последовательность

Темы: [Цикл for]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 7-9 классы, 2009, Задача A ]

По двум известным соседним членам последовательности чисел Фибоначчи и их номерам требуется определить первый и второй члены последовательности.

Последовательность чисел a₁, a₂, …, a_i,… называется Фибоначчиевой, если для всех i≥3 верно, что a_i=a_i_–1+a_i_–2, то есть каждый член последовательности (начиная с третьего) равен сумме двух предыдущих.

Ясно, что задавая различные числа a₁ и a₂ мы можем получать различные такие последовательности, и любая Фибоначчиева последовательность однозначно задается двумя своими первыми членами.

Будем решать обратную задачу. Вам будет дано число N и два члена последовательности: a_N и a_N₊₁. Вам нужно написать программу, которая по их значениям найдет a₁ и a₂.

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

Вводятся число N и значения двух членов последователности: a_N и a_N₊₁ (1≤N≤30, члены последовательности — целые числа, по модулю не превышающие 100)
Если вы пишите на языке программирования python, то считывание a_N и a_N₊₁ элементов должно быть организовано так:
x, y = map(int, input().split())

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

Выведите два числа — значения первого и второго членов этой последовательности.

Примеры

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

4
3 5

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

1 1

Страница: << 1 2 3 4 >> Отображать по:

Выбрано

Отменить

Добавить в контест

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

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

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