Поновлення послідовності
Сортування злиттям є одним з класичних алгоритмів сортування. Він ділить вхідний масив на дві частини, рекурсивно сортує кожну з них окремо та потім зливає дві відсортовані частини разом.
У цьому завданні алгоритм сортування злиттям сортує масив цілих чисел у зростаючому порядку. Точний опис алгоритму наведемо на псевдокоді:
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.