Fişierul intrare/ieşire:	alpine.in, alpine.out	Sursă	ad-hoc
Autor	Cristian Francu	Adăugată de	Catalin Francu •Catalin.Francu
Timp execuţie pe test	0.2 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	2/5

Vezi solutiile 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

alpine.in	alpine.out
10 4 3 1 4 4 1 4 4 3 2 3 3 3 4	24 212232122231

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.