Fişierul intrare/ieşire:alpine.in, alpine.outSursăad-hoc
AutorCristian FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inalpine.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici