Diferente pentru problema/pachete intre reviziile #1 si #12

Diferente intre titluri:

pachete
Pachete

Diferente intre continut:

== include(page="template/taskheader" task_id="pachete") ==
Poveste si cerinta...
Zaharel si-a facut firma de curierat si trebuie sa transporte cate un pachet fiecaruia din cei $N$ clienti din oras. Orasul in care locuieste Zaharel este foarte asemanator cu Manhattan, in sensul ca te poti deplasa doar pe directiile nord-sud si est-vest. De asemenea, fiecare client, cat si sediul firmei, poate fi reprezentat printr-un punct in plan. Fiecare pachet trebuie livrat cat de repede posibil, astfel incat livrarea pachetelor se va face mereu pe un drum de distanta (Manhattan) minima. Deoarece predarea pachetului unui client se face foarte repede, pe drumul catre un client, Zaharel poate alege sa livreze pachete si altor clienti, cu conditia sa se pastreze distanta minima.
Stiind locatia sediului si a celor $N$ clienti, determinati numarul minim de drumuri pe care trebuie sa le faca Zaharel pentru a livra toate pachetele.
h2. Date de intrare
...
In fisierul $pachete.in$ se afla pe prima linie numarul natural $N$ reprezentand numarul de clienti. A doua linie va contine doua numere naturale $Ox Oy$ reprezentand coordonatele $x$, respctiv $y$ a sediului firmei. Urmeaza $N$ linii fiecare continand doua numere naturale $X{~i~}$ $Y{~i~}$, reprezentand coordonatele clientilor.
h2. Date de iesire
...
Fisierul de iesire $pachete.out$ va contine o singura linie pe care se va afla numarul minim de drumuri pe care trebuie sa le faca Zaharel.
h2. Restrictii
... ≤ ...
* $1 ≤ N ≤ 50.000$
* Distana Manhattan dintre doua puncte $(x{~1~},y{~1~})$ si $(x{~2~},y{~2~})$ este $|x{~1~}-x{~2~}|+|y{~1~}-y{~2~}|$
* Toatele cele $N$ puncte, cat si sediul firmei, au coordonatele $x$ diferite doua cate doua, cat si coordonatele $y$
* $0 ≤ x{~i~}, y{~i~} ≤ 2*10^9^$
h2. Exemplu
table(example). |_. pachete.in |_. pachete.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
| 4
0 3
1 2
2 5
3 0
4 1
| 3 |
h3. Explicatie
...
Cele 3 drumuri sunt:
$(0,3) -> (2,5)$
$(0,3) -> (1,2) -> (3,0)$
$(0,3) -> (4,1)$
== include(page="template/taskfooter" task_id="pachete") ==
 
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
1466