Sıra yeniləməsi#2822
Birləşmə çeşidləməsi (merge sort) klassik çeşidləmə alqoritmlərindən biridir. O, daxil olan massivı iki hissəyə bölür, hər hissəni rekursiv olaraq çeşidləyir və sonra iki çeşidlənmiş hissəni birləşdirir.
Bu məsələdə merge sort alqoritmi tam ədədlərdən ibarət massivı artan sıra ilə çeşidləyir. Ətraflı iş prinsipi aşağıdakı psevdokodda təsvir edilmişdir:
"' 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 "'
Sərt diskin sıradan çıxması nəticəsində 1-dən n-ə qədər olan ədədlərin çox vacib bir permutasiyası itdi. Xoşbəxtlikdən, bu ardıcıllıq yuxarıdakı alqoritmlə çeşidlənmişdi və ancaq tək və ikilərdən (1 və 2) ibarət olan debug məlumatı digər diskdə saxlanılmışdı. Verilmiş ardıcıllığın uzunluğu n və debug məlumatına əsaslanaraq ilkin ədəd ardıcıllığını bərpa etməyiniz tələb olunur.
Birinci sətirdə testlərin sayı t verilir. Hər test iki sətirdən ibarətdir. Hər testin birinci sətrində ilkin ardıcıllığın uzunluğu — n (2 ≤ n ≤ 10000) verilir. İkinci sətirdə isə massiv üçün merge sort alqoritminin yaratdığı debug ardıcıllığı — yalnız 1 və 2-lərdən ibarət sətir yazılır. Sətirlər "\n" simvolu ilə ayrılır.
Bütün ardıcıllığı çap etmək əvəzinə, yalnız aşağıdakı alqoritmə əsasən hesablanan çek-samini (checksum) çap etməlisiniz:
"' function checksum(arr): result = 1 for i = 0 to arr.length() - 1: result = (31 * result + arr[i]) mod 1000003 return result "'
Nümunə
Birinci nümunədə n = 2, debug ardıcıllığı isə 1-dir. İlkin ardıcıllıq 1 2 və ya 2 1 ola bilərdi. Debug ardıcıllığı bizə ilk ədədin ikincidən kiçik olduğunu deyir, ona görə də ardıcıllıq 1 2-dir. Onun çek-samı 994-dür.
İkinci nümunədə n = 2, debug ardıcıllığı isə 2-dir. Bu dəfə ilkin ardıcıllıq 2 1-dir.
Üçüncü nümunədə n = 4, debug ardıcıllığı isə 12212-dir. İlkin ardıcıllıq 2 4 3 1-dir.
Nümunə 1