Fişierul intrare/ieşire: | marmote.in, marmote.out | Sursă | Algoritmiada 2009, Runda 2 |
Autor | Andrei Grigorean | Adăugată de | |
Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Marmote
Miruna a primit mostenire de la matusa Tamara o livada ce poate fi reprezentanta sub forma unei matrice cu N linii si M coloane. Livada se afla la baza unui munte locuit de K marmote. Deoarece a venit iarna, este timpul ca marmotele sa coboare la altitudini mai mici pentru a se adaposti de frig. In fiecare zi, cate o marmota soseste in livada Mirunei si vrea sa isi construiasca o vizuina. Fiecare marmota isi alege un punct de coordonate Xi si Yi. Vizuina sa va fi formata din toate pozitiile campului aflate la o distanta Manhattan mai mica sau egala cu un numar dat L de pozitia (Xi, Yi). In cazul in care exista cel putin o pozitie din vizuina care face deja parte dintr-o vizuina construita anterior, marmota va refuza sa se stabileasca in livada Mirunei si va pleca in lumea larga.
Date de intrare
Fişierul de intrare marmote.in va contine pe prima linie 4 numere intregi N, M, K si L avand semnficatia din enunt. Urmatoarele K linii vor contine cate doua numere intregi Xi si Yi, valorile asociate marmotei cu indicele i.
Date de ieşire
În fişierul de ieşire marmote.out veti afisa in ordine crescatoare indicii marmotelor care isi vor construi viziuna in livada Mirunei. Aceste valori vor fi afisate pe cate o linie.
Restricţii si precizari
- 1 ≤ N ≤ 1 000
- 1 ≤ M ≤ 1 000
- 1 ≤ K ≤ 100 000
- 1 ≤ L ≤ N, M
- 1 ≤ Xi ≤ N
- 1 ≤ Yi ≤ M
- Distanta Manhattan intre doua puncte (X1, Y1) si (X2, Y2) este egala cu |X1 - X2| + |Y1 - Y2|
Exemplu
marmote.in | marmote.out |
---|---|
10 12 6 3 3 6 5 9 7 1 9 4 4 11 2 10 | 1 3 |