Diferente pentru problema/sunmihai intre reviziile #2 si #26

Diferente intre titluri:

sunmihai
Sunmihai

Diferente intre continut:

== include(page="template/taskheader" task_id="sunmihai") ==
Poveste şi cerinţă...
Meseria de doctor nu necesita numai cunostinte sau indemanare, ci si inteligenta. Sunmihai, student la "Scoala de Studiu Medical si Farmece" din Lyon (meme 2020), rezolva zilnic jocuri ce dezvolta inteligenta, insa astazi s-a impotmolit. Sunmihai are initial N piese de domino cu cate 2 valori scrise pe ele, in stanga, respectiv in dreapta. O piesa de domino va dobori o alta piesa daca valoarea sa din dreapta esti egala cu valoarea din stanga a piesei ce urmeaza sa fie doborata. Sunmihai are la dispozitie operatii de tip:
 
* 1: intoarce piesa de domino cu costul A (valoarile din stanga si dreapta ale piesei se vor interschimba)
* 2: scoate o piesa oarecare din joc cu costul B (astfel, piesele vecine acesteia vor deveni in relatie; *nu* se poate aplica aceasta operatie pe prima si ultima piesa de domino)
* 3: adauga o piesa intre 2 alte piese de domino existente cu costul C (strict dupa prima piesa, dar inaintea ultimei piese; piesa adaugata poate avea valorile din stanga si dreapta orice numere)
 
Ajutati-l pe Sunmihai si determinati costul minim total astfel incat daca doboram prima piesa, sa cada implicit si ultima (evident, si toate aflate intre prima si ultima).
h2. Date de intrare
Fişierul de intrare $sunmihai.in$ ...
Fişierul de intrare $sunmihai.in$ va contine pe prima linie 4 numere N, A, B si C (cu semnificatia din enunt), iar pe fiecare a i-a linie dintre urmatoarele N, cate 2 numere t1 (reprezentand valoarea la stanga a piesei i), respectiv t2 (reprezentand valoarea la dreapta a piesei i).
h2. Date de ieşire
În fişierul de ieşire $sunmihai.out$ ...
În fişierul de ieşire $sunmihai.out$ se va afla un singur numar reprezentand costul total minim cerut.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$ ; $1 ≤ A, B, C ≤ 100$ ; $1 ≤ t1, t2 ≤ 100$ pentru orice domino
* Pentru $10$ puncte $1 ≤ N ≤ 10$ ; $1 ≤ t1, t2 ≤ 5$ pentru orice domino
* Pentru alte $20$ puncte $1 ≤ N ≤ 500$ ; $1 ≤ t1, t2 ≤ 10$ pentru orice domino
* Pentru alte $20$ puncte $1 ≤ N ≤ 5.000$ ; $1 ≤ t1, t2 ≤ 50$ pentru orice domino
* Pentru alte $20$ puncte $1 ≤ N ≤ 20.000$ ; $1 ≤ t1, t2 ≤ 50$ pentru orice domino
h2. Exemplu
table(example). |_. sunmihai.in |_. sunmihai.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 5 8 1 7
2 3
1 1
1 3
3 1
2 1
| 9
|
h3. Explicaţie
...
Scoatem a 2-a si a 3-a piesa cu cost 2 in total si adaugam cu cost 7 o piesa inaintea ultimei piese, avand numarul din stanga 1 si numarul din dreapta 2. In total vom plati 9 unitati, iar dominourile vor arata: (2,3) , (3,1) , (1,2) , (2,1)
== include(page="template/taskfooter" task_id="sunmihai") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.