Revizia anterioară Revizia următoare
| 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
| football2.in | football2.out |
|---|---|
| 3 3 1 3 1 1 5 2 2 1 1 1 1 1 2 3 |
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.
