Fişierul intrare/ieşire:nave_interdimensionale.in, nave_interdimensionale.outSursăAutumn WarmUp 2020
AutorCezar Trisca-Vicol, Cosmin-Mihai TutunaruAdăugată deautumnwarmup2020autumnwarmup2020 autumnwarmup2020
Timp execuţie pe test0.4 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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 \textbf{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 (x, y) . În fiecare secundă, poate fi efectuată o operaţie de tipul: se selectează o navă i aflată la poziţia (x_{i}, y_{i}) şi se mută în una dintre cele 4 poziţii vecine: (x_{i+1}, y_{i}), (x_{i-1}, y_{i}), (x_{i}, y_{i+1}), (x_{i}, y_{i-1}) .

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ă.

Cerinţă

Cunoscând coordonatele celor N nave interdimensionale, aflaţi numărul minim de secunde cerut de Alex.

Date de intrare

Fişierul de intrare nave_interdimensionale.in conţine pe prima linie numerele naturale N şi K separate printr-un spaţiu, iar pe următoarele N linii se află câte două numere naturale separate printr-un spaţiu, reprezentând coordonatele navelor.

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.

Restricţii

  •  K \le N
  • Se garantează poate demonstra că există mereu soluţie.
  • Coordonatele navelor în orice secundă sunt trebuie să fie numere \textbf{nenegative} \le 10^{5} .
  • Subtaskul 1 de 10 puncte :  N \le 13 şi  0 \le x, y \le 31
  • Subtaskul 2 de 10 puncte :  N \le 50 şi  0 \le x, y \le 200
  • Subtaskul 3 de 10 puncte :  N \le 50 şi  0 \le x, y \le 2000
  • Subtaskul 4 de 10 puncte :  N \le 200 şi  0 \le x, y \le 2000 şi  K \le 100
  • Subtaskul 5 de  60 puncte :  N \le 10^{5} şi  0 \le x, y \le 10^{4} şi  K  \le 1000

Exemplu

nave_interdimensionale.innave_interdimensionale.out
7 4
2 2
2 2
3 2
4 2
4 2
4 3
4 3
3
3 3
0 0
0 0
0 0
6

Explicaţie

Pentru primul exemplu:

Cifra de lângă litera reprezintă numărul de nave care se află în acel punct, iar punctele cu  ' sunt obţinute din cele iniţiale.

Prima navă se mută spre stânga (2, 2) -> (1, 2)
A patra navă se mută în jos (4, 2) -> (4, 1)
Ultima navă se mută în sus (4, 3) -> (4, 4)

Punctele ocupate sunt: (1, 2), (2, 2), (3, 2), (4, 1), (4, 2), (4, 3), (4, 4) .

Pentru al doilea exemplu:

O nava se mută în   (1, 1) cu cost 2 iar altă navă se mută în (2, 2) cu cost 4.
Nu putem să mutăm nava în (-1, -1) deoarece încalcă restricţiile.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?