Merge sort is one of the classic sorting algorithms. It divides the input array into two halves, recursively sorts each half, then merges the two sorted halves.
In this problem merge sort is used to sort an array of integers in ascending order. The exact behavior is given by the following pseudo-code:
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
A very important permutation of the integers 1 through N was lost to a hard drive failure. Luckily, that sequence had been sorted by the above algorithm and the debug sequence of 1s and 2s was recorded on a different disk. You will be given the length N of the original sequence, and the debug sequence. Recover the original sequence of integers.
The first line of the input file contains an integer T. This is followed by T test cases, each of which has two lines. The first line of each test case contains the length of the original sequence, N. The second line contains a string of 1s and 2s, the debug sequence produced by merge sort while sorting the original sequence. Lines are separated using Unix-style ("\n") line endings.
To avoid having to upload the entire original sequence, output an integer checksum of the original sequence, calculated by the following algorithm:
function checksum(arr):
result = 1
for i=0 to arr.length()-1:
result = (31 * result + arr[i]) mod 1000003
return result
5 ≤ T ≤ 20
2 ≤ N ≤ 10000
In the first example, N is 2 and the debug sequence is 1. The original sequence was 1 2 or 2 1. The debug sequence tells us that the first number was smaller than the second so we know the sequence was 1 2. The checksum is 994.
In the second example, N is 2 and the debug sequence is 2. This time the original sequence is 2 1.
In the third example, N is 4 and the debug sequence is 12212. The original sequence is 2 4 3 1.
5
2
1
2
2
4
12212
5
1122211
10
121221212111122121212
Case #1: 994
Case #2: 1024
Case #3: 987041
Case #4: 570316
Case #5: 940812
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
public class Checkpoint {
public static void main(String[] args) throws IOException {
BufferedReader leer= new BufferedReader(new InputStreamReader(System.in));
int T= Integer.parseInt(leer.readLine());
int r[]=coefBin(4500);
for (int i = 1; i <= T; i++) {
int n= Integer.parseInt(leer.readLine());
int t=Integer.MAX_VALUE;
for (int j = 1; j*j <= n; j++) {
if(n%j==0){
int a=r[j]==Integer.MAX_VALUE/3?j:r[j];
int b=r[n/j]==Integer.MAX_VALUE/3?n/j:r[n/j];
t=Math.min(a+b,t);
}
}
System.out.println("Case #"+i+": "+t);
}
}
public static int[] coefBin(int N){
int c[][]= new int[N][N];
int r[]= new int[10000001];
Arrays.fill(r, Integer.MAX_VALUE/3);
r[0]=0;
r[1]=1;
for (int i = 0; i < N; i++)
c[i][0] = c[i][i]=1;
for (int i = 1; i < N; i++){
if(c[i-1][1]==0 && i>1)
break;
for (int j = 1; j < i; j++){
if(c[i-1][j-1]+c[i-1][j]<=10000000){
c[i][j]=c[i-1][j-1]+c[i-1][j];
r[c[i][j]]=Math.min(r[c[i][j]], i);
}
else{
c[i][j]=Integer.MAX_VALUE/3;
}
}
}
return r;
}
}