Fişierul intrare/ieşire: | alpine.in, alpine.out | Sursă | ad-hoc |
Autor | Cristian Francu | Adăugată de | |
Timp execuţie pe test | 0.2 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
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 Di, 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ă T1 secunde.
- Poate adăuga mesajul curent la o selecţie. Această operaţie durează T2 secunde.
- Poate salva toate mesajele selectate în acelaşi director. Această operaţie durează T3 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 T1 T2 T3, cu semnificaţiile de mai sus, despărţite prin spaţii. Pe a doua linie se află numerele naturale D1, D2, ..., DN, 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 ≤ T1, T2, T3 ≤ 10.000
- 1 ≤ Di ≤ 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.