Farfurii

farfurii

==Include(page="template/taskheader" task_id="farfurii")==

== include(page="template/taskheader" task_id="farfurii") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| farfurii.in | farfurii.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="farfurii") ==

==Include(page="template/raw")==
 
Link: [1]File-List
 
farfurii
 
 
 
In fiecare zi Zaharel este obligat de Eugenia sa spele farfuriile si tacamurile dupa fiecare masa. Dupa ce le spala el trebuie sa le aranjeze pe doua rafturi, farfuriile pe primul si tacamurile pe al doilea... dar nu oricum! El are N farfurii de marimi distincte, cuprinse intre 1 si N si K tacamuri identice. Pentru fiecare pereche de farfurii asezate in raft astfel incat farfuria de marime mai mare, dintre cele doua, apare inaintea farfuriei de marime mai mica, Zaharel pune un tacam pe randul al doilea.
 
h2. Cerinta
 
Ajutati-l pe Zaharel sa aseze toate farfuriile pe primul raft astfel incat sa puna toate tacamurile pe al doilea raft. Dintre toate asezarile posibile determinati-o pe aceea minim lexicografica din punct de vedere al marimilor.
 
h2. Date de Intrare (fisier: farfurii.in)
 
Pe prima linie din fisierul de intrare se gasesc numerele naturale N si K.
 
h2. Date de Iesire (fisier: farfurii.out)
 
Pe prima linie din fisierul de iesire se vor gasi N numere distincte intre 1 si N reprezentand marimile farfuriilor, afisate in ordinea in care au asezate pe raft.
 
h2. Restrictii
 
S 1 <= N <= 100.000
 
S 0 <= K <= N*(N-1)/2
 
S Pentru cel putin 40% din teste N <= 2.000
 
S O asezare (A[1],A[2]...A[N]) este mai mica din punct de vedere lexicografic decat o alta asezare (B[1],B[2]...B[N]) daca exista o pozitie p astfel incat A[p]<B[p] si A[1]=B[1,] A[2]=B[2,] ... [,]A[p-1]=B[p-1
 
]
 
farfurii.in farfurii.out Explicatie
7 8 1 2 5 7 6 4 3 Pentru perechile de farfurii din asezare (5 4) (5 3)
(7 6) (7 4) (7 3) (6 4) (6 3) (4 3) Zaharel pune cate un tacam pe randul al doilea.
 
O alta asezare posibila este 1 2 6 5 7 4 3 dar aceasta este mai mare lexicografic decat cea din fisierul de iesire
 
 
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/farfurii/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="farfurii")==