|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||4||3||3||75.000%|
Little Square’s school is organising the annual football match. The two team captains are Little Square and Little Triangle. They will select their teams from the N classes in the school. The team selection works in the following way:
The captains do not care how many students they select overall, and all students are identical when it comes to football skill. They only care about the ”Fo(1)otball” prize. Assuming both have perfect strategy, who wins it ?
Each test file will contain multiple test cases, describing different scenarios. On the first line you will find T, the number of testcases. Their descriptions follow. On the first line of a testcase you will find N and K. On the second line of a testcase you will find N positive integers, which represent the sizes of the classes in Little Square’s school.
Output the answers for the T testcases, each on the same line, not separated by spaces. If Little Square wins the prize in a testcase, output
3 3 1 3 1 1 5 2 2 1 1 1 1 1 2 3
In the first test, there are 5 students in total, and exactly one student must be selected on each turn (as K = 1). Thus, selection will last exactly 5 turns, and the last student will be selected on Little Square’s turn, and Little Square wins.
In the second test, Little Square can first select two students from the first class. Then, after four further turns in which each captain selects one student (since all the classes have only one student at this point), Little Square wins.
In the third test, one winning strategy has Little square first selecting one student.
Contest > infO(1) Cup > infO(1) Cup 2020 3번