Подразделы

Другие разделы

Дата и время

11/12/2024 23:21:57

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЗадачи заочного тура личного первенства 2004

1. Головоломка

Эта головоломка состоит из двух колес. Оба колеса могут вращаться по часовой и против часовой стрелки. Они содержат 21 цветные части, 10 из которых – округленные треугольники и 11 из которых – прямоугольные сепараторы. Рисунок 1 показывает конечное положение каждой части. Заметьте, чтобы выполнить одно вращение вы должны повернуть колесо так, чтобы продвинулся и треугольник и сепаратор.
Рисунок 1. Конечное состояние головоломки
Ваша работа – написать программу, которая читает состояние головоломки и печатает минимальную последовательность перемещений, требуемых, чтобы достигнуть конечного состояния. Мы используем следующие целые значения, чтобы кодировать каждый тип фрагмента:
0 серый сепаратор
1 желтый треугольник
2 желтый сепаратор
3 синий треугольник
4 синий сепаратор
5 фиолетовый треугольник
6 фиолетовый сепаратор
7 зеленый треугольник
8 зеленый сепаратор
9 красный треугольник
10 красный сепаратор
Состояние головоломки может быть описана, используя 24 целых числа, первые 12, чтобы описать левое колесо, и последние 12 – для правого колеса. Первое целое число представляет сепаратор правой нижней части левого колеса, и следующие одиннадцать целых чисел описывают левое колесо по часовой стрелке. Тринадцатое целое число представляет сепаратор левой нижней части правого колеса, и следующие одиннадцать целых чисел описывают правое колесо против часовой стрелки.
Конечное состояние следовательно кодируется так:
0 3 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1
Если, например, мы вращаем левое колесо по часовой стрелке на один шаг из конечного состояние (как показано на рисунке 2), состояние головоломки кодируется так:
2 1 0 3 4 3 0 5 6 5 0 1 0 7 8 7 0 9 10 9 0 5 0 1
Рисунок 2. Состояние головоломки после поворота левого колеса на один шаг из конечного состояния.
Ввод
Ввод для вашей программы состоит из отдельных задач. Первая линия ввода будет содержать целое число n – число задач. Затем следует n строк, каждая содержит 24 целых числа, разделенных пробелом, описывающие начальное состояние головоломки, как объяснено выше.
Вывод
Для каждого состояния ваша программа должна вывести одна строку с только одним числом, представляющим решение. Каждое перемещение кодируется, используя один разряд от 1 до 4 следующим способом:
1 – поворот левого колеса по часовой стрелке
2 – поворот правого колеса по часовой стрелке
3 – поворот левого колеса против часовой стрелки
4 – поворот правого колеса против часовой стрелки
Никаких пробелов не должно быть напечатано между цифрами. Так как несколько решений может быть найдено, вы должны печатать решение, которое кодируется как самый маленькое число. Решение никогда не будет требовать больше чем 16 перемещений.
Если решение за 16 перемещений не найдено, вы должны напечатать "NO SOLUTION WAS FOUND IN 16 STEPS". Если при вводе встретится конечное состояние, вы должны напечатать "PUZZLE ALREADY SOLVED".

Пример ввода

3
0 3 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1
0 3 4 5 0 3 6 5 0 1 2 1 0 7 8 7 0 9 10 9 0 1 2 1
0 9 4 3 0 5 6 5 0 1 2 1 0 7 8 7 0 9 10 3 0 1 2 1

Вывод для примера

PUZZLE ALREADY SOLVED
1434332334332323
NO SOLUTION WAS FOUND IN 16 STEPS

2. Раздел

Маша и Петя владеют коллекцией ракушек. Они хотят разделить коллекцию между собой так, чтобы оба получили равную долю ракушек. Это был бы просто, если все ракушки имели одинаковую ценность, потому что они могли бы разделить коллекцию попалам. Но к сожалению, некоторые из ракушек большие или более красивые, чем другие. Так, Маша и Петя сначала приписали ценность, натуральное число между один и шесть, каждой ракушке. Теперь они хотят разделить ракушки так, чтобы каждый из них получил ракушки на одинаковую суммарную ценность.
К сожалению, не всегда возможно поделить ракушки попалам, даже если суммарная ценность четна. Например, если имеется одна ракушка ценностью 1, одна – ценностью 3 и две – ценностью 4, то они не могут быть разделены на два набора равной ценностью. Вы должны написать программу, которая проверяет, имеется ли честное разбиение коллекции ракушек.
Ввод
Ввод содержит несколько тестовых случаев. Каждая строка ввода описывает одну коллекцию ракушек, которая будет разделена. Строки содержат по шесть неотрицательных целых чисел `n_1,\ …\ ,n_6`, где `n_i` – число ракушек ценностью `i`. Так, пример вверху был бы описан входной строкой "1 0 1 2 0 0". Максимальное общее число ракушек не превышает 20000.
Последняя строка ввода всегда будет "0 0 0 0 0 0"; эта строка не обрабатывается.
Вывод
Для каждой коллекции выведите "Collection #`k`:", где `k` – это номер тестового случая, а затем "Can be divided.", если коллекцию можно разделить, или "Can't be divided.", в противном случае.
Выведите пустую строку после каждого тестового случая.

Пример ввода

1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0

Вывод для примера

Collection #1:
Can't be divided.

Collection #2:
Can be divided.

3. Деление

Напишите программу, которая находит и печатает все пары 5-разрядных чисел, которые используют все цифры от 0 до 9 по одному разу и частное от деления первого числа на второе точно равно целому `N`. То есть,
`"abcde"\ /\ "fghij"\ =\ N`
где разные буквы соответствуют разным цифрам. Первая цифра числа может быть нулем.
Ввод
Каждая строка содержит целое число `N` (`2\ ≤\ N\ ≤\ 79`). Число 0 означает конец ввода.
Вывод
Программа должна выводить пары чисел, в порядке увеличения делимого.
Вывод производится по формату:
xxxxx / xxxxx = `N`
xxxxx / xxxxx = `N`
Если пар чисел, соответствующих условиям нет, вы должны напечатать "There are no solutions for `N`.". Вывод для двух значений `N` нужно разделять пустой строкой.

Пример ввода

61
62
0

Вывод для примера

There are no solutions for 61.

79546 / 01283 = 62
94736 / 01528 = 62
loading