Kostya və tapşırıqlar#11798

Şərt Müzakirə

Kostya və tapşırıqlar

1 saniyə

256 meqabayt

Çox asan

Kostya məşq fəaliyyətlərinin ardıcıllığını keçirir və hər biri bir tapşırığın həllindən ibarətdir.

Tutaq ki, $n$ — onun həll etdiyi tapşırıqların sayıdır. Hər tapşırığın nəticəsi var:

$1$ — düzgün həll,
$0$ — yanlış həll.

Nəticələrin ardıcıllığı a = (a_1, a_2, \dots, a_n) massivində verilmişdir, burada a_i \in \{0, 1\}.

Zəmanət verilir ki a_n = 1.

Hər həll üçün Kostya müəyyən sayda xal alacaq.

İlk olaraq Kostyanın hesabında $0$ xal var və həll üçün ilkin mükafat və ya cəza miqdarı s_1 = 1-dir. Hər $i$ üçün (1 \le i \le n) hesabdakı və s_i-dəki yenilənmə aşağıdakı qaydalara görə edilir:

Əgər a_i = 1, ümumi hesaba s_i əlavə olunur və növbəti tapşırıq üçün s_{i+1} = 1 təyin edilir.
Əgər a_i = 0, ümumi hesabdan s_i çıxılır və növbəti tapşırıq üçün s_{i+1} = 2 \cdot s_i təyin edilir.

Bütün $n$ məşqləri yerinə yetirdikdən sonra son xalları hesablamalısınız.

Giriş

Birinci sətrdə tam ədəd $n$ (1 \le n \le 10^5) — tapşırıqların sayı verilmişdir. İkinci sətir a_1, a_2, \dots, a_n (a_i \in \{0, 1\}) ədədini boşluqlarla ayrılmış halda verir.

Çıxış

Bütün $n$ məşqləri yerinə yetirdikdən sonra son xalları verin.

Nümunələr

Nümunə 1

Loading

Loading

Qeyd

Kostyanın hər addımda hesabının necə dəyişdiyini nəzərdən keçirək. Əvvəlcə onun hesabında $0$ xal var və həll üçün ilkin mükafat və ya cəza miqdarı s_1 = 1-dir. Sonra o ardıcıl olaraq tapşırıqları həll edir:

Birinci tapşırıq (a_1 = 1) — düzgün cavab:
- s_1 = 1 xalı əlavə edirik, hesab 0 + 1 = 1 olur.
- Tapşırıq düzgün həll edildiyindən s_2 = 1 təyin edirik.
İkinci tapşırıq (a_2 = 0) — yanlış cavab:
- s_2 = 1 xalı çıxırıq, hesab 1 - 1 = 0 olur.
- Cavab yanlış olduğundan, növbəti cəza miqdarı ikiqat artır: s_3 = 2 \cdot s_2 = 2.
Üçüncü tapşırıq (a_3 = 0) — yanlış cavab:
- s_3 = 2 xalını çıxırıq, hesab 0 - 2 = -2 olur.
- Cavab yanlış olduğundan, növbəti cəza miqdarı ikiqat artır: s_4 = 2 \cdot s_3 = 4.
Dördüncü tapşırıq (a_4 = 1) — düzgün cavab:
- s_4 = 4 xalı əlavə edirik, hesab -2 + 4 = 2 olur.
- Tapşırıq düzgün həll edildiyindən s_5 = 1 təyin edirik.
Beşinci tapşırıq (a_5 = 1) — düzgün cavab:
- s_5 = 1 xalı əlavə edirik, hesab 2 + 1 = 3 olur.
- Tapşırıqlar bitdi, beləliklə son hesab — 3 xalıdır.

a = (a_{1}, a_{2}, \dots, a_{n})

a_{i} \in {0, 1}

a_{n} = 1

s_{1} = 1

1 \leq i \leq n

s_{i}

a_{i} = 1

s_{i}

s_{i + 1} = 1

a_{1} = 1

s_{i}

s_{i + 1} = 2 \cdot s_{i}

1 \leq n \leq 1 0^{5}

a_{1}, a_{2}, \dots, a_{n}

a_{i} \in {0, 1}

s_{1} = 1

a_{1} = 1

s_{1} = 1

0 + 1 = 1

s_{2} = 1

a_{2} = 0

s_{2} = 1

1 - 1 = 0

s_{3} = 2 \cdot s_{2} = 2

a_{3} = 0

s_{3} = 2

0 - 2 = - 2

s_{4} = 2 \cdot s_{3} = 4

a_{4} = 1

s_{4} = 4

- 2 + 4 = 2

s_{5} = 1

a_{i} \in {0, 1}

s_{5} = 1

2 + 1 = 3