Fişierul intrare/ieşire:magazin.in, magazin.outSursăpreONI 2007, Runda 3
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inmagazin.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content