Issue # 26: IT training - current issues and challenges from leading companies

Questions

A thief has just found a pair of ancient treasure caves. One of the caves is filled with unbelievable treasure and the other has a fire breathing monster that will eat anyone who opens that cave.

One cave has a black door decorated with diamonds and the other cave has a brown door decorated with sapphires.

Each of the doors has an engraved description on top. The descriptions say:



Black Door: Monster is here.

Brown Door: Only One Door speaks the truth.



Which door should the thief open?

Alok has three daughters. His friend Shyam wants to know the ages of his daughters. Alok gives him first hint.

1. The product of their ages is 72. Shyam says this is not enough information Alok gives him a second hint.
2. The sum of their ages is equal to my house number. Shyam goes out and look at the house number and says “I still do not have enough information to determine the ages”. Alok admits that Shyam can not guess and gives him the third hint
3. The oldest of the girls likes strawberry ice-cream. Shyam is able to guess after the third hint.

Can you guess what are the ages of three daughters?

Tasks

Since very long time Tom and Jerry have been fighting with each other for a piece of Cheese. So finally you came to rescue and decided that the result of the fight will be decided by a mathematical game, in which you will write a number N (1 <= N <= 10^6)



. Tom and Jerry will play the game alternatively and each of them would subtract a number n [n < N]



such that N % n = 0



.

The game is repeated turn by turn until the one, who now cannot make a further move looses the game.

The game begins with Tom playing first move. It is well understood that both of them will make moves in optimal way. You are to determine who wins the game.



Input: the first line of each test case consists of N the number.

Output: print 1 if Tom wins and print 0 if Jerry wins in a separate line.



Constraints:

1 <= N <= 10^6







Sample:

Input: 2 / Output: 1

Input: 4 / Output: 1

There is one meeting room in a firm. There are N meetings in the form of (S[i], F[i])



where S [i] is start time of meeting i and F [i] is finish time of meeting i.

What is the maximum number of meetings that can be accommodated in the meeting room?



Input:

The first line of input consists number of the test cases. The description of T test cases is as follows:

The first line consists of the size of the array, second line has the array containing the starting time of all the meetings each separated by a space, ie, S [i]. And the third line has the array containing the finishing time of all the meetings each separated by a space, ie, F [i].

Output:

In each separate line print the order in which the meetings take place separated by a space.



Constraints:

1 ≤ T ≤ 70

1 ≤ N ≤ 100

1 ≤ S[ i ], F[ i ] ≤ 100000







Example:

Input:

2

6

1 3 0 5 8 5

2 4 6 7 9 9

8

75250 50074 43659 8931 11273 27545 50879 77924

112960 114515 81825 93424 54316 35533 73383 160252





Output:

1 2 4 5

6 7 1

Given an array of positive integers. The task is to find inversion count of array.

Inversion Count: For an array, inversion count indicates how far (or close) the array is from being sorted. If array is sorted in reverse order that inversion count is the maximum.

Formally, two elements a [i] and a [j] form an inversion if a[i] > a[j]



and i < j



.



Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N, the size of array. The second line of each test case contains N elements.

Output: Print the inversion count of array.



Constraints:

1 ≤ T ≤ 100

1 ≤ N ≤ 107

1 ≤ C ≤ 1018







Example:

Input:

1

5

2 4 1 3 5





Output:

3

The answers

 using System; public class TomJerry { static public void Main () { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.printIn((n - 1) % 2); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 #include <bits/stdc++.h> using namespace std; struct Activity { int start, finish, index; }; bool activityCompare(Activity s1, Activity s2) { return s1.finish < s2.finish; } int main() { int t, n, i, j; cin >> t; while (t--) { cin >> n; Activity arr[n]; for (i = 0; i < n; i++) { cin >> arr[i].start; arr[i].index = i; } for (i = 0; i < n; i++) cin >> arr[i].finish; sort(arr, arr + n, activityCompare); i = 0; cout << arr[i].index + 1 << " "; for (int j = 1; j < n; j++) { if (arr[j].start >= arr[i].finish) { cout << arr[j].index + 1 << " "; i = j; } } cout << endl; } return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 #include<iostream> using namespace std; int merge(int* arr, int* LArr, int* RArr, int m, int n) { int i = 0, j = 0, k = 0; int count = 0; while (i < m && j < n) { if (LArr[i] <= RArr[j]) arr[k++] = LArr[i++]; else { arr[k++] = RArr[j++]; count = count + m - i; } } while (i < m) arr[k++] = LArr[i++]; while (j < n) arr[k++] = RArr[j++]; return count; } int mergeSort(int* arr, int start, int end) { if (start > end) return 0; if (start == end) return 0; if (start == end - 1) { if (arr[start] <= arr[end]) return 0; else swap(arr[start], arr[end]); return 1; } int mid = (start + end) / 2; int* LArr = new int[mid + 1]; int* RArr = new int[end - mid]; int i; for (i = start; i <= mid; i++) LArr[i] = arr[i]; for (i = mid + 1; i <= end; i++) RArr[i - (mid + 1)] = arr[i]; int count = 0; count += mergeSort(LArr, 0, mid); count += mergeSort(RArr, 0, end - mid - 1); count += merge(arr, LArr, RArr, mid + 1, end - mid); delete[] LArr; delete[] RArr; return count; } int main() { int t, n,*arr; cin >> t; while (t--) { cin >> n; arr = new int[n]; for (int i = 0; i < n; i++) cin >> arr[i]; cout << mergeSort(arr, 0, n - 1) << endl; } }