Страница: 1 2 >> Отображать по:
#1039
Магия Копперфильда
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Дана прямоугольная таблица. Фишка в таблице может перемещаться в любое место на K ходов. Требуется последовательно убрать все ячейки таблицы, кроме одной, задавая количество ходов, на которые должна сходить фишка, и координаты удаляемых клеток. Фишка должна оказаться в единственной оставшейся клетке.

Всемирно известный маг Дэвид Копперфильд любит показывать следующий трюк. Квадрат из N столбцов и N строк, в каждой клетке которого находится какая-нибудь картинка, появляется на экране телевизора. Пусть все картинки пронумерованы следующим образом:

1

2

…

N

N+1

N+2

…

2*N

:

:

…

:

N*(N–1)+1

N*(N–1)+2

…

N*N

Дэвид просит каждого зрителя поставить палец на левую верхнюю картинку (то есть в клетку номер 1), и Магия начинается: маг просит зрителей сдвинуть свой палец K1 раз в произвольном направлении (сдвигать палец разрешается только на соседнюю картинку по горизонтали или по вертикали, оставлять палец на месте запрещено, при этом если, допустим, Дэвид попросил сдвинуть палец 3 раза, то можно, например, сдвинуть палец на одну клетку вправо, затем — на одну клетку вниз, затем — на одну вверх). Затем со словами "Ваш палец не здесь" Дэвид убирает некоторые картинки, и — что удивительно, пальцы телезрителей действительно не указывают на те картинки, которые убирает Дэвид. Затем он просит сделать K2 ходов, и так далее (если Дэвид уже убрал какую-то картинку, то ходить через эту клетку нельзя). В конце, Дэвид убирает все картинки, кроме одной, и, улыбаясь, говорит: "Вы здесь" (аплодисменты).

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

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

Во входном файле записано одно число N — размер квадрата (2N100).

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

В выходной файл ваша программа должна печатать следующие строки чисел:

K1 X1,1 X1,2 … X1,m1

K2 X2,1 X2,2 … X2,m2

…

Ke Xe,1 Xe,2 … Xe,me

где Ki — это число ходов, которые должны сделать телезрители, а Xi,1 … Xi,mi — номера картинок, которые Дэвид должен убрать с экрана после этого. При этом все Ki должны удовлетворять условию 2NKi10000 и все Ki должны быть различны. Каждая картинка (кроме той, которая останется) должна убираться ровно один раз. После каждой просьбы зрителей сделать Ki ходов, Дэвид должен убирать хотя бы одну картинку. Каждое Ki должно печататься в начале новой строки. Ситуаций, когда телезритель остался на клетке, у которой нет соседних, а его просят куда-нибудь ходить, возникать не должно.

Примеры
Входные данные
3
Выходные данные
7 1 3 7 9
9 2 4 6 8
#1107
Лягушачьи игры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Имя входного файла: frogs.in
Имя выходного файла: frogs.out

В тридесятом царстве в новогодние праздники все лягушки собираются на самом большом болоте, чтобы поиграть в замечательную игру. Всего в этом царстве живет N зеленых лягушек и M коричневых. Для игры они выбирают на болоте N + M + 1 кочку, на первые N кочек слева садятся зеленые лягушки, а на последние M — коричневые (т. е. между ними находится одна кочка, на которой никто не сидит). Зеленые лягушки садятся лицом к коричневым лягушкам, а коричневые — к зеленым. Кочки настолько маленькие, что развернуться на них, не свалившись в болото, совершенно не возможно. Поэтому лягушки могут двигаться только вперед и не могут разворачиваться.

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

Чтобы праздник удался, зеленые лягушки должны оказаться на последних кочках, а коричневые — на первых. Порядок, в котором лягушки окажутся на кочках, не важен. Так как на праздник каждый раз приходит разное количество лягушек, то им каждый год приходится придумывать очередность прыжков. Напишите программу, которая поможет лягушкам составить план прыжков.

Поиграть в эту игру для случая N=M=3 можно по ссылке:

http://olympiads.ru/zaoch/2007/problems/frogs.swf

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

Во входном файле записаны два числа N и M (1≤N≤1000, 1≤M≤1000) – количество зеленых и коричневых лягушек соответственно.

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

Выведите последовательность прыжков лягушек для достижения поставленной цели. Каждый прыжок можно задать одним числом — номером прыгающей лягушки (поскольку свободная кочка всегда ровно одна). Пронумеруем всех лягушек в соответствии с их начальным положением. Зеленые лягушки будут пронумерованы числами от 1 до N, а коричневые — с N+1 до N+M в порядке слева направо.

В первую строку выходного файла выведите число K — количество прыжков. K не должно превышать 107. Далее выведите K чисел — номера лягушек.

Если же достичь требуемой рассадки лягушек нельзя, выведите одно число –1.

Примеры
Входные данные
2 1
Выходные данные
5
2 3 2 1 3
#112032
Перемешивание
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Каждое утро капитан Ъ проводит занятия по строевой подготовке в возглавляемой им роте солдат. Всего в роте N солдат, каждый из которых носит форму определенного цвета. Различных цветов формы не более 26, так что для удобства солдаты обозначают цвета строчными латинскими буквами. Таким образом, каждому из \(N\) солдат соответствует буква от 'a' до 'z' — цвет его формы.

За многие месяцы службы солдаты выяснили, что капитан пребывает в наилучшем расположении духа в том случае, когда цвета формы солдат в шеренге образуют определенную последовательность. Недолго думая, они выписали соответствующую строку \(S\) из \(N\) букв на асфальте и договорились, что отныне каждый должен при построении вставать именно на ту букву, которая соответствует цвету его формы.

Но к 23 февраля солдаты решили удивить капитана и поменяться местами так, чтобы \(каждый\) солдат встал не на ту букву, которая соответствует цвету его формы. Так, солдат с цветом формы 'q' может встать на любую букву, кроме буквы 'q', иначе удивление капитана будет недостаточным.

Помогите солдатам организовать праздничное построение: по данной строке \(S\), обозначающей старую последовательность цветов, выведите строку \(T\), являющуюся перестановкой символов строки \(S\) и обозначающую новую последовательность цветов. i-й символ строки T должен отличаться от i-го символа строки \(S\).

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

В первой строке входного файла содержится единственное целое число \(N\) — количество солдат в роте \((1 \le N \le 100 000)\). Во второй строке содержится строка S, состоящая из \(N\) строчных латинских букв.

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

Единственная строка выходного файла должна содержать искомую строку \(T\), если задумка солдат осуществима, и «Impossible» в противном случае. Если верных ответов несколько, выведите любой из них.

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

Тесты к этой задаче состоят из четырех групп. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.

0. Тесты 1—2. Тесты из условия, оцениваются в ноль баллов.

1. Тесты 3—21. В тестах этой группы \(N \le 9\). Эта группа оценивается в 30 баллов.

2. Тесты 22—36. В тестах этой группы \(N \le 200\), а строка не может содержать никаких букв, кроме 'a', 'b' и 'c'. Эта группа оценивается в 30 баллов независимо от первой.

3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.

Примеры
Входные данные
9
olimpiada
Выходные данные
iapdialom
Входные данные
7
baaaaaa
Выходные данные
Impossible
#112831
Строки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Даны три строки, состоящие из строчных латинских букв. С этими строками можно производить следующие операции: либо заменить один символ строки на два таких же символа (например, заменить символ «a» на «aa»), либо, наоборот, заменить два подряд идущих одинаковых символа на один такой же символ.

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

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

Программа получает на вход три строки, состоящие из строчных букв латинского алфавита. Длина каждой строки не превышает 100 символов.

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

Если при помощи указанных операций возможно сделать все три строки равными, выведите такую строку S , что суммарное число операций, необходимых для преобразования всех трёх данных строк к строке S , будет минимальным. Если этого сделать нельзя, программа должна вывести одно слово IMPOSSIBLE (заглавными буквами).

Примечание

Решение, которое выводит правильный ответ только на тестах из условия и тех тестах, на которых ответом является слово IMPOSSIBLE, будет оцениваться в 0 баллов.

Примеры
Входные данные
aaaza
aazzaa
azzza
Выходные данные
aazza
Входные данные
xy
xxyy
yx
Выходные данные
IMPOSSIBLE
#113100
Три сына
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Во владениях короля Флатландии находится прямая дорога длиной \(n\) километров, по одну сторону от которой расположен огромный лесной массив. Король Флатландии проникся идеями защиты природы и решил превратить свой лесной массив в заповедник. Но сыновья стали сопротивляться: ведь им хотелось получить эти земли в наследство.

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

  • каждый участок должен иметь форму квадрата, длина стороны которого выражается целым положительным числом. Одна из сторон каждого квадрата должна лежать на дороге. Пусть участки имеют размеры \(a \times a, b \times b\) и \(c \times c\);
  • стороны квадратов должны полностью покрывать дорогу: величина a + b + c должна быть равна \(n\);
  • участок младшего сына должен быть строго меньше участка среднего сына, а участок среднего сына должен, в свою очередь, быть строго меньше участка старшего сына, то есть должно выполняться неравенство \(a < b < c\);
  • суммарная площадь участков \(a^2 + b^2+ c^2\) должна быть минимальна.
Требуется написать программу, которая по заданной длине дороги определяет размеры участков, которые следует выделить сыновьям короля.

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

Входной файл содержит одно целое число \(n\) (\(6 \le n \le 10^9\) ).

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

Выходной файл должен содержать три целых положительных числа, разделенных пробелами: \(a\), \(b\) и \(c\) – длины сторон участков, которые следует выделить младшему, среднему и старшему сыну, соответственно. Если оптимальных решений несколько, разрешается вывести любое.

Пояснение к примеру

Описание подзадач и системы оценивания

В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Подзадача 1 (25 баллов)

\(n \le 50\)

Подзадача 2 (25 баллов)

\(n \le 2000\)

Подзадача 3 (25 баллов)

\(n \le 40000\)

Подзадача 4 (25 баллов)

\(n \le 10^9\)

Примеры
Входные данные
6
Выходные данные
1 2 3
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест