Задачи олимпиады "Муниципальный этап ВсОШ Красноярского края по информатике, 7-8 классы"
Задача A. Винни-Пух
(Время: 1 сек. Память: 32 Мб Баллы: 100)
Однажды Винни-Пух решил сходить в гости к своему другу Пятачку. Известно, что дом Винни-Пуха находится в точке X, а дом его друга – в точке Y на координатной прямой. За один шаг Пятачок может переместиться на 1, 2, 3, 4 или 5 позиций как влево, так и вправо.
Помогите Винни-Пуху определить: за какое минимальное количество шагов он сможет добраться от своего дома до дома Пятачка?
Входные данные
В первых двух строках входного файла INPUT.TXT записаны два различных целых числа X и Y – координаты домов Винни-Пуха и Пятачка (–109 ≤ X, Y ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – минимальное количество шагов, которые необходимо сделать Винни-Пуху, чтобы оказаться в гостях у Пятачка.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3 8
1
2
7 19
3
Пояснение к примерам
В первом примере Винни-Пух может оказаться в гостях у Пятачка, сделав один шаг вправо на 5 позиций: 3+5 = 8.
Во втором примере существует несколько решений, в каждом из которых Винни-Пух может оказаться у Пятачка, сделав 3 шага вправо. Например, он может сначала пойти на 3 позиции, затем на 4 позиции, а потом – на 5 позиций: 7+3+4+5 = 19.
Задача B. Домашняя работа
(Время: 1 сек. Память: 32 Мб Баллы: 100)
Вася, вернувшись из школы домой, получил от мамы задание сходить на почту за посылкой, а также в магазин за продуктами.
Чтобы зайти из дома на почту и в магазин, Вася может использовать три дороги: от дома до магазина длиной A метров, от дома до почты длиной B метров, от почты до магазина длиной C метров. По этим дорогам Вася может ходить в любом направлении и любое количество раз.
Скорость Васи зависит от груза, который он несёт. Если он идет без груза, то его скорость составляет V0 м/мин (метров в минуту). Если же у него всего один груз (продукты или посылка), то его скорость равна V1 м/мин. Если у него в руках оба груза (продукты и посылка), то его скорость равна V2 м/мин.
При прохождении Васи мимо магазина или почты он может мгновенно покупать продукты или получать почту соответственно, если этого еще не сделал. Проходя мимо дома с грузом, Вася может мгновенно оставлять груз дома.
Определите минимальное время, за которое Вася может принести домой посылку и продукты.
Входные данные
Первая строка входного файла INPUT.TXT содержит шесть целых чисел A, B, C, V0, V1 и V2 – расстояния между объектами и возможные скорости Васи, описанные в условии задачи (1 ≤ A, B, C ≤ 100; 1 ≤ V2 ≤ V1 ≤ V0 ≤ 100).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – минимальное количество минут, которое потребуется Васе, чтобы сходить за посылкой и продуктами и вернуться домой, с точностью, не хуже, чем 10-6.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
1 2 2 10 10 10
0.5
2
4 1 2 5 5 5
1.2
3
2 3 4 7 6 5
1.495238
Задача C. Мирные ладьи
(Время: 1 сек. Память: 32 Мб Баллы: 100)
Ладья — шахматная фигура, которая может двигаться на любое число клеток по горизонтали или по вертикали.
Ладья может бить другую шахматную фигуру, если она находится на той же горизонтали или вертикали. Две шахматные фигуры не могут занимать одну клетку.
Есть шахматная доска размером N×M (N строк и M столбцов). Требуется на данном поле расставить K ладей так, чтобы они не били друг друга.
Входные данные
Первые три строки входного файла INPUT.TXT содержат три целых числа N, M и K – размеры поля и число ладей, соответственно (1 ≤ N, M, K ≤ 100).
Выходные данные
В выходной файл OUTPUT.TXT выведите «Impossible» (без кавычек), если расставить K ладей на поле N×M невозможно.
Если хотя бы одна искомая расстановка существует, выведите в первой строке «Possible» (без кавычек). А затем выведите N строк по M символов в каждой – описание расстановки ладей на поле. В (i+1)-й строке j-м символом выведите «#», если клетка (i, j) содержит ладью, и «.», если соответствующая клетка вашей расстановки пуста. Если подходящих расстановок несколько, выведите любую.
Примеры
№
INPUT.TXT
OUTPUT.TXT
Пояснение
1
1 3 1
Possible .#.
2
2 3 4
Impossible
Невозможно на доске 2х3 разместить 4 ладьи без боя
3
3 5 2
Possible
.....
#....
...#.
Система оценки
Решения, работающие только для N, M ≤ 10, будут оцениваться в 25 баллов.
Задача D. Поездка на автобусе
(Время: 1 сек. Память: 32 Мб Баллы: 100)
Дима собрался в гости к бабушке, которая проживает в том же городе. Чтобы добраться до цели ему предстояло сесть на автобус и проехать N-1 остановку. Город имеет сложный ландшафт и достоверно известно, что все N остановок маршрута Димы находятся на разной целочисленной высоте от 1 до N.
В процессе поездки от одной остановки к другой автобус то поднимался в гору, то спускался с горы. Чтобы поездка не была скучной, Дима решил записывать в блокнот эту информацию, совершая по одной записи между каждой последовательной парой остановок. В итоге получилась N-1 запись в его блокноте.
Позже Диму заинтересовал вопрос: какую высоту может иметь каждая из остановок таким образом, чтобы это не противоречило его записям?
Помогите Диме решить эту задачу!
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N – количество остановок в маршруте (2 ≤ N ≤ 105). Во второй строке содержится последовательность из N-1 символа «<» и «>». Символ «<» на i-й позиции означает, что от i-й до (i+1)-й остановки автобус ехал в гору, в противном случае знак «>» означает, что он ехал с горы.
Выходные данные
В выходной файл OUTPUT.TXT выведите N различных чисел от 1 до N – высоты остановок в маршруте Димы в порядке их посещения автобусом. Если решений несколько, выведите любое. Если Дима ошибся в своих записях и решения не существует, то следует вывести «No solution» (без кавычек).
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
5 <><<
3 5 1 2 4
2
3 ><
2 1 3
3
3 ><
3 1 2
Система оценки
Решения, работающие только для N ≤ 10, будут оцениваться в 25 баллов.
Задача E. Игра в 8
(Время: 2 сек. Память: 64 Мб Баллы: 100)
В квадратной коробке размером 3×3 находятся 8 фишек, на которых написаны цифры от 1 до 8. Таким образом, в коробке есть одна пустая ячейка, в которую за один ход разрешается перемещать соседнюю фишку. В начале игры фишки перемешаны. Задача игрока состоит в том, чтобы, не вынимая фишки из коробки, выстроить фишки в правильном порядке (см. рисунок).
Ваша задача – решить эту задачу за минимальное число ходов.
Входные данные
Входной файл INPUT.TXT содержит три строки, в каждой из которых записаны три цифры от 0 до 8 через пробел. Цифрой «0» обозначается пустая клетка. Гарантируется, что все цифры различны.
Выходные данные
В выходной файл OUTPUT.TXT выведите решение в виде строки из символов «L», «R», «U» и «D» – последовательность команд по перемещению пустого поля в направлениях «влево», «вправо», «вверх» и «вниз» соответственно. Гарантируется, что решение существует. Если существует несколько правильных решений – выведите любое.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
1 2 3 4 5 6 7 0 8
R
2
1 2 3 4 5 6 7 8 0
3
1 2 3 0 6 8 4 7 5
DRRULDR
Пояснение к третьему примеру
Система оценки
Решения, анализирующие не более трёх ходов, будут оцениваться в 10 баллов.
Решения, анализирующие не более шести ходов, будут оцениваться в 20 баллов.
