Постановка задачи
Наконец-то прогресс дошел до семьи Мадока и она решила сыграть со своей младшей сестрой в нашумевшую игру 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