Страница: << 1 2 Отображать по:
#543
Военная сортировка
  
Источники: [ Командные олимпиады, ВКОШП, 2002, Задача H ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Требуется упорядочить числа от 1 до N. Разрешается менять только соседние числа и нельзя переставлять число, которое уже стоит на своем месте.

Фирма Macrohard получила заказ от армии одной страны на реализацию комплекса программного обеспечения для нового суперсекретного радара. Одной из наиболее важных подпрограмм в разрабатываемом комплексе является процедура сортировки.

Однако в отличие от обычной сортировки, эта процедура должна сортировать не произвольный массив чисел, который передается ей на вход, а специальный заранее заданный массив из \(N\) чисел, в котором записана некоторая фиксированная перестановка чисел от 1 до \(N\), и кроме того, ни одно число в нем изначально не находится на своем месте (то есть на позиции с номером i изначально не находится число \(i\)).

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

Например, если массив из 6 элементов в некоторый момент имеет вид <2, 1, 3, 6, 4, 5>, то можно поменять местами 1 и 2, 6 и 4 или 4 и 5, а менять местами 1 и 3 или 3 и 6 нельзя, поскольку число 3 находится на своем месте (на позиции с номером 3).

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

Подсказка

Найти такую последовательность обменов всегда возможно.

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

В первой строке вводится целое число \(N\) - размер входного массива (1 <= \(N\) <= 100). Вторая строка содержит \(N\) целых чисел - исходную перестановку чисел от 1 до \(N\) в массиве. Изначально ни одно число не стоит на своем месте.

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

Выведите \(K\) строк, где \(K\) - количество обменов в Вашей сортировке. На каждой строке выведите по два числа \(x_i\) и \(y_i\), разделенных пробелом - позиции в массиве, числа на которых следует поменять местами на i-ом обмене. Помните, что должно выполняться условие |\(x_i\) - \(y_i\)| = 1 и что нельзя перемещать число, которое уже стоит на своем месте.

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

В приведенном примере массив последовательно имеет следующий вид:
исходный вид массива
2 3 1 6 4 5
поменяли местами числа на 2 и 3 позициях
2 1 3 6 4 5
поменяли местами числа на 1 и 2 позициях
1 2 3 6 4 5
поменяли местами числа на 4 и 5 позициях
1 2 3 4 6 5
поменяли местами числа на 5 и 6 позициях
1 2 3 4 5 6

Примеры
Входные данные
6
2 3 1 6 4 5
Выходные данные
2 3
1 2
4 5
5 6
#544
Космический мусорщик
  
Источники: [ Командные олимпиады, ВКОШП, 2002, Задача I ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Вызов функции осуществляется с одним числовым параметром. Функция прибавляет один к счетчику и вызывает заданный набор функций с параметром, на 1 меньшим. При параметре 0 функция прекращает работу. Требуется вывести значение счетчика.

В околоземном космическом пространстве накопилось много мусора, поэтому ученые сконструировали специальный аппарат - ловушку для космического мусора. Для того, чтобы хорошо собирать мусор, этот аппарат должен двигаться по достаточно сложной траектории, сжигая собранный по пути мусор. Ловушка может передвигаться в пространстве по 6 направлениям: на север (\(N\)), на юг (\(S\)), на запад (\(W\)), на восток (\(E\)), вверх (\(U\)) и вниз (\(D\)). Движением ловушки управляет процессор. Программа движения задается шестью правилами движения, которые соответствуют каждому из указанных направлений. Каждое такое правило представляет собой строку символов из множества {\(N\), \(S\), \(W\), \(E\), \(U\), \(D\)}.

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

Пусть, например, заданы следующие правила:


Тогда при выполнении команды \(S\)(3) мусорщик выполнит следующие действия:

1) переместится на 1 метр в направлении \(S\)
2) выполнит последовательно команды \(N\)(2), \(U\)(2), \(S\)(2), \(D\)(2), \(D\)(2), \(U\)(2), \(S\)(2), \(E\)(2).
Если далее проанализировать действия мусорщика при выполнении команд из пункта 2, получим, что в целом он совершит следующие перемещения:

SNNUUSNUSDDUSEDWEDDWEDUUSNUSDDUSEEПо заданной команде определите, какое общее количество перемещений на один метр совершит ловушка при выполнении заданной команды. В приведенном примере это количество равно 34.

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

Первые шесть строк входных данных задают правила для команд с направлением \(N\), \(S\), \(W\), \(E\), \(U\) и \(D\) соответственно. Каждая строка содержит не более 100 символов (и может быть пустой). Следующая строка содержит команду ловушки: сначала символ из множества {\(N\), \(S\), \(W\), \(E\), \(U\), \(D\)}, затем пробел и параметр команды - целое положительное число, не превышающее 100.

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

Выведите единственное число - количество перемещений, которое совершит ловушка. Гарантируется, что ответ не превышает \(10^9\).

Примеры
Входные данные
N
NUSDDUSE
UEWWD

U
WED
S 3
Выходные данные
34
Страница: << 1 2 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест