blaturi

Blaturi

== include(page="template/taskheader" task_id="blaturi") ==

Comisia a promis că le va oferi participanţilor acestui concurs mâncare şi băutură gratuită. În urma mai multor discuţii, s-a hotărât că ar fi imoral să li se ofere pizza concurenţilor, aşa cum era prevăzut iniţial (doar suntem în perioadă de post, nu?!). Aşa că s-a decis că cel mai bine este să li se ofere blaturi (mâncarea favorită a comisiei).
Doi dintre membrii comisiei, maeştrii în arte culinare, s-au oferit să le prepare ei (contra cost, evident), în noaptea de dinaintea concursului. Având la dispoziţie un singur cuptor, ei nu pot prepara decât un blat la un moment de timp. Cei doi doresc să fie plătiţi în funcţie de timpul total petrecut pentru prepararea blaturilor (se ştie preţul pe minut cerut de fiecare). Mai mult de atât, fiecare va cere un cost suplimentar dacă este nevoit să prepare mai multe blaturi la rând:
Dacă primul prepară 3 blaturi unul după altul, el va cere costul suplimentar de 2 ori (+ costul standard pentru fiecare blat).

h3. __Un fel de "după muncă şi răsplată"__

S-a ajuns la concluzia că este nevoie de N blaturi pentru ziua concursului. Pentru fiecare se cunoaşte timpul de preparare. Cei doi au hotărât că primul va începe să prepare blaturile în ordinea 1, 2, ..., N iar cel de-al doilea în ordinea N, N-1, ..., 1.

Comisia a promis că le va oferi participanţilor acestui concurs mâncare şi băutură gratuită. În urma mai multor discuţii, s-a hotărât că ar fi imoral să li se ofere pizza concurenţilor, aşa cum era prevăzut iniţial (doar suntem în perioadă de post, nu?!). Aşa că s-a decis că cel mai bine este să li se ofere doar blaturile (partea favorită din pizza a comisiei).
Doi dintre membrii comisiei, nu dăm nume, maeştri în arte culinare, s-au oferit să le prepare ei (contra cost, evident), în noaptea de dinaintea concursului. Având la dispoziţie un singur cuptor, ei nu pot prepara decât un blat la un moment de timp. Cei doi doresc să fie plătiţi în funcţie de timpul total petrecut pentru prepararea blaturilor (se ştie preţul pe minut cerut de fiecare). Mai mult de atât, dacă este nevoit să prepare mai multe blaturi la rând, fiecare va cere un cost suplimentar pentru fiecare blat "extra":
De exemplu, dacă primul prepară 3 blaturi unul după altul, el va cere costul suplimentar de 2 ori (plus costul standard pentru fiecare blat).
 
S-a ajuns la concluzia că este nevoie de N blaturi pentru ziua concursului. Pentru fiecare se cunoaşte timpul de preparare. Cei doi au hotărât că primul va începe să prepare blaturile în ordinea $1, 2, ..., N$ iar cel de-al doilea în ordinea $N, N-1, ..., 1$.

h2. Date de intrare

Pe cea de-a treia linie se vor afla două numere naturale P1 şi S1 reprezentând preţul pe minut şi costul suplimentar cerut de primul coleg.
Pe ultima linie se vor afla două numere naturale P2 şi S2 reprezentând preţul pe minut şi costul suplimentar cerut de al doilea coleg.

h2. Date de ieşire

În fişierul de ieşire $blaturi.out$ se va scrie, pe prima linie, costul minim pentru a pregăti cele N blaturi iar pe a doua linie o secvenţă de N valori ‘1’ sau ‘2’. Dacă a i-a valoare este ‘1’ înseamnă că al i-lea blat a fost pregătit de primul coleg, respectiv de al doilea coleg dacă valoarea este ‘2’.

În fişierul de ieşire $blaturi.out$ se va scrie, pe prima linie, costul minim pentru a pregăti cele N blaturi.

h2. Restricţii
* $1 ≤ N ≤ 100.000$
* $1 ≤ P1, P2 ≤ 100$
* $1 ≤ S1, S2 ≤ 10.000$

* $1 ≤ timpul unui blat ≤ 100$
* $Se garantează că pentru 20% din teste 1 ≤ N ≤ 10$
* $Costul suplimentar este acelaşi indiferent de timpul de preparare al blatului.$
* $Este posibil ca un coleg să pregătească singur toate blaturile.$
* $Dacă există mai multe secvenţe care dau timpul minim, se va afişa cea mai mică din punct de vedere lexicografic.$

* $1 ≤$ timpul unui blat $≤ 100$
* Se garantează că pentru $20%$ din teste $1 ≤ N ≤ 10$
* Costul suplimentar este acelaşi indiferent de timpul de preparare al blatului.
* Este posibil ca un coleg să pregătească singur toate blaturile.

h2. Exemplu

1 2 3 4
2 1
3 3|23

1 1 1 1

|
h3. Explicaţie
Doar colegul 1 prepară cele 4 blaturi

Costul: (2*1) + (2*2 + 1) + (2*3 + 1) + (2*4 + 1)

Costul: $(2*1) + (2*2 + 1) + (2*3 + 1) + (2*4 + 1)$

== include(page="template/taskfooter" task_id="blaturi") ==