Fişierul intrare/ieşire:marmote.in, marmote.outSursăAlgoritmiada 2009, Runda 2
AutorAndrei GrigoreanAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inmarmote.out
10 12 6 3
3 6
5 9
7 1
9 4
4 11
2 10
1
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content