ŠIOM — Vidurkių seka

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: mean.in

Rezultatų failas: mean.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Vidurkių seka

Nagrinėkime nemažėjačią seką $s_1,\\dots,s_{n+1}$ ( $s_i\\les_{i+1}$ kiekvienam i, $1\\lei\\len$ ). Šios sekos vidurkių seka vadinama seka $m_1,\\dots,m_n$ , apibrėžta tokiu būdu: $m_i=(s_i+s_{i+1})/2$ kiekvienam i, $1\\lei\\len$ . Pavyzdžiui, sekos 1, 2, 2, 4 vidurkių seka lygi 1.5, 2, 3. Vidurkių sekos elementai gali būti trupmenos, tačiau šiame uždavinyje nagrinėjamos tik tokios vidurkių sekos, kurias sudaro sveikieji skaičiai.

Duota nemažėjanti vidurkių seka iš n sveikųjų skaičių: $m_1,\\dots,m_n$ . Reikia suskaičiuoti, kiek gali būti nemažėjančių sekų $s_1,\\dots,s_{n+1}$ (sudarytų iš $n+1$ sveikųjų skaičių), kurių vidurkių sekos lygios duotajai $m_1,\\dots,m_n$ .

Pradiniai duomenys

Pirmoje eilutėje įrašytas vienas sveikasis skaičius n ( $2\\len\\le5~000~000$ ). Tolesnėse n eilučių įrašyta seka $m_1,\\dots,m_n$ . ( $i+1$ )-oje eilutėje įrašytas vienas sveikasis skaičius $m_i$ ( $0\\lem_i\\le10^9$ ).

Rezultatai

Programa turi išvesti vieną sveikąjį skaičių – kiek rasta nemažėjančių sekų, kurių vidurkių sekos lygios duotajai.

Pavyzdys

Duomenys	Rezultatai
3 2 5 9	4

Šeštadieninė informatikos olimpiadininkų mokykla

Vidurkių seka

Pradiniai duomenys

Rezultatai

Pavyzdys