== include(page="template/taskheader" task_id="alpine") ==
Poveste și cerință...
Un hacker își citește e-mailul cu programul Alpine. Pe lângă directorul Inbox, în care intră implicit mesajele primite, el și-a mai definit $K$ directoare (pentru mesajele de la familie, prieteni, serviciu etc.). Venit dintr-o vacanță, hackerul observă că i s-au adunat $N$ mesaje în Inbox. După ce își citește poșta, hackerul dorește să salveze mesajul cu numărul $i$ în directorul $D[~i~]$, pentru $1 ≤ i ≤ N$. El caută o metodă cât mai rapidă de a salva mesajele, cu următoarele reguli:
* Poziționează cursorul pe primul mesaj din Inbox.
* Se poate deplasa de la un mesaj la altul, mergând doar în jos. Această operație este instantanee.
* Poate salva mesajul curent în directorul său potrivit. Această operație durează $T[~1~]$ secunde.
* Poate adăuga mesajul curent la o _selecție_. Această operație durează $T[~2~]$ secunde.
* Poate salva toate mesajele selectate în același director. Această operație durează $T[~3~]$ secunde. După salvare, selecția este golită.
* Inițial, selecția este goală.
h2. Date de intrare
Fișierul de intrare $alpine.in$ ...
Fișierul de intrare $alpine.in$ conține pe prima linie numerele naturale $N K T[~1~] T[~2~] T[~3~]$, cu semnificațiile de mai sus, despărțite prin spații. Pe a doua linie se află numerele naturale $D[~1~], D[~2~], ..., D[~N~]$, despărțite prin spații.
h2. Date de ieșire
În fișierul de ieșire $alpine.out$ ...
În fișierul de ieșire $alpine.out$ se va tipări pe prima linie costul total minim pentru a salva fiecare mesaj în directorul dorit. Pe a doua linie se va tipări un șir de caractere '1', '2', și '3', fără spații, care redau comenzile pentru salvarea mesajelor:
h2. Restricții
* '1' pentru salvarea mesajului curent și avansarea la următorul
* '2' pentru adăugarea mesajului curent la selecție și avansarea la următorul
* '3' pentru salvarea selecției
h2. Restricții și observații
* $1 ≤ N ≤ 10.000$
* $1 ≤ K ≤ 1.000$
* $1 ≤ T[~1~], T[~2~], T[~3~] ≤ 10.000$
* $1 ≤ D[~i~] ≤ K$ pentru $1 ≤ i ≤ N$
* Soluția nu este unică.
* Pentru calcularea corectă doar a costului se acordă 30% din punctaj.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. alpine.in |_. alpine.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 10 4 3 1 4
4 1 4 4 3 2 3 3 3 4
| 24
212232122231
|
h3. Explicație
...
Comenzile sunt:
* adaugă mesajul 1 la selecție (cost 1);
* salvează mesajul 2 în directorul 1 (cost 3);
* adaugă mesajul 3 la selecție (cost 1);
* adaugă mesajul 4 la selecție (cost 1);
* salvează selecția (mesajele 1, 3 și 4) în directorul 4 (cost 4);
* adaugă mesajul 5 la selecție (cost 1);
* salvează mesajul 6 în directorul 2 (cost 3);
* adaugă mesajul 7 la selecție (cost 1);
* adaugă mesajul 8 la selecție (cost 1);
* adaugă mesajul 9 la selecție (cost 1);
* salvează selecția (mesajele 5, 7, 8 și 9) în directorul 3 (cost 4);
* salvează mesajul 10 în directorul 4 (cost 3);
Cost total: 24.
== include(page="template/taskfooter" task_id="alpine") ==
