| 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 de execuție pe test | 0.2 sec | Limită de memorie | 65536 KB |
| Scorul tău | N/A | Dificultate |
  2
|
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 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.
