Постановка задачи

Наконец-то прогресс дошел до семьи Мадока и она решила сыграть со своей младшей сестрой в нашумевшую игру Space Arrays.

Правила игры следующие:

  • Изначально задана последовательность a1,a2,…,aN.
  • Ходы игроков чередуются.
  • В каждый ход текущий игрок должен выбрать индекс i и увеличить ai, т. е. изменить ai на ai+1.
  • После этого, если не существует такой перестановки p1,p2,…,pN целых чисел от 1 до N, что ai≤pi выполняется для каждого действительного i, текущий игрок проигрывает.
  • В противном случае игра продолжается со следующего хода.

Мадока просит вас помочь ей ― сказать ей, выиграет ли в этой игре первый игрок (игрок, который играет в первый ход) или второй игрок, если оба играют оптимально.

Вход

  • Первая строка входных данных содержит единственное целое число T, обозначающее количество тестовых случаев. Ниже приводится описание T тестовых случаев.
  • Первая строка каждого набора входных данных содержит одно целое число N.
  • Во второй строке через пробел записаны N целых чисел a1,a2,…,aN.

Вывод

Для каждого набора входных данных выведите одну строку, содержащую строку "First", если выигрывает первый игрок, или "Second", если выигрывает второй игрок (без кавычек).

Ограничения

  • 1≤T≤2⋅10⁴
  • 1≤N≤2⋅10⁵
  • Сумма N по всем тестам не превосходит 2⋅10⁵
  • 1≤ai≤N для каждого действительного i

Подзадачи

Подзадача 1 (100 баллов): исходные ограничения.

Пример ввода

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

Объяснение

Пример 1:

  • Если первый игрок увеличивает четвертый элемент, получается последовательность (1,2,3,4). Второй игрок проигрывает после увеличения любого из элементов.
  • Если первый игрок увеличивает второй элемент, результирующая последовательность будет (1,3,3,3), и он проигрывает, потому что нет допустимой перестановки. Например, если p=(2,1,4,3), второй элемент aa больше второго элемента p.

Код (решение)

Код был реализован на 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();
Outer:
while(t-- > 0){
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++){
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
int sum =0;
int i=0;
for(i=0;i<n;i++){
if(arr[i] <= i+1){
sum += Math.abs(arr[i]-(i+1));
}
else{
System.out.println("Second");
continue Outer;
}
}
if(sum%2==0)
System.out.println("Second");
else
System.out.println("First");
}
}
}

Надеюсь, вам понравилась статья. Пожалуйста, поставьте 50 аплодисментов этой статье и подписывайтесь на меня, чтобы не пропустить новые блоги, связанные с программированием.

Ссылки

https://www.codechef.com/MARCH21C/problems/SPACEEARR