Fișierul intrare/ieșire alpine.in, alpine.out Sursă ad-hoc
Autor Cristian Frâncu Adăugată de avatar Catalin.Francu 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 stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii