1
1. Write a program that accepts two integers n,k and finds bnkc. The algorithm behind your program should run in time polynomial in logn. Math libraries are not allowed.
Input format: The first line of the input consists of a number t ≥ 1 of test cases. Each subsequent line consists of pairs n,k separated by a space. An example is given below.
Sample Input:
3
64 3
15 2
10 5
Sample Output:
4
3
1
Constraints: 1 ≤ n ≤ 1016, 1 ≤ k ≤ n.
2. Given an array A[1,2,...,n] of distinct elements, an inversion is a pair (i,j) of indices such that i < j and A[i] > A[j]. Eg: The sequence 3,8,0,-4,1 has 7 inversions, namely the pairs (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4).
Write a program to count the number of inversions of a given array. The algorithm behind your input should run in O(nlogn) time.
Input format: The first line of the input consists of a single integer: n, the number of elements in the array. The second line of the input consists of the elements of the array, separated by a space.
Sample Input:
5
3 8 0 -4 -1
Sample Output:
7
Constraints: n ≤ 105.
