Nave Interdimensionale

nave interdimensionale

== 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") ==