Задачи олимпиады "Школьный этап ВОШ Красноярского края по информатике, 7-8 классы"

Задача A. Игра

Иван и Денис играют в следующую игру на круглом столе с радиусом T. У них есть неограниченное количество одинаковых круглых монет с радиусом M. Они поочередно выкладывают монеты на стол, не меняя расположения ранее размещенных на столе монет. При этом нельзя, чтобы монеты прикасались друг к другу. Проигрывает тот, кто на очередном ходе не сможет разместить свою монету. Иван ходит первым.

Требуется определить победителя при условии, что ребята играют оптимально.

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

Первая строка входного файла INPUT.TXT содержит целое число M – радиусы монет, во второй строке содержится целое число T – радиус стола (0 < M ≤ T ≤ 100).

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

В выходной файл OUTPUT.TXT выведите имя победителя: Ivan (если выиграет Иван) или Denis (если выиграет Денис).

Пример

Подсказка

Иван точно что-то знает о симметрии.

Задача B. Шахматная доска

Шахматная доска состоит из N строк и M столбцов: всего N×M клеток, покрашенных в чёрный и белый цвет в шахматном порядке. При этом клетка в левом нижнем углу доски покрашена в чёрный цвет. Определите, сколько всего на доске чёрных клеток.

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

В первой строке входного файла INPUT.TXT содержится целое число N – количество строк шахматной доски, вторая строка содержит целое число M - количество столбцов шахматной доски (1 ≤ N, M ≤ 10⁹).

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

В выходной файл OUTPUT.TXT выведите единственное целое число – ответ на задачу.

Пример

№	INPUT.TXT	OUTPUT.TXT	Рисунок
1	3 4	6

Система оценки

Решения, работающие только для N ≤ 10 и M ≤ 10, будут оцениваться в 40 баллов.

Задача C. Ограбление в парке

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

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

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

В первой строке входного файла INPUT.TXT записаны два числа: L – длина лавочки и K – количество гранитных блоков-ножек. Оба числа натуральные и не превышают 10 000.

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

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

В выходной файл OUTPUT.TXT требуется вывести координаты ножек, которые грабителям нужно оставить. Для каждой ножки нужно выдать ее положение. Ножки следует перечислять слева направо, как они встречаются во входных данных.

Примеры

Примечание

Второй пример соответствует лавочке на рисунке.

Задача D. Шахматобокс

Шахматобокс - командная игра, объединяющая два известных вида спорта: шахматы и бокс. В результате соревнований каждая команда получает рейтинговые баллы, которые вычисляются на основании составленного протокола соревнований для данной команды. Протокол представляет собой таблицу из N строк и M столбцов, заполненную символами "+", "-" или "?". Здесь "+" означает число +1, "-" означает число -1, а "?" говорит о том, что данный результат пока не определен в связи с тем, что соревнования еще не закончились. Таким образом, в начале соревнований таблица состоит только из знаков "?", а по мере проведения соревнований знаки "?" заменяются либо на "+", либо на "-". По окончанию соревнований в таблице нет знаков неопределенности "?". После чего рейтинговый балл команды равен разности суммы в строке с наибольшей суммой и суммы в столбце с наименьшей суммой.

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

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

В первой строке входного файла INPUT.TXT записаны целые числа N и M (1 ≤ N, M ≤ 1000) – количество строк и столбцов в протоколе команды соответственно. Далее идут N строк по M символов, содержащие символы "+", "-" и "?".

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

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

Пример

Пояснение

В примере максимальный рейтинговый балл может быть равен 5 после следующей замены знаков "?":

+-+
+--
--+
+++

Действительно, после такой замены в четвертой строке сумма равна 3, а во втором столбце она равна -2, таким образом получаем рейтинговый балл: 3 - (-2) = 5.

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

Система оценки

Решения, работающие только для 1 ≤ N, M ≤ 100, будут оцениваться в 50 баллов.

Задача E. Ханойская башня

A	B	C

Многим известна классическая задача о ханойской башне. Напомним ее условие.

Имеется три стержня: A, B и C. На один из стержней нанизаны N колец, причем кольца пронумерованы от 1 до N сверху вниз и номер каждого кольца соответствует его диаметру. Таким образом, на каждом кольце лежит кольцо меньшего диаметра. Требуется перенести данную пирамиду из N колец с одного стержня на другой с выполнением следующих двух условий:

• за один раз разрешается переносить только одно кольцо;
• нельзя класть большее кольцо на меньшее.

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

• один из стержней должен использоваться при каждом перекладывании кольца (каждый раз мы должны перекладывать кольцо либо с него, либо на него);

Поясним последнее условие. Пусть стержень B должен всегда использоваться. Это означает, что допустимы только следующие перекладывания кольца: с A на B, с C на B, с B на A и с B на C. А перекладывания с A на C и с C на A при этом недопустимы.

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

Первая строка входного файла INPUT.TXT содержит натуральное число N – количество колец (N ≤ 10). Во второй строке через пробел записаны значения S, D и M (M может отсутствовать) – это соответственно исходный стержень, конечный стержень и стержень, который обязательно должен использоваться при каждой операции перекладывания кольца. В том случае, когда M отсутствует, следует решать классическую задачу без третьего условия. Гарантируется, что S≠D и S, D и M – прописные латинские символы (A, B или C – имена стержней).

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

В выходной файл OUTPUT.TXT выведите последовательность перемещений, в результате которой все N колец будут перемещены со стержня S на стержень D через стержень M (если указан). Каждую операцию перекладывания кольца необходимо вывести в отдельной строке через пробел: номер кольца, исходный стержень и конечный стержень. При этом алгоритм не обязательно должен быть оптимальным, но нельзя использовать более 100 000 операций.

Примеры

Пояснение

В примере №5 приведена классическая задача для трёх колец, иллюстрация решения которой представлена ниже:

Исходное положение	1. Операция "1 A C"	2. Операция "2 A B"	3. Операция "1 C B"
4. Операция "3 A C"	5. Операция "1 B A"	6. Операция "2 B C"	7. Операция "1 A C"

Система оценки

Решения, работающие только для N ≤ K (1 ≤ K ≤ 10), будут оцениваться в 10×K баллов.

Решения, работающие только для классической задачи (в случае отсутствия во входных данных информации о стержне M) будут оцениваться в 60 баллов.