Header Ads Widget

Space Arrays | codechef solution

 Finally, progress reached the Madoka family and she decided to play with her little sister in the sensational game Space Arrays.

The rules of the game are as follows:

  • Initially, a sequence 1,2,, is given.
  • The players alternate turns.
  • In each turn, the current player must choose an index  and increment , i.e. change  to +1.
  • Afterwards, if there is no permutation 1,2,, of the integers 1 through  such that  holds for each valid , the current player loses.
  • Otherwise, the game continues with the next turn.

Madoka is asking you to help her ― tell her if the first player (the player that plays in the first turn) or second player wins this game if both play optimally.

Input

  • The first line of the input contains a single integer  denoting the number of test cases. The description of  test cases follows.
  • The first line of each test case contains a single integer .
  • The second line contains  space-separated integers 1,2,,.

Output

For each test case, print a single line containing the string "First" if the first player wins or "Second" if the second player wins (without quotes).

Constraints

  • 12104
  • 12105
  • The sum of  over all test cases doesn't exceed 2105
  • 1 for each valid 

Subtasks

Subtask #1 (100 points): Original constraints

Sample 1:

Input
Output
4
4
1 2 3 3
4
1 1 3 3
5
1 2 2 1 5
3
2 2 3
First
Second
Second
Second

Explanation:

Example case 1:

  • If the first player increases the fourth element, the resulting sequence is (1,2,3,4). The second player loses after increasing any of the elements.
  • If the first player increases the second element, the resulting sequence is (1,3,3,3), and he loses because there is no valid permutation. For example if =(2,1,4,3), the second element of  is greater than the second element of .

Code(C++):-
#include <iostream>
#include<algorithm>
using namespace std;

int main() {
    // your code goes here
    int t;
    cin>>t;
    for (int j=0; j<t; j++){
     int n;
     cin>>n;
     int arr[n];
     long long count=0;
     for (int i=0; i<n; i++){
     cin>>arr[i];
     }
     int flag=0;
     std::sort(arr,arr+n);
     for (int i=0; i<n; i++){
     if (arr[i]<i+1){
     count += i+1-arr[i];
     }
     if (arr[i]>i+1){
     flag=-1;
     break;
     }
     }
     if (flag==0){
     if (count%2==1){
     cout<<"First"<<endl;
     }
     else{
     cout<<"Second"<<endl;
     }
     }
     else{
     cout<<"Second"<<endl;
     }
    }
    return 0;
}


Code(JAVA):-
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
  public static void main (String[] args) throws java.lang.Exception
  {
    // your code goes here
    Scanner sc=new Scanner(System.in);
    int t=sc.nextInt();
    while(t-->0){
     int n=sc.nextInt();
     int a[]=new int[n];
     for(int i=0;i<n;i++)
     a[i]=sc.nextInt();
     Arrays.sort(a);
     int sum=0;
     boolean is=true;
     for(int i=0;i<n;i++){
     if(a[i]<=(i+1)){
     sum=sum+i+1-a[i];
     }
     else{
     is=false;
     break;
     }
     }
     if(!is)
     System.out.println("Second");
     else{
     if(sum%2==0)
     System.out.println("Second");
     else
     System.out.println("First");
     }
    }
  }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-