| Fişierul intrare/ieşire: | farfurii.in, farfurii.out | Sursă | preONI 2005 Runda 3 |
| Autor | Mircea Bogdan Pasoi | Adăugată de | |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Vezi solutiile trimise | Statistici
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.
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.
Date de intrare
Pe prima linie din fisierul de intrare farfurii.in se gasesc numerele naturale N si K.
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.
Restrictii
- 1 ≤ N ≤ 100.000
- 0 ≤ K ≤ N*(N-1)/2
- Pentru cel putin 40% din teste N ≤ 2.000
- O asezare (A1,A2...AN) este mai mica din punct de vedere lexicografic decat o alta asezare (B1,B2...BN) daca exista o pozitie p astfel incat Ap<Bp si A1=B1, A2=B2, ... Ap-1=Bp-1
Exemplu
| farfurii.in | farfurii.out |
|---|---|
| 7 8 | 1 2 5 7 6 4 3 |
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.
