| Fişierul intrare/ieşire: | gardening.in, gardening.out | Sursă | RMI 2021 |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Gardening
Azusa, vrăjitoarea munţilor, doreşte să se apuce de o activitate distractivă cu prietena ei, Laika: grădinărit. Ele vor să construiască o grădină dreptunghiulară de N metri înălţime şi M metri lăţime. Grădina este împărţită în pătrate de 1 metru pe 1 metru. Ele şi-au pus următoarea întrebare: ce flori ar trebui ele să planteze?
Laika are la dispoziţie K tipuri diferite de flori. Azusa şi Laika vor planta câte un tip de floare în fiecare pătrat de 1 metru pe 1 metru. În plus, din motive estetice, grădina trebuie să satisfacă următoarele proprietăţi:
- Fiecare tip de floare trebuie să apară cel puţin odată în grădină.
- Pentru oricare două pătrate unde acelaşi tip de floare este plantat, trebuie să existe un drum între ele unde toate pătratele intermediare au acelaşi tip de floare. Spre exemplu, următoarele grădini nu sunt permise:
- Orice pătrat trebuie să aibă exact două pătrate adiacente în care e plantat acelaşi tip de floare. Spre exemplu, următoarele grădini nu sunt permise:
A se observa că, în restricţiile de mai sus, două pătrate sunt "adiacente" dacă şi numai dacă au o latură în comun (nu doar un colţ); şi un drum este o secvenţă de pătrate adiacente.
Ţi se dau T valori diferite pentru N, M şi K. Ajutaţi-le pe Azusa şi Laika să creeze grădini care satisfac condiţiile pentru fiecare test din input sau, dacă nu există soluţie, spuneţi-le că acest lucru este imposibil.
Date de intrare
Prima linie din input conţine numărul întreg T. În continuare, urmează T linii, fiecare descriind un test. Fiecare test consistă în trei numere întregi N, M şi K.
Date de ieşire
Afişaţi răspunsurile pentru fiecare test în ordine. Pentru un test, dacă nu există soluţie, afişaţi NO pe o singură linie. Altfel, mai întâi afişati YES pe o singură linie, apoi afişati N x M numere întregi aranjate pe N linii şi M coloane descriind grădina cerută. Liniile şi coloanele din output corespund liniilor şi coloanelor grădinii, fiecare număr întreg resprezentând tipul de flori plantate într-un pătrat de 1 metru pe 1 metru. Tipurile sunt indexate de la 1 la K. Dacă sunt mai multe soluţii corecte puţeti afişa oricare din ele.
Restrictii
- 1 ≤ N, M ≤ 200 000.
- 1 ≤ K ≤ N x M.
- Fie S egal cu suma N x M pentru toate testele dintr-un fişier pentru care există răspuns (i.e. pentru care răspunsul afişat nu este NO).
- S ≤ 200 000.
- Pentru 5 puncte, N, M ≤ 4.
- Pentru alte 6 puncte, N ≤ 4.
- Pentru alte 10 puncte, N ≤ 6.
- Pentru alte 18 puncte, N = M.
- Pentru alte 36 de puncte, K este un număr între 1 şi N x M ales uniform aleator.
Exemple
| gardening.in | gardening.out |
|---|---|
| 5 2 2 2 2 2 1 4 4 4 4 4 2 4 6 3 | NO YES 1 1 1 1 YES 1 1 2 2 1 1 2 2 3 3 4 4 3 3 4 4 YES 1 1 1 1 1 2 2 1 1 2 2 1 1 1 1 1 YES 1 1 1 1 1 1 1 2 2 3 3 1 1 2 2 3 3 1 1 1 1 1 1 1 |
Explicaţii
Pentru primul test case, observăm ca nicio gradină de 2 pe 2 cu 2 tipuri de flori nu este corectă. Aşadar vom afisa NO. Celelalte grădini sunt ilustrate mai jos:
