Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | voodoo.in, voodoo.out | Sursă | preONI 2023 6-7 |
|---|---|---|---|
| Autor | Luca Mureșan | Vlad Tutunaru | Adăugată de |
Muresan Luca
•
LucaLucaM
|
| Timp de execuție pe test | 0.1 sec | Limită de memorie | 65536 KB |
| Scorul tău | N/A | Dificultate |
   3.5
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Voodoo
Se dă N, X, Y și un șir de N numere naturale a1, a2, ..., aN.
Definim costul unui rearajament p al șirului a ca fiind suma tuturor subsecvențelor (i, j) astfel încât 1 ≤ i ≤ X și Y ≤ j ≤ N. Costul poate fi calculat astfel:
Aflați costul minim al unei rearanjări a șirului a cât și o rearanjare ce obține acest cost minim.
Date de intrare
Fișierul de intrare voodoo.in conține pe prima linie, în această ordine numerele naturale N, X, Y, separate prin câte un spațiu. Pe cea de-a doua linie se află N numere naturale separate prin câte un spațiu, reprezentând șirul a.
Date de ieșire
Pe prima linie a fișierul de ieșire voodoo.out se află costul minim al unei rearanjări a șirului a, iar pe a doua linie se află N numere naturale separate prin câte un spațiu care reprezintă o rearanjare a șirului a ce obține cost minim.
Restricții
- 1 ≤ X < Y ≤ N ≤ 1.000.000
- 0 ≤ ai ≤ 1.000.000, pentru fiecare i de la 1 la N
- se garantează că răspunsul se incadrează pe tipul de date long long
- printr-un rearanjament al unui șir întelegem o reordonare a termenilor acestuia
- se acordă 50% din punctaj pentru afișarea costului minim corect
- pentru 30% din punctaj, se garantează că N ≤ 1.000
- pentru 60% din punctaj, se garantează că N ≤ 10.000
- ATENȚIE! Din cauza dimensiunii mari a datelor de intrare si de ieșire, se recomandă parsarea intrării și a ieșirii. Vă oferim o implementare suficientă pentru rezolvarea acestei probleme aici.
Exemplu
| voodoo.in | voodoo.out |
|---|---|
| 5 1 2 1 2 3 4 5 |
34 1 2 3 5 2 |
| 5 2 4 1 3 3 4 5 |
46 5 1 4 3 3 |
| 8 2 6 1 2 6 2 10 9 3 5 |
149 1 10 2 9 2 6 5 3 |
Explicație
Pentru primul exemplu, o rearanjare de cost minim este 2 1 3 4 5, costul acestei rearanjari este:
(2 + 1) + (2 + 1 + 3) + (2 + 1 + 3 + 4) + (2 + 1 + 3 + 4 + 5) =
3 + 6 + 10 + 15 = 34
Nu există nicio altă rearanjare cu cost mai mic.
Pentru al doilea exemplu, rearanjarea este 5 3 1 3 4, costul acestei rearanjari este:
(5 + 3 + 1 + 3) + (5 + 3 + 1 + 3 + 4) + (3 + 1 + 3) + (3 + 1 + 3 + 4) =
12 + 16 + 7 + 11 = 46
Din nou, se poate demonstra ca nu exista alte rearanjări ale șirului a care au costul mai mic decât 46.
