Fişierul intrare/ieşire:wall.in, wall.outSursăAlgoritmiada 2017, Runda 1
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Wall

Republica Federala Serbanistan a fost separata de vecina ei din Sud, Republica Federala Popanistan, printr-un zid. Acest zid este impartit in Z sectiuni adiacente si are un singur paznic, situat initial pe sectiunea 1. Zidul a fost ridicat pentru a nu permite imigrantilor din Popanistan sa intre ilegal in Serbanistan, dar in timp, situatia in Serbanistan s-a deteriorat, astfel incat acum zidul are rolul de a-si tine proprii cetateni in interiorul tarii. Astazi, N dintre acesti cetateni vor sa evadeze, sarind peste zid. Pentru fiecare dintre cei N cetateni se cunoaste timpul sau de escaladare a zidului: al i-lea cetatean are nevoie de time[i] secunde pentru a sari zidul. La fiecare moment de timp, maxim un cetatean va incerca sa escaladeze zidul. El va alege una din cele Z sectiuni ale zidului pentru a face acest lucru. In momentul in care un cetatean incepe escaladarea, paznicul se va indrepta spre el cu o viteza de o sectiune de zid pe secunda. Daca cetateanul termina escaladarea inainte ca paznicul sa ajunga la sectiunea in cauza, cetateanul este evadat iar paznicul se opreste din miscare, ramanand pe loc. Daca paznicul ajunge in sectiunea in cauza exact in ultima secunda a sariturii cetateanului, cetateanul reuseste totusi sa evadeze.

Voi trebuie sa aflati o ordine a evadarii cetatenilor cat si sectiunea de zid pe care o va escalada fiecare cetatean astfel incat un numar maxim dintre ei sa poata evada cu succes.

Date de intrare

Fişierul de intrare wall.in va contine pe prima sa linie valoarile N si Z, semnificand numarul de cetateni care vor sa evadeze din Serbanistan, respectiv numarul de sectiuni ale zidului. Urmeaza N linii, a i-linie continand numarul de secunde necesar pentru ca al i-lea cetatean sa escaladeze zidul.

Date de ieşire

Fişierul de ieşire wall.out ca contine pe prima sa linie valoarea MAX, semnificand numarul maxim de cetateni care pot evada cu succes. Urmeaza N linii care contin cate doua valori: indicele cetateanului pe care-l vom trimite sa evadeze in momentul respectiv (in ordinea data in fisierul de intrare), respectiv sectiunea de zid pe care acesta o va escalada.

Pentru ca solutia voastra sa fie corecta trebuie ca sirul de indici sa formeze o permutare, iar fiecare sectiune afisata sa se afle in intervalul [1..Z]. Bineinteles, trebuie ca urmand aceasta strategie sa evadeze exact MAX cetateni. Daca exista mai multe solutii corecte este acceptata oricare dintre acestea.

Notati ca toti cei N evadati trebuie sa incerce sa sara zidul la un moment dat, indiferent de rezultatul acestei tentative.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ Z ≤ 100.000
  • 1 ≤ time[i] ≤ 100.000

Exemplu

wall.inwall.out
3 5
1
1
2
3
1 5
2 5
3 5
3 5
4
4
4
3
1 5
2 1
3 5

Explicaţie

In exemplul 1, zidul este suficient de lung astfel incat toti cetatenii sa poata sari zidul prin sectiunea 5 fara sa fie ajunsi de paznic. Dupa trecerea cetateanului 1, paznicul se va afla in sectiunea 2. Dupa trecerea cetateanului 2, paznicul se va afla in sectiunea 3, iar dupa trecerea cetateanului 3, paznicul s-ar afla in sectiunea 5. Observam ca desi paznicul a ajuns in sectiunea 5 in ultima secunda a escaladarii cetateanului 3, acesta din urma a evadat cu succes. Daca paznicul ar fi ajuns cu o secunda mai devreme, lucrurile ar fi stat diferit.
In exemplul 2, cetateanul 1 va urca zidul pe sectiunea 5 si va reusi sa scape, moment in care paznicul se va afla in aceeasi sectiune. Cetateanul 2 va trece zidul pe la sectiunea 1, iar paznicul o sa se intoarca pentru a-l prinde, dar nu va reusi. In momentul in care cetateanul 3 incepe sa urce sectiunea 5, paznicul va fi in sectiunea 1 si va porni din nou spre sectiunea 5, nereusind nici de aceasta data sa prinda cetateanul care urca.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?