Fișierul intrare/ieșire:	alpine.in, alpine.out	Sursă	ad-hoc
Autor	Cristian Frâncu	Adăugată de	Cătălin Frâncu •Catalin.Francu
Timp execuție pe test	0.2 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	2/5

Poți vedea testele pentru această problemă accesând atașamentele.

Vezi soluțiile trimise | Statistici

Alpine (clasele 10-12)

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₁ secunde.
• Poate adăuga mesajul curent la o selecție. Această operație durează T₂ secunde.
• Poate salva toate mesajele selectate în același director. Această operație durează T₃ secunde. După salvare, selecția este golită.
• Inițial, selecția este goală.

Date de intrare

Fișierul de intrare alpine.in conține pe prima linie numerele naturale N K T₁ T₂ T₃, cu semnificațiile de mai sus, despărțite prin spații. Pe a doua linie se află numerele naturale D₁, D₂, ..., D_N, despărțite prin spații.

Date de ieșire

Î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:

• ‘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

Restricții și observații

• 1 ≤ N ≤ 10.000
• 1 ≤ K ≤ 1.000
• 1 ≤ T₁, T₂, T₃ ≤ 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.

Exemplu

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.