Задачи олимпиады "II (муниципальный) этап Всероссийской олимпиады школьников Красноярского края по информатике"
Задача A. Карусель
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Карусель – одна из популярных форм проведения командных соревнований по решению задач. Наибольшую известность в использовании данной модели в России получил ресурс «Интернет-карусели», расположенный в сети Интернет по адресу http://karusel.desc.ru.
Всем командам, участвующим в карусели, предлагаются в строгом порядке одни и те же задачи, которые необходимо решить в установленное время. Система подсчета баллов такова, что доминирующим фактором является не количество решенных задач, а длины последовательностей правильных решений.
Начисление баллов происходит согласно следующей схеме:
первая задача стоит 3 балла;
если к задаче дан верный ответ, то команда получает ее стоимость, а следующая задача будет стоить на 1 балл больше;
если на задачу дан неверный ответ, то команда получает за решение 0 баллов, а следующая задача будет стоить на 3 балла меньше, но не менее 3 баллов.
Вам требуется написать программу, которая по результатам ответов команды определит итоговый балл.
Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N – количество задач в карусели (N ≤ 105). Во второй строке расположены N цифр 0 или 1, разделенные пробелом; i-я цифра соответствует корректности ответа команды на i-ю задачу (0 – неверный ответ, 1 – верный ответ).
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – количество набранных баллов.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3 1 1 1
12
2
9 1 0 1 1 1 1 0 1 1
30
Задача B. Крестики-нолики
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Крестики-нолики – логическая игра между двумя противниками на квадратном поле 3 на 3 клетки. Один из игроков играет «крестиками» (тот, кто ходит первым), другой – «ноликами». Игроки по очереди ставят на свободные клетки поля знаки (один всегда «крестики», другой всегда «нолики»). Первый, выстроивший в ряд три своих фигуры по вертикали, горизонтали или диагонали, выигрывает и на этом игра заканчивается. В том случае, когда все клетки заполнены и победитель не определен, игра завершается ничьей.
По состоянию игрового поля в конце игры требуется определить результат игры для первого игрока: выиграл, проиграл или сыграл вничью.
Входные данные
Входной файл INPUT.TXT содержит информацию об игровом поле – три строки по три символа в каждой. Символ «X» (ASCII 88) означает «крестик», символ «O» (ASCII 79) - «нолик», а символ «.» (ASCII 46) - пустую клетку.
Выходные данные
В выходной файл OUTPUT.TXT выведите в случае победы первого игрока «Win», в случае его проигрыша – «Lose» и «Draw» в случае ничьей.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
.OX
.XO
XXO
Win
2
OXO
.OX
OXX
Lose
3
XOX
XOX
OXO
Draw
Задача C. Паутина
(Время: 1 сек. Память: 64 Мб Баллы: 100)
Имеется паутина на плоскости, состоящая из нитей, параллельных осям координат. В основе конструкции паутины лежит бесконечное множество вертикальных нитей, пронумерованных слева направо, начиная с единицы. Смежные вертикальные нити могут быть соединены горизонтальными нитями на некоторой высоте. Для каждой вертикальной нити на определенной высоте может быть не более одного подобного соединения.
На одной из вертикальных нитей, в самом верху (выше всех горизонтальных соединений) находится паук, который начинает свое движение вниз. Натыкаясь на очередную нить, паук меняет свое направление. Движение паука продолжается до тех пор, пока все горизонтальные нити не окажутся выше паука.
По заданной конструкции паутины и начальному расположению паука требуется определить номер нити, на которой окажется паук в конце своего движения.
Входные данные
Первая строка входного файла INPUT.TXT содержит два числа K и M, где K – номер нити, соответствующей начальному положению паука. Далее идут M строк, определяющих горизонтальные соединения, по одному в каждой строке. Каждое такое соединение определяется двумя числами P и H, обозначающие соединение смежных вертикальных нитей с номерами P и P+1 на высоте H. Во входных данных все числа натуральные, имеющие следующие ограничения: K, P, H ≤ 109, M ≤ 105.
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3 6
1 2
3 4
2 5
3 1
1 4
2 3
2
Задача D. Охрана - 2
(Время: 1 сек. Память: 16 Мб Баллы: 100)
В одном из секретных учреждений в целях безопасности установлены два инфракрасных датчика движения. Каждый датчик позволяет контролировать пространство, ограниченное формой прямоугольного параллелепипеда. Причем, датчики в здании установлены таким образом, что все грани охраняемых датчиками граничных зон параллельны стенам здания. При этом охраняемые зоны могут пересекаться, совпадать, включаться одна в другую и т.д.
По заданным координатам охраняемых зон необходимо определить общий объем территории, покрываемой датчиками.
Входные данные
Входной файл INPUT.TXT содержит две строки, каждая из которых определяет охраняемую датчиком зону. Каждая зона определяется 6 целыми числами x1, y1, z1, x2, y2, z2, где (x1, y1, z1) и (x2, y2, z2) – координаты противоположных вершин правильного параллелепипеда. Все числа записаны через пробел и не превосходят 104 по абсолютной величине.
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – совокупный объем охраняемой территории.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
0 0 0 2 2 2 3 3 3 4 4 4
9
2
0 0 3 3 3 0 2 2 2 4 4 4
34
Задача E. Кубик Рубика
(Время: 3 сек. Память: 16 Мб Баллы: 100)
Кубик Рубика – популярная головоломка в форме куба, состоящая из множества мелких кубиков. Каждая видимая сторона такого кубика окрашена в определенный цвет. Повороты сторон кубика позволяют переупорядочить цветные квадраты множеством различных способов. Целью игры служит поиск последовательности поворотов сторон куба таким образом, чтобы он вернулся в первоначальное состояние, где каждая из граней состоит из квадратов одного цвета.
Доказано, что число всех достижимых различных состояний традиционного 6-цветного кубика Рубика 3×3×3 равно 43 252 003 274 489 856 000, а оптимальная последовательность ходов, необходимых для сборки кубика Рубика из любого состояния не превышает 20. Алгоритм, собирающий кубик Рубика за минимальное число ходов, традиционно называется «алгоритмом Бога», а 20 – числом Бога.
Рассмотрим более простую модель кубика Рубика 2×2×2, в которой используется всего 3 цвета: красный (R), синий (B) и зеленый (G). При этом противоположные грани окрашены в одинаковый цвет. Под ходом будем понимать вращение одной из граней на угол 90º. Поскольку всего 6 граней (передняя (F), левая (L), задняя (B), правая (R), верхняя (U) и нижняя (D)), то всего может быть 12 различных ходов (по часовой и против часовой стрелки для каждой грани). Ходы обозначаются буквами соответствующих граней, если ход происходит против часовой стрелки, то после буквы ставится апостроф (ASCII 39).
По заданной конфигурации трехцветного кубика Рубика 2×2×2 требуется найти оптимальный алгоритм (алгоритм Бога), решающий головоломку.
Входные данные
Входной файл INPUT.TXT содержит две строки, определяющие конфигурацию кубика Рубика. Первая строка содержит информацию о цветах верхнего слоя для каждой грани – пары символов, разделенные пробелом. Вторая строка аналогичным образом описывает нижние слои. Порядок граней (слева направо): передняя, левая, задняя, правая, верхняя, нижняя.
Выходные данные
В выходной файл OUTPUT.TXT выведите оптимальное решение головоломки для заданной конфигурации кубика Рубика. Если решений несколько, выведите любое. Если задана начальная конфигурация (кубик Рубика собран), то следует вывести «Solved».
