Diferente pentru problema/farfurii intre reviziile #1 si #7

Nu exista diferente intre titluri.

Diferente intre continut:

==Include(page="template/taskheader" 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
 
==Include(page="template/taskheader" task_id="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
 
Pe prima linie din fisierul de intrare $farfurii.in$ se gasesc numerele naturale $N$ si {$K$}.
 
h2. Date de iesire
 
Pe prima linie din fisierul de iesire $farfurii.out$ se vor gasi $N$ numere distincte intre $1$ si $N$ reprezentand marimile farfuriilor, afisate in ordinea in care au asezate pe raft.
 
h2. Restrictii
 
* $1 &le; N &le; 100.000$
* $0 &le; K &le; N*(N-1)/2$
* Pentru cel putin $40%$ din teste $N &le; 2.000$
* 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~}$
 
h2. Exemplu
 
table(example). |_. farfurii.in |_. farfurii.out |
| 7 8
| 1 2 5 7 6 4 3 |
 
h3. Explicatii
 
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.
 
 
==Include(page="template/taskfooter" task_id="farfurii")==
References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/farfurii/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="farfurii")==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
305