Fişierul intrare/ieşire:aranjare3.in, aranjare3.outSursăONI 2018, clasele 11-12, ziua 1
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1.6 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Aranjare3

Tanaka are o stivă cu N elemente şi vrea să le sorteze în ordine crescătoare de la bază spre vârf. Pentru a realiza acest lucru, el poate să achiziţioneze M stive suplimentare şi să efectueze K operaţii. O operaţie constă în a lua un element din vârful unei stive şi a-l insera în vârful unei alte stive. Tanaka poate alege convenabil valorile lui M şi K. Ajutaţi-l pe Tanaka să sorteze elementele astfel încât M * K să aibă valoare cât mai mică şi toate valorile să ajungă pe stiva iniţială în ordine crescătoare de la bază spre vârf.

Cerinţă

Afişaţi o secvenţă de K operaţii care folosesc M stive suplimentare în aşa fel încât să sortaţi elementele de pe stiva iniţială în ordine crescătoare de la bază spre vârf.

Date de intrare

Fişierul de intrare aranjare.in va conţine pe primul rând un număr natural nenul N. Pe al doilea rând se află o permutare a mulţimii {1, 2, …, N} ce reprezintă valorile iniţiale pe stiva lui Tanaka. Ultimul element din permutare este cel aflat în vârful stivei.

Date de ieşire

Fişierul de ieşire aranjare.out va conţine pe primul rând numerele naturale M şi K. Pe următoarele K rânduri se vor scrie perechi de numere s t (câte o pereche pe fiecare rând) reprezentând mutarea elementului din vârful stivei s în vârful stivei t. Se consideră că stiva iniţială a lui Tanaka are indicele 0, iar cele M stive suplimentare au indicii 1, 2, …, M.
Pentru acordarea punctelor este necesar ca după executarea tuturor operaţiilor indicate în fişierul de ieşire, elementele din stiva 0 să fie ordonate crescător de la bază spre vârf.

Restricţii şi precizări

  • Pentru teste în valoare de 25 de puncte avem N = 980. Pentru celelalte teste avem N = 10 000.
  • Pentru testele cu N = 980, punctajele se acordă în modul următor:
    • Dacă M * K ≤ 60 000, se acordă 100% din punctajul testului respectiv
    • Dacă 60 000 < M * K ≤ 200 000, se acordă 60% din punctajul testului respectiv
    • Dacă 200 000 < M * K ≤ 3 000 000 se acordă 20% din punctajul testului respectiv
  • Pentru testele cu N = 10 000, punctajele se acordă în modul următor:
    • Dacă M * K ≤ 800 000, se acordă 100% din punctajul testului respectiv
    • Dacă 800 000 < M * K ≤ 6 000 000, se acordă 60% din punctajul testului respectiv
    • Dacă 6 000 000 < M * K ≤ 300 000 000 se acordă 20% din punctajul testului respectiv

Exemplu

aranjare3.inaranjare3.out
3
3 2 1
2 9
0 1
0 1
0 1
1 2
1 2
1 2
2 0
2 0
2 0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?