Sıra yeniləməsi
Sıralama birləşməsi, klassik sıralama alqoritmlərindən biridir. Bu alqoritm, giriş massivini iki hissəyə ayırır, hər bir hissəni rekursiv olaraq sıralayır və sonra iki sıralanmış hissəni birləşdirir.
Bu tapşırıqda, birləşmə sıralama alqoritmi tam ədədlər massivini artan sırada sıralayır. Alqoritmin dəqiq təsviri aşağıdakı psevdokodda verilmiş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 "'
Çox vacib olan 1 -dən n -ə qədər olan ədədlərin permutasiyası sərt disk zədələndiyi üçün itirildi. Xoşbəxtlikdən, ardıcıllıq yuxarıda göstərilən alqoritmlə sıralanmışdı və tək (1) və iki (2) rəqəmlərdən ibarət olan debugging məlumatı başqa bir diskdə yazılmışdı. Giriş ardıcıllığının uzunluğuna n və debugging məlumatına əsasən ilkin tam ədədlər ardıcıllığını bərpa etmək lazımdır.
Giriş verilənləri
Birinci sətir testlərin sayını t ehtiva edir. Hər bir test iki sətirdən ibarətdir. Testin birinci sətiri ilkin ardıcıllığın uzunluğunu n (2 ≤ n ≤ 10000) ehtiva edir. İkinci sətir isə ilkin ardıcıllığın birləşmə sıralama alqoritminin debugging məlumatı olan 1 və 2 simvollarının ardıcıllığını ehtiva edir. Sətirlər "\n" simvolu ilə ayrılır.
Çıxış verilənləri
Bütün ardıcıllığı çıxarmaq əvəzinə, yalnız onun nəzarət cəmini hesablamaq və çap etmək lazımdır, hansı ki, aşağıdakı alqoritmlə hesablanır:
"' function checksum(arr): result = 1 for i=0 to arr.length()-1: result = (31 * result + arr[i]) mod 1000003 return result "'
Nümunələr
Birinci nümunədə n 2-yə bərabərdir, debugging ardıcıllığı 1. İlkin ardıcıllıq 1 2 və ya 2 1 idi. Debugging məlumatı bizə ardıcıllığın birinci ədədinin ikincidən kiçik olduğunu bildirir, buna görə ilkin ardıcıllıq 1 2 olacaq. Onun nəzarət cəmi 994-ə bərabərdir.
İkinci nümunədə n 2-yə bərabərdir, debugging ardıcıllığı 2. Bu dəfə ilkin ardıcıllıq 2 1 olacaq.
Üçüncü nümunədə n 4-ə bərabərdir, debugging ardıcıllığı 12212. İlkin ardıcıllıq 2 4 3 1-ə bərabərdir.