Fişierul intrare/ieşire:	football2.in, football2.out	Sursă	Info(1)cup 2020
Autor	Tamio-Vesa Nakajima	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	1 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Football2

Şcoala lui Pătraţel organizează meciul anual de fotbal. Cei doi capitani sunt Pătrăţel şi Triunghiuleţ. Ei îşi vor selecta echipele din cele N clase ale şcolii. Selecţia echipelor funcţionează în felul următor:

• Pătrăţel şi Triunghiuleţ aleg membrii alternativ, în ture. Pătrăţel începe.
• Într-o tură, pot fi aleşi doar elevi dintr-o singură clasă.
• Într-o tură, vor fi selectaţi cel puţin unul şi cel mult K elevi.
• Într-o tură, se vor selecta cel mult la fel de mulţi elevi ca în tura precedentă.
• Căpitanul care selectează ultimul (sau ultimii) elevi primeşte premiul "Fo(1)tbal".

Căpitanilor nu le pasă câţi elevi selectează, şi toţi elevii sunt identici când vine vorba de fotbal. Le pasă doar de premiul "Fo(1)tbal". Presupunând că amândoi au o strategie perfectă, cine câstigă premiul?

Date de intrare

Fişierul de intrare football2.in va conţine mai multe teste, ce descriu scenarii diferite.
Pe prima linie a unui fişier veţi găsi T, numărul de teste. Apoi urmează descrierile testelor.
Pe prima linie a unui test veţi găsi N şi K.
Pe a doua linie a unui test veţi găsi N numere întregi pozitive, ce reprezintă mărimile claselor din şcoala lui Pătrăţel.

Date de iesire

In fisierul de iesire football2.out afişaţi răspunsurile pentru cele T teste, pe un singur rând, fără spaţii între ele. Daca Pătrăţel câştigă premiul într-un test, afişaţi 1; altfel, afişaţi 0.

Restrictii

• T ≤ 100.000
• Fie SN suma valorilor lui N pentru toate testele dintr-un fişier. Atunci SN ≤ 100.000
• K, mărimea oricărei clase ≤ 1.000.000.000
• Pentru 26 de puncte, K = 1
• Pentru alte 8 puncte, N ≤ 10, SN ≤ 100, mărimea oricărei clase ≤ 3.
• Pentru alte 11 puncte N ≤ 10, mărimea oricărei clase ≤ 5.
• Pentru alte 8 puncte, N = 1, K, mărimea oricărei clase ≤ 100.
• Pentru alte 16 puncte, N = 1
• Pentru alte 16 puncte K = 2
• Pentru alte 7 puncte, K e putere de 2

Exemple

Explicatie

În primul test sunt 5 elevi în total, şi exact unul va fi selectat la fiecare tură (căci K = 1). Astfel, selecţia va dura exact 5 ture, şi ultimul student va fi selectat în tura lui Pătraţel. Astfel Pătrăţel câştigă.

În al doilea test, Pătrăţel poate mai întâi să selecteze doi elevi din prima clasa. Apoi, după încă patru ture în care fiecare capitan selectează câte un elev (căci toate clasele au doar un elev), Pătrăţel câştigă.

În al treilea test, Pătrăţel poate selecta iniţial un elev.

Cum se trimit solutii?