| Fişierul intrare/ieşire: | magazin.in, magazin.out | Sursă | preONI 2007, Runda 3 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Mircea Pasoi •domino |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
Vezi solutiile trimise | Statistici
Magazin
Nargy si Fumeanu si-au deschis magazin. Acesta este aranjat astfel: sunt N-1 randuri de rafturi, intre rafturi existand N culoare. Fiecare rand este format din M rafturi de aceeasi marime. Distanta de la un raft la altul adiacent este de 1 metru, iar distanta intre un culoar si alt culoar adiacent este de D metri. De asemenea, distanta pentru a intra sau a iesi de pe culoar este de 1 metru. Mai jos este o diagrama a magazinului, punctele gri reprezentand locurile in care te poti opri pe culoar pentru a cumpara produse de pe un raft:
Zaharel vine intr-o zi la magazin cu o lista de P produse pe care vrea sa le cumpere. El intra in coltul stanga-jos al magazinului, cumpara cele P produse de pe lista (pentru fiecare produs stie exact culoarul si raftul unde trebuie sa se afle), si iese prin coltul dreapta-jos al magazinului. Determinati distanta minima a unui astfel de traseu.
Date de intrare
Fisierul de intrare magazin.in va contine prima linie numerele naturale P, N, M, D separate prin spatii. Urmatoarele P linii vor contine cate doua numere naturale x y cu semnificatia ca exista un produs pe care Zaharel vrea sa-l cumpere pe culoarul x, la raftul y.
Date de iesire
Fisierul de iesire magazin.out va contine un singur numar natural reprezentand distanta minima pe care Zaharel trebuie s-o parcurga.
Restrictii
- 1 ≤ P ≤ 50.000
- 1 ≤ N ≤ 30.000
- 1 ≤ M ≤ 25
- 1 ≤ D ≤ 5
- Pentru 50% din teste P ≤ 300, N ≤ 350
- Pot exista mai multe produse pe acelasi culoar si acelasi raft
- Culoarele sunt numerotate cu numere de la 1 la N iar rafturile de pe un culoar cu numere de la 1 la M, ca in diagrama
Exemplu
| magazin.in | magazin.out |
|---|---|
| 7 5 10 3 2 8 3 3 3 5 3 7 4 10 5 10 4 3 | 54 |
Explicatie
Ordinea in care Zaharel cumpara produsele este urmatoarea: 2, 3, 4, 1, 6, 5, 7 (produsele au fost numerotate in functie de ordinea din fisierul de intrare).
