Diferențe pentru problema/voodoo între reviziile #12 si #30

== include(page="template/taskheader" task_id="voodoo") ==

Se dă $*N*$, $*X*$, $*Y*$ și un șir de $*N*$ numere naturale $*a*[~1~]$, $*a*[~2~]$, ..., $*a*~*N*~$.
Definim costul unui rearajament $*p*$ al șirului $*a*$ ca fiind suma tuturor subsecvențelor $(i, j)$ astfel încat $1$ ≤ $i$ ≤ $*X*$ și $*Y*$ ≤ $j$ ≤ $*N*$. Costul poate fi calculat astfel:

Se dă [$N$], [$X$], $Y$ și un șir de $N$ numere naturale [$a$][~1~], [$a$][~2~], ..., [$a$][~N~].
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:

!>{width:300px; height:auto;}problema/voodoo?pseudocod_.png!

!problema/voodoo?pseudocod2!

 
 
$  $
$  $
$  $
$  $
$  $
$  $
$  $
$  $
$  $
 
 
Aflați costul minim al unei rearanjări a șirului $*a*$ cât și o rearanjare ce obține acest cost minim.

Aflați costul minim al unei rearanjări a șirului $a$ cât și o rearanjare ce obține acest cost minim.

h2. Date de intrare

Fișierul de intrare $voodoo.in$ conține pe prima linie, în aceast ordine numerele naturale $*N*$, $*X*$, $*Y*$, separate prin spațiu. Pe cea de-a doua linie se află $*N*$ numere naturale separate prin spațiu, reprezentând șirul $*a*$.

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$].

h2. 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 afla $*N*$ numere naturale care reprezintă o rearanjare a șirului $*a*$ ce obține cost minim.

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.

h2. Restricții

* $1$ ≤ $*X*$ < $*Y*$ ≤ $*N*$ ≤ $1.000.000$
* $1$ ≤ $*a*~*i*~$ ≤ $1.000.000$, pentru fiecare $i$ de la $1$ la $*N*$
* Se garantează că răspunsul se incadreaza pe tipul de date $long long$
* $50%$ din punctaj se acordă pentru afișarea costului minim corect
* $30%$ din teste satisfac $*N*$ ≤ $1.000$
* $60%$ din teste satisfac $*N*$ ≤ $10.000$

* $1$ ≤ $X$ < $Y$ ≤ $N$ ≤ $1.000.000$
* $0$ ≤ [$a$][~i~] ≤ $100.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 $40%$ din punctaj, se garantează că $N$ ≤ $10.000$
* pentru $60%$ din punctaj, se garantează că $N$ ≤ $100.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":parsare_io_c .

h2. Exemplu

table(example).

table(example).

|_. voodoo.in |_. voodoo.out |
|5 1 2
1 2 3 4 5

|5 2 4
1 3 3 4 5
|46

5 3 1 3 4

5 3 1 3 4

|

| 8 2 6
1 2 6 2 10 9 3 5
|202
6 2 1 2 3 5 9 10

| 10 2 6
1 2 8 6 2 10 9 3 5 8
|322
8 2 3 5 1 2 6 8 9 10

|
h3. Explicație

Pentru primul exemplu, rearanjarea este $2 1 3 4 5$, costul acestei rearanjari este:

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$

Se poate demonstra ca nu exista alta rearanjare cu costul mai mic.

Nu există nicio altă rearanjare cu cost mai mic.

Pentru al doilea exemplu, rearanjarea este $5 3 1 3 4$, costul acestei rearanjari este:

Pentru al doilea exemplu, rearanjarea este $5 3 1 3 4$, costul acestei rearanjări 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.
 
 

Din nou, nu există alte rearanjări ale șirului $a$ care au costul mai mic de 46.

== include(page="template/taskfooter" task_id="voodoo") ==