== include(page="template/taskheader" task_id="nave_interdimensionale") ==
Alex tocmai a redescoperit un joc din copilărie de care este atât de încântat încât s-a gândit să-l propună la concursul <tex>\textbf{Autumn WarmUp 2020} </tex>. Cum probabil v-aţi aşteptat deja, el oferă <tex>100</tex> de puncte ca recompensă celor care rezolvă corect jocul.
Alex tocmai a redescoperit un joc din copilărie de care este atât de încântat încât s-a gândit să-l propună la concursul Autumn WarmUp 2020. Cum probabil v-aţi aşteptat deja, el oferă 100 de puncte ca recompensă celor care rezolvă corect jocul.
Fie N nave interdimensionale aflate la diferite coordonate întregi <tex>(x, y) </tex>. În fiecare secundă, poate fi efectuată o operaţie de tipul: se selectează o navă <tex>i</tex> aflată la poziţia <tex>(x_{i}, y_{i}) </tex> şi se mută în una dintre cele <tex>4</tex> poziţii vecine: <tex>(x_{i+1}, y_{i}), (x_{i-1}, y_{i}), (x_{i}, y_{i+1}), (x_{i}, y_{i-1}) </tex>.
Fie N nave planare aflate la diferite coordonate întregi (x, y). În fiecare secundă, poate fi efectuată o operaţie de tipul: se selectează o navă i aflată la poziţia (xi, yi) şi se mută în una dintre cele 4 poziţii vecine: (xi+1, yi), (xi-1, yi), (xi, yi+1), (xi, yi-1).
Alex vrea să afle numărul minim de secunde după care vor fi cel puţin <tex>K</tex> linii cu măcar o navă şi cel puţin <tex>K </tex> coloane cu măcar o navă.
h2. Cerinţă
Cunoscând coordonatele celor <tex>N</tex> nave interdimensionale, aflaţi numărul minim de secunde cerut de Alex.
Alex vrea să afle numărul minim de secunde după care vor fi cel puţin K linii cu măcar o navă şi cel puţin K coloane cu măcar o navă.
h2. Date de intrare
Fişierul de intrare $nave_interdimensionale.in$ conţine pe prima linie numerele naturale <tex>N</tex> şi <tex>K</tex> separate printr-un spaţiu, iar pe următoarele <tex>N</tex> linii se află câte două numere naturale separate printr-un spaţiu, reprezentând coordonatele navelor.
Fişierul de intrare $nave_interdimensionale.in$ ...
h2. Date de ieşire
În fişierul de ieşire $nave_interdimensionale.out$ conţine pe prima linie numărul minim de secunde cerut de Alex.
În fişierul de ieşire $nave_interdimensionale.out$ ...
h2. Restricţii
* <tex> K \le N </tex>
* Se -garantează- poate demonstra că există mereu soluţie.
* Coordonatele navelor în orice secundă -sunt- *trebuie să fie* numere <tex>\textbf{nenegative} \le 10^{5} </tex>.
* $Subtaskul$ <tex>1</tex> $de$ <tex>10 </tex> $puncte$ : <tex> N \le 13 </tex> $şi$ <tex> 0 \le x, y \le 31 </tex>
* $Subtaskul$ <tex>2</tex> $de$ <tex>10 </tex> $puncte$ : <tex> N \le 50 </tex> $şi$ <tex> 0 \le x, y \le 200 </tex>
* $Subtaskul$ <tex>3</tex> $de$ <tex>10 </tex> $puncte$ : <tex> N \le 50 </tex> $şi$ <tex> 0 \le x, y \le 2000 </tex>
* $Subtaskul$ <tex>4</tex> $de$ <tex>10 </tex> $puncte$ : <tex> N \le 200 </tex> $şi$ <tex> 0 \le x, y \le 2000 </tex> şi <tex> K \le 100 </tex>
* $Subtaskul$ <tex>5</tex> $de$ <tex> 60 </tex> $puncte$ : <tex> N \le 10^{5} </tex> $şi$ <tex> 0 \le x, y \le 10^{4} </tex> şi <tex> K \le 1000 </tex>
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. nave_interdimensionale.in |_. nave_interdimensionale.out |
| 7 4
2 2
2 2
3 2
4 2
4 2
4 3
4 3
| 3
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|3 3
0 0
0 0
0 0
|6
|
h3. Explicaţie
h4. Pentru primul exemplu:
Cifra de lângă litera reprezintă numărul de nave care se află în acel punct, iar punctele cu <tex> ' </tex> sunt obţinute din cele iniţiale.
!problema/nave_interdimensionale?EX2.png!
!problema/nave_interdimensionale?EX3.png!
Prima navă se mută spre stânga <tex>(2, 2) -> (1, 2) </tex>
A patra navă se mută în jos <tex>(4, 2) -> (4, 1) </tex>
Ultima navă se mută în sus <tex>(4, 3) -> (4, 4) </tex>
Punctele ocupate sunt: <tex>(1, 2), (2, 2), (3, 2), (4, 1), (4, 2), (4, 3), (4, 4) </tex>.
h4. Pentru al doilea exemplu:
O nava se mută în <tex> (1, 1) </tex> cu cost 2 iar altă navă se mută în <tex>(2, 2)</tex> cu cost 4.
Nu putem să mutăm nava în <tex>(-1, -1)</tex> deoarece încalcă restricţiile.
...
== include(page="template/taskfooter" task_id="nave_interdimensionale") ==
