Header Ads Widget

Space Arrays | codechef solution

Rajnish Tripathi 07:30

 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

  • 1≤�≤2⋅104
  • 1≤�≤2⋅105
  • The sum of � over all test cases doesn't exceed 2⋅105
  • 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:-





Tags:

Post a Comment

0 Comments