Это простая версия задачи. Единственное различие между двумя версиями задачи — количество операций, которые вы можете сделать. Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Вам дан массив \(a\) длины \(n\).
Крутая прогулка с обменом — это следующий процесс:
- В сетке \(n \times n\) обозначим ячейку в строке \(i\) и столбце \(j\) как \((i, j)\). Вам нужно пройти от \((1,1)\) до \((n,n)\), делая только шаги вправо или вниз.
- Формально, если вы находитесь в \((x,y)\) в данный момент, вы можете сделать шаг в \((x+1,y)\) или \((x,y+1)\), но вы не можете выйти за границы сетки.
- Когда вы делаете шаг в \((i,j)\), вы должны поменять местами \(a_i\) и \(a_j\), если \(i \neq j\).
Вы можете выполнить не более \(2n+4\) крутых прогулок с обменом. Отсортируйте массив \(a_1, a_2, \ldots, a_n\) в неубывающем порядке. Можно показать, что это всегда можно сделать.
Выходные данные
Для каждого набора входных данных вывод должен состоять из нескольких строк:
- Первая строка содержит целое число \(k\) (\(0 \leq k \leq 2n+4\)), представляющее количество крутых прогулок с обменом, которое вы выполняете.
- Каждая из следующих \(k\) строк содержит строку \(s\) длины \(2n-2\), состоящую только из R и D, представляющую путь (буквы чувствительны к регистру). Для всех \(1 \le i \le 2n-2\), если \(s_i=\) R, то на \(i\)-м шаге вы идёте направо, иначе на \(i\)-м шаге вы идёте вниз.
Примечание
В первом наборе входных данных массив \(a\) уже является неубывающим, поэтому вам не нужно выполнять никаких прогулок.
Во втором наборе входных данных изначально \(a=[2,1,3]\).
На первой прогулке:
- На \(1\)-м шаге вы делаете шаг вправо в клетку \((1,2)\). Затем, \(a=[1,2,3]\). Обратите внимание, что хотя массив \(a\) уже является неубывающим, вы не можете остановиться, пока не достигнете \((n,n)\).
- На \(2\)-м шаге вы делаете шаг вправо в \((1,3)\). Тогда \(a=[3,2,1]\).
- На \(3\)-м шаге вы делаете шаг вниз в \((2,3)\). Тогда, \(a=[3,1,2]\).
- На \(4\)-м шаге вы спускаетесь в \((3,3)\). Тогда, \(a=[3,1,2]\).
На второй прогулке:
- На \(1\)-м шаге вы опускаетесь в \((2,1)\). Тогда \(a=[1,3,2]\).
- На \(2\)-м шаге вы делаете шаг вправо в \((2,2)\). Тогда, \(a=[1,3,2]\).
- На \(3\)-м шаге вы делаете шаг вниз в \((3,2)\). Тогда, \(a=[1,2,3]\).
- На \(4\)-м шаге вы опускаетесь в \((3,3)\). Тогда, \(a=[1,2,3]\).
После двух крутых прогулок с обменом, описанных выше, мы получаем \(a=[1,2,3]\), что является неубывающим массивом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
1 2
3
2 1 3
4
3 2 3 4
|
0
2
RRDD
DRDR
3
RRDRDD
DRDDRR
DDRRRD
|