Zadanie
Za posledné obdobie mal Kúl Spolok Pandemiológov naozaj kopu práce. Popri bežných povinnostiach zvládali rozbehnúť nový výskum zameraný na boj s vírusmi. Po niekoľkých mesiacoch tvrdej driny sa dostavili veľmi dobré výsledky. Vytvorili metódu, podľa ktorej dokážu na vírus jednoducho vytvoriť spoľahlivú vakcínu, a tak ho zneškodniť. Spôsob je veľmi jednoduchý. Každý vírus má svoje charakteristické číslo \(n\). Na to, aby našli vakcínu k danému vírusu stačí nájsť \(n\) takých prirodzených čísel, že prvých \(n/2\) čísel je parných a druhých \(n/2\) nepárnych. Zároveň musí platiť, že súčet prvej polovice je rovný súčtu druhej polovice. Kým ale celý KSP odišiel na konferecie prezentovať tento úžasný vynález, tebe nechali na starosť kopu vírusov, na ktoré máš nájsť vakcínu…
Úloha
KSP ti nechalo \(t\) vírusov, a ty máš pre každý z nich povedať či naň existuje vakcína. Ak existuje, tak takú nejakú vakcínu máš vypísať. Pre všetky čísla \(n_i\), pre ktoré existuje vakcína máš vypísať presne \(n_i\) medzerou oddelených čísel takých, že súčet prvej polovice čísel sa rovná súčtu druhej polovice. Všetky čísla musia byť unikátne a všetky čísla v prvej polovici musia byť párne a v druhej nepárne. Takýchto možností je samozrejme veľa a môžete vypísať ľubovoľnú z nich.
Formát vstupu
Na prvom riadku vstupu dostanete číslo \(t\), (\(t \leq 100\)), ktoré označuje počet vírusov. Nasleduje \(t\) riadkov, na každom je práve jedno párne číslo \(n_i\), (\(n_i \leq 10\,000\)), ktoré označuje vírus.
Formát výstupu
Pre každé \(n_i\) na samostatný riadok vypíšte “ano” alebo “nie”, podľa toho či sa dá urobiť pole dĺžky \(n_i\) také, že spĺňa podmienky zo zadania. V prípade ak vypíšete “ano”, na nový riadok vypíšte aj toto pole. Teda, vypíšete \(n_i\) medzerou oddelených čísel \(a_{i,j}\). Dodržte aby \(0 < a_{i,j} < 1\,000\,000\), a každé číslo bolo unikátne (nachádzalo sa v Tebou vypísanej postupnosti čísel len raz).
Príklad
Input:
5
10
2
4
8
6
Output:
nie
nie
ano
2 4 1 5
ano
2 6 4 8 5 3 1 11
nie
Samozrejme, toto nie sú jediné možnosti, ktoré mohli byť vypísané za “ano”. Napríklad za prvým “ano” rovnako mohlo byť aj “6 10 11 5”, alebo “4 2 5 1”.
Poďme si najprv povedať, kedy a prečo vieme, resp. nevieme na danú vakcínu nájsť vírus. Prečo by sa vlastne taký vírus nemal dať urobiť? Veď vieme predsa na obe strany dať (takmer) ľubovolné čísla, nie? V sampli ale poľahky nájdeme nejaké prípady, ktoré spája to, že sa na daný vírus nedá nájsť vakcína. Čo majú spoločné?
Aby sme na to prišli, tak musíme použiť trošku matematiky. Totiž, nech sčítame akýkoľvek počet párnych čísel, výsledok bude vždy párny. Pri nepárnych číslach záleží na počte sčítavaných čísel. Ak sčítame nepárny počet nepárnych čísel, výsledok bude nepárny (napr. \(3+3+3 = 9\)), ale ak sčítame párny počet nepárnych čísel, tak výsledok bude párny (\(3+3 = 6\)).
Z toho vyplýva, že ak dostaneme úlohu vypísať nepárny počet párnych čísel, a nepárny počet nepárnych čísel tak, aby sa ich súčet rovnal, tak sa to nedá. Pretože, kým súčet párnych bude vždy párny, súčet nepárnych bude nepárny (lebo ich je nepárny počet). Takto sme našli prípad, kedy sa vakcína na vírus nedá nájsť. Čo ale ostatné prípady? Ak máme vypísať párny počet párnych a párny počet nepárnych čísel, tak sú súčty oboch častí párne, a nie je nič, čo by nám bránilo vytvoriť dve skupiny s rovnakým súčtom.
Teraz, keď už vieme, kedy sa to dá, a kedy nie, je riešenie úlohy jednoduché. Ak sa to nedá, teda ak \(n/2\) je nepárne, tak vypíšeme “nie”.
Vo všetkých ostatných prípadoch vypíšeme “ano”, a vypíšeme takú postupnosť čísel, ktorá spĺňa podmienky zo zadania. Napríklad začneme postupne vypisovať párne čísla, presne toľko, koľko treba (\(n/2\)), a počítame si ich súčet. Potom vypíšeme o jedno nepárne menej (\(n/2 - 1\)), ako treba (zase si počítame súčet), a na koniec vypíšeme také číslo, koľko je rozdiel súčtov (prečo bude nepárne sme si povedali v prvom odstavci).
Vzorový kód si nepočíta súčty, ale robí to trochu trikovejšie, a to tak, že ak je prvé párne \(2\), a prvé nepárne \(1\), tak s každou dvojicou (jedným párnym, jednám nepárnym) sa zvýši rozdiel medzi súčtami o \(1\).
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.