Восстановление последовательности
Сортировка слиянием является одним из классических алгоритмов сортировки. Он делит входной массив на две части, рекурсивно сортирует каждую из них отдельно и затем сливает две отсотированные части вместе.
В этой задаче алгоритм сортировки слиянием сортирует массив целых чисел в возрастающем порядке. Точное описание алгоритма приведем на псевдокоде:
function merge_sort(arr): n = arr.length() if n <= 1: return arr // arr is indexed 0 through n-1, inclusive mid = floor(n/2) first_half = merge_sort(arr[0..mid-1]) second_half = merge_sort(arr[mid..n-1]) return merge(first_half, second_half) function merge(arr1, arr2): result = [] while arr1.length() > 0 and arr2.length() > 0: if arr1[0] < arr2[0]: print '1' // for debugging result.append(arr1[0]) arr1.remove_first() else: print '2' // for debugging result.append(arr2[0]) arr2.remove_first() result.append(arr1) result.append(arr2) return result
Очень важная перестановка чисел от 1 до n была утеряна из-за порчи жесткого диска. К счастью, последовательность сортировалась выше приведенным алгоритмом и отладочная информация из единиц (1) и двоек (2) была записана на другой диск. По длине входной последовательности n и отладочной информации следует восстановить исходную последовательность целых чисел.
Входные данные
Первая строка содержит количество тестов t. Каждый тест состоит из двух строк. Первая строка теста содержит длину исходной последовательности n (2 ≤ n ≤ 10000). Вторая строка содержит последовательность символов 1 и 2 - отладочную информацию программы сортировки слияниям исходной последовательности. Строки разделяются символом "\n".
Выходные данные
Чтобы не выводить всю последовательность, следует вычислить и напечатать только ее контрольную сумму, которая вычисляется по следующему алгоритму:
function checksum(arr): result = 1 for i=0 to arr.length()-1: result = (31 * result + arr[i]) mod 1000003 return result
Примеры
В первом примере n равно 2, отладочная последовательность 1. Исходной была последовательность 1 2 или 2 1. Отладочная информация сообщает нам, что первое число последовательности было меньше второго, поэтому исходной последовательностью будет 1 2. Ее контрольная сумма равна 994.
Во втором примере n равно 2, отладочная последовательность 2. На этот раз исходной будет последовательность 2 1.
В третьем примере n равно 4, отладочная последовательность 12212. Исходная последовательность равна 2 4 3 1.