Raul: Pagină nouă: Arpsod are în curtea sa `N` copaci foarte bătrâni, așezați în linie și numerotați de la `1` la `N`. Fiecare copac are o înălțime cunoscută, `H_i`. Există riscul ca la un vânt mai puternic aceștia să cadă, provocând stricăciuni. Astfel Arpsod a angajat doi muncitori pentru a-i tăia copacii. Primul muncitor va începe să taie copacii în ordinea `1, 2, 3, ... ,N` iar cel de-al doilea în ordi...

2024-02-17T17:34:28Z

Pagină nouă: Arpsod are în curtea sa <code>N</code> copaci foarte bătrâni, așezați în linie și numerotați de la <code>1</code> la <code>N</code>. Fiecare copac are o înălțime cunoscută, <code>Hi</code>. Există riscul ca la un vânt mai puternic aceștia să cadă, provocând stricăciuni. Astfel Arpsod a angajat doi muncitori pentru a-i tăia copacii. Primul muncitor va începe să taie copacii în ordinea <code>1, 2, 3, ... ,N</code> iar cel de-al doilea în ordi...

New page

Arpsod are în curtea sa <code>N</code> copaci foarte bătrâni, așezați în linie și numerotați de la <code>1</code> la <code>N</code>. Fiecare copac are o înălțime cunoscută, <code>Hi</code>. Există riscul ca la un vânt mai puternic aceștia să cadă, provocând stricăciuni.

Astfel Arpsod a angajat doi muncitori pentru a-i tăia copacii. Primul muncitor va începe să taie copacii în ordinea <code>1, 2, 3, ... ,N</code> iar cel de-al doilea în ordinea <code>N, N-1, N-2, ... 1</code>.

Fiind un tărâm democratic, fiecare muncitor dorește să fie plătit pentru fiecare metru pe care îl taie. Muncitorul <code>1</code> are un tarif de <code>T1</code> pe metru iar muncitorul <code>2</code> un tarif de <code>T2</code> pe metru. Dacă un muncitor a început să taie un copac, acesta îl va tăia integral. Din motive de protecție a muncii, muncitorilor nu le este permis să lucreze simultan. De aici apare următoarea pretenție: dacă după tăierea unui copac, muncitorul nu este înlocuit de colegul său, acesta va cere un cost suplimentar <code>C</code> pentru a rămâne să taie în continuare.

De exemplu, dacă avem <code>3</code> copaci: <code>1, 2, 3</code> și muncitorul <code>1</code> taie singur toți copacii, acesta va cere un cost suplimentar de <code>2</code> ori (pentru copacul <code>2</code> și copacul <code>3</code>).

= Cerința =
Arpsod vă cere să determinați costul minim pe care îl poate plăti astfel încât toți cei <code>N</code> copaci să fie tăiați.

= Date de intrare =
Pe prima linie a fișierului <code>democratie.in</code> se va afla numărul natural <code>N</code>, reprezentând numărul de copaci.

Pe cea de-a doua linie vor exista <code>N</code> numere naturale nenule reprezentând înălțimile celor <code>N</code> copaci.

Pe cea de-a treia linie se vor afla două numere naturale <code>T1</code> și <code>T2</code> reprezentând tariful pe metru al muncitorului <code>1</code> respectiv al muncitorului <code>2</code>.

Pe ultima linie se vor afla două numere naturale <code>C1</code> și <code>C2</code> reprezentând costul suplimentar cerut de muncitorul <code>1</code> respectiv muncitorul <code>2</code>.

= Date de ieșire =
În fișierul <code>democratie.out</code> se va scrie, pe prima și singura linie din fișier, costul minim pe care Arpsod trebuie să-l plătească.

= Restricții și precizări =

* <code>1 ≤ N ≤ 100.000</code>
* <code>1 ≤ T1, T2 ≤ 100</code>
* <code>1 ≤ C1, C2 ≤ 10.000</code>
* <code>1 ≤ Hi ≤ 100</code>
* Se garantează că pentru <code>20%</code> din teste <code>1 ≤ N ≤ 10</code>
* Costul suplimentar este același indiferent de înălțimea copacului ce va fi tăiat.
* Este posibil ca un muncitor să taie singur toți copacii.
* Un muncitor va tăia complet un copac.
* Cam scumpă democrația asta!

= Exemplu: =
<code>democratie.in</code>
4
1 2 3 4
7 2
3 9
<code>democratie.out</code>
34

=== Explicație ===
Ordinea muncitorilor:

<code>M2 -> M1 -> M2 -> M2</code>

Costul: <code>(2*4) + (7*1) + (2*3) + (2*2 + 9)</code>

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

Nmax = 100002
inf = 2000000000

N, T1, T2, C1, C2 = 0, 0, 0, 0, 0
v = [0] * Nmax
Sol = inf
config = [0] * Nmax

def bkt(poz):
global N, T1, T2, C1, C2, Sol, v, config

if poz > N:
st, dr = 1, N
Total = 0

for i in range(1, N + 1):
if config[i] == 1:
Total += v[st] * T1
st += 1

if config[i - 1] == config[i]:
Total += C1
else:
Total += v[dr] * T2
dr -= 1

if config[i - 1] == config[i]:
Total += C2

Sol = min(Sol, Total)
return

for i in range(1, 3):
config[poz] = i
bkt(poz + 1)

def main():
global N, T1, T2, C1, C2, Sol, v, config

lines = sys.stdin.readlines()
N = int(lines[0])

v = list(map(int, lines[1].split()))

T1, T2, C1, C2 = map(int, lines[2].split())

bkt(1)

print(Sol)

if __name__ == "__main__":
main()
</syntaxhighlight>

1755 - Democratie - Revision history