Diferente pentru problema/pwca intre reviziile #11 si #23

Diferente intre titluri:

PWCA
Problem With a Cool Acronym

Diferente intre continut:

!{margin: 10px}>problema/pwca?HotWings.png!
_Agent P., plictisit de interactive de geometrie si de algoritmi de cuplaj in O(N) cu rucsac random, a demisionat de la Organizatia Fara Acronim Cool si s-a apucat de compus Probleme Cu Acronim Cool._
_Agent P., plictisit de interactive de geometrie şi de algoritmi de cuplaj în $O(N)$ cu rucsac random, a demisionat de la Organizaţia Fără Acronim Cool şi s-a apucat de compus Probleme Cu Acronim Cool._
Doctorul Heinz Doofenshmirtz lucra la un nou inator, cand i s-a facut foame si s-a gandit sa comande prin _FoodPlatypus_ niste aripioare picante de pui. Aripioarele de pui pot fi de $2$ tipuri: $condimentate$ (codificate prin $1$) sau $necondimentate$ (codificate prin $0$). Comanda sa prin _FoodPlatypus_ are urmatoarele instructiuni:
Doctorul Heinz Doofenshmirtz lucra la un nou inator, când i s-a făcut foame şi s-a gândit să comande prin _FoodPlatypus_ nişte aripioare picante de pui. Aripioarele de pui pot fi de $2$ tipuri: $condimentate$ (codificate prin $1$) sau $necondimentate$ (codificate prin $0$). Comanda sa prin _FoodPlatypus_ are următoarele instrucţiuni:
_"Vreau sa primesc un sir de aripioare, impartit in_ <tex>N</tex> _secvente alternante. Astfel, prima secventa sa contina_ <tex>v_1_</tex> _aripioare $necondimentate$, a doua secventa sa contina_ <tex>v_2_</tex> _aripioare $condimentate$, a treia secventa sa contina_ <tex>v_3_</tex> _aripioare $necondimentate$ etc."_
_"Vreau să primesc un şir de aripioare, împărţit în $N$ secvenţe alternante. Astfel, prima secvenţă să conţină $V{~1~}$ aripioare $necondimentate$, a doua secvenţă să conţină $V{~2~}$ aripioare $condimentate$, a treia secvenţă să conţină $v{~3~}$ aripioare $necondimentate$ etc."_
Patronul firmei, renumitul bucatar 'Gordon Ramsay':problema/gordonramsay are acum un sir de aripioare de pui in fata lui, unele $condimentate$, altele nu. El defineste o $subsecventa picanta maximala$ ca fiind o subsecventa formata din aripioare de acelasi tip care nu se poate extinde la stanga sau la dreapta. La un pas, el poate schimba tipul unei $subsecvente picante maximale$ daca si numai aceasta are langa ea o alta $subsecventa picanta maximala$ de lungime mai mare sau egala ca ea. Fiind in secret pasionat de probleme de algoritmica, el se intreaba care este numarul total de configuratii initiale de aripioare pe care le poate avea astfel incat, aplicand operatia de mai sus de oricate ori vrea, sa poata obtina comanda finala a Doctorului Doofenshmirtz. Fiind insa prea ocupat cu prepararea comenzii si insultarea angajatilor lui, va intreaba pe voi care este acest numar, *modulo 998244353*.
Patronul firmei, renumitul bucătar 'Gordon Ramsay':problema/gordonramsay are acum un şir de aripioare de pui în faţa lui, unele $condimentate$, altele nu. El defineşte o $subsecvenţă picantă maximală$ ca fiind o subsecvenţă formată din aripioare de acelaşi tip care nu se poate extinde la stânga sau la dreapta. La un pas, el poate schimba tipul unei $subsecvenţe picante maximale$ dacă şi numai dacă aceasta are lângă ea o altă $subsecvenţă picantă maximală$ de lungime mai mare sau egală ca ea. Fiind în secret pasionat de probleme de algoritmică, el se întreabă care este numărul total de configuraţii iniţiale de aripioare pe care le poate avea astfel încât, aplicând operaţia de mai sus de oricâte ori vrea, să poată obţine comanda finală a Doctorului Doofenshmirtz. Fiind însă prea ocupat cu prepararea comenzii şi insultarea angajaţilor, vă întreabă pe voi care este acest număr, *modulo 998244353*.
h2. Date de intrare
Fişierul de intrare $pwca.in$ va contine pe prima linie numarul natural <tex>N</tex> reprezentand numarul de secvente. Urmatoarea linie va contine <tex>N</tex> numere <tex>v_1_, v_2_, ..., v_N_</tex> reprezentand comanda de aripioare a Doctorului Doofenshmirtz.
Fişierul de intrare $pwca.in$ va conţine pe prima linie numărul natural $N$ reprezentând numărul de secvenţe. Următoarea linie va conţine $N$ numere $V{~1~}, V{~2~}, ..., V{~N~}$ reprezentând comanda de aripioare a Doctorului Doofenshmirtz.
h2. Date de ieşire
În fişierul de ieşire $pwca.out$ se va afisa numarul de configuratii initiale cautat, *modulo 998244353*.
În fişierul de ieşire $pwca.out$ se va afişa numărul de configuraţii iniţiale căutat, *modulo 998244353*.
h2. Restricţii
 
* <tex>1 \leq N \leq 10^5</tex>
* <tex>1 \leq v_{i} \leq 200</tex>
h2. $Subtask 1 (10 puncte)$
 
* <tex>N = 1</tex>
 
h2. $Subtask 2 (15 puncte)$
h3. $Subtask 1 (10 puncte)$
* <tex>\sum_{i = 1}^{n} v_i \leq 20</tex>
* <tex>\sum_{i = 1}^{n} v_i \leq 15 </tex>
h2. $Subtask 3 (20 de puncte)$
h3. $Subtask 2 (20 puncte)$
* <tex>N \leq 10</tex>
* <tex>v_i \leq 15 </tex>
h2. $Subtask 4 (25 de puncte)$
h3. $Subtask 3 (30 de puncte)$
* <tex>v_i \leq 10</tex>
* <tex> N = 1 </tex>
h2. $Subtask 5 (30 de puncte)$
h3. $Subtask 4 (40 de puncte)$
* $Fara restrictii suplimentare.$
* $Fără restricţii suplimentare.$
h2. Exemplu
2 3 1
| 4
|
| 1
15
| 30626
|
h2. Explicaţie
h3. Exemplul 1
Configuratia din exemplu o reprezinta sirul de biti <tex>000</tex>. Acesta poate fi obtinut din urmatoarele configuratii:
Configuraţia din exemplu o reprezintă şirul de biti $000$. Acesta poate fi obţinut din următoarele configuraţii:
* <tex>000</tex>
* <tex>111 \rightarrow 000</tex>
* <tex>100\rightarrow 000</tex>
* <tex>010\rightarrow 000</tex>
* <tex>001\rightarrow 000</tex>
* $000$
* $100$ &#8594; $000$
* $010$ &#8594; $000$
* $001$ &#8594; $000$
* $101$ &#8594; $100$ &#8594; $000$
h3. Exemplul 2
Configuratia din exemplu o reprezinta sirul de biti <tex>001110</tex>. Acesta poate fi obtinut din urmatoarele configuratii:
Configuraţia din exemplu o reprezintă şirul de biti $001110$. Acesta poate fi obţinut din următoarele configuraţii:
* <tex>001110</tex>
* <tex>101110\rightarrow 001110</tex>
* <tex>001010\rightarrow 001110</tex>
* <tex>101010\rightarrow 001010\rightarrow 001110</tex>
* $001110$
* $101110$ &#8594; $001110$
* $001010$ &#8594; $001110$
* $101010$ &#8594; $001010$ &#8594; $001110$
== include(page="template/taskfooter" task_id="pwca") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.