Diferente pentru problema/superbec intre reviziile #12 si #42

Diferente intre titluri:

superbec
Superbec

Diferente intre continut:

== include(page="template/taskheader" task_id="superbec") ==
Marcel are N becuri, numerotate de la 1 la N, care pot lumina puternic, pot lumina slab sau pot sa nu lumineze deloc. Pentru a schimba straile becurilor, el poate apasa de cate ori vrea pe oricare dintre urmatoarele butoane:
Marcel are $N$ becuri, numerotate de la $1$ la $N$, care pot lumina puternic, pot lumina slab sau pot sa nu lumineze deloc. Pentru a schimba straile becurilor, el poate apasa de cate ori vrea pe oricare dintre urmatoarele butoane:
1. butonul A, care modifica starea tuturor becurilor.
2. butonul B, care modifica starea becurilor cu indice par.
3. butonul C, care modifica starea becurilor cu indice impar.
4. butonul D, care modifica starea becurilor cu indice de forma 3K+1, K numar natural
5. butonul E, care modifica starea becurilor cu indice de forma 3K+2, K numar natural
6. butonul F, care modifica starea becurilor cu indice de forma 5K, K numar natural
7. butonul G, care modifica starea becurilor cu indice de forma 5K+2, K numar natural
8. butonul H, care modifica starea becurilor cu indice de forma 5K+3, K numar natural
9. butonul I, care modifica starea becurilor cu indice de forma 5K+4, K numar natural
# Butonul $A$, care modifica starea tuturor becurilor.
# Butonul $B$, care modifica starea becurilor cu indice par.
# Butonul $C$, care modifica starea becurilor cu indice impar.
# Butonul $D$, care modifica starea becurilor cu indice de forma <tex> 3 \cdot K + 1 </tex>, <tex> K </tex> numar natural
# Butonul $E$, care modifica starea becurilor cu indice de forma <tex> 3 \cdot K + 2 </tex>, <tex> K </tex> numar natural
# Butonul $F$, care modifica starea becurilor cu indice de forma <tex> 5 \cdot K </tex>, <tex> K </tex> numar natural
# Butonul $G$, care modifica starea becurilor cu indice de forma <tex> 5 \cdot K + 2 </tex>, <tex> K </tex> numar natural
# Butonul $H$, care modifica starea becurilor cu indice de forma <tex> 5 \cdot K + 3 </tex>, <tex> K </tex> numar natural
# Butonul $I$, care modifica starea becurilor cu indice de forma <tex> 5 \cdot K + 4 </tex>, <tex> K </tex> numar natural
Modificarea starii unui buton se realizeaza in felul urmator: daca becul era stins, el urmeaza sa lumineze slab; daca lumina slab, urmeaza sa lumineze puternic; daca lumina puternic, urmeaza sa nu mai lumineze deloc.
Initial toate becurile sunt stinse. Marcel apasa de M ori butoane aleatoare, iar la final isi noteaza starea fiecarui bec. El se intreaba care este numarul de moduri de a obtine starea respectiva, tot din M mutari, considerand ca starea initiala este aceeasi (toate becurile sunt stinse). Ordinea apasarii butoanelor nu conteaza (ABA se considera aceeasi secventa de mutari cu AAB).
Initial toate becurile sunt stinse. Marcel apasa de $M$ ori butoane aleatoare, iar la final isi noteaza starea fiecarui bec. El se intreaba care este numarul de moduri de a obtine starea respectiva, tot din $M$ mutari, considerand ca starea initiala este aceeasi (toate becurile sunt stinse). Ordinea apasarii butoanelor nu conteaza ({$ABA$} se considera aceeasi secventa de mutari cu {$AAB$}).
h2. Date de intrare
Fişierul de intrare $superbec.in$ va contine pe prima linie numarul T de teste. Structura fiecarui test este descrisa mai jos:
Pe prima linie se vor afla numerele N si M, iar pe urmatoarea linie, N caractere egale fie cu '0' (bec stins), fie cu '1' (bec care lumineaza slab), fie cu '2' (bec care lumineaza puternic), fie cu caracterul '?' (bec a carui stare ii este necunoscuta pana si lui Marcel), reprezentand starea finala a becurilor.
Fişierul de intrare $superbec.in$ va contine pe prima linie numarul $T$ de teste. Structura fiecarui test este descrisa mai jos:
Pe prima linie se vor afla numerele $N$ si $M$, iar pe urmatoarea linie, $N$ caractere egale fie cu $0$ (bec stins), fie cu $1$ (bec care lumineaza slab), fie cu $2$ (bec care lumineaza puternic), fie cu caracterul $?$ (bec a carui stare ii este necunoscuta pana si lui Marcel), fie $a$ (din amintirile lui Marcel - bec a carui stare poate fi $0$ sau $1$), fie $b$ (bec a carui stare poate fi $1$ sau $2$), reprezentand starea finala a becurilor.
h2. Date de ieşire
În fişierul de ieşire $superbec.out$ se vor gasi T linii, fiecare dand raspunsul la cate un test, raspunsul fiind un singur numar, reprezentand restul la impartirea cu 1.000.000.007 a numarului de moduri de a apasa de M ori butoanele si de a obtine sirul dat in input, la testul respectiv.
În fişierul de ieşire $superbec.out$ se vor gasi $T$ linii, fiecare dand raspunsul la cate un test, raspunsul fiind un singur numar, reprezentand restul la impartirea cu <tex> 10^9 + 7 </tex> a numarului de moduri de a apasa de $M$ ori butoanele si de a obtine sirul dat in input, la testul respectiv.
h2. Restricţii si precizari
* Un mod de a apasa de M ori butoanele se considera ca obtine sirul dat in input daca exista o modalitate de a asocia fiecarui caracter '?' din input unul dintre caracterele '0', '1' sau '2' astfel incat codificarea sirului de becuri din input sa fie identica cu codificarea sirului de becuri asa cum arata ele dupa cele M apasari de butoane
* M &le; 1.000.000.000
* N &le; 10.000
* T &le; 100
* **Subtask 1 (20 puncte)**: T, N, M &le; 10
* **Subtask 2 (30 puncte)**: suma celor T numere N nu va depasi 1.000 si M &le; 200.000
* **Subtask 3 (20 puncte)**: suma celor T numere N nu va depasi 1.000
* Un mod de a apasa de $M$ ori butoanele se considera ca obtine sirul dat in input daca exista o modalitate de a asocia fiecarui caracter $?$ din input unul dintre caracterele $0$, $1$ sau $2$, fiecarui caracter $a$ $0$ sau $1$ si fiecarui caracter $b$ $1$ sau $2$ astfel incat codificarea sirului de becuri din input sa fie identica cu codificarea sirului de becuri asa cum arata ele dupa cele $M$ apasari de butoane.
 
* $1 &le; M &le; 1.000.000.000$
* $1 &le; N &le; 100.000$
* $1 &le; T &le; 100$
 
* **Subtask 1 (20 puncte)**: $1 &le; T, N, M &le; 10$
* **Subtask 2 (30 puncte)**: suma celor $T$ numere $N$ nu va depasi $10.000$ si $1 &le; M &le; 200.000$
* **Subtask 3 (20 puncte)**: suma celor $T$ numere $N$ nu va depasi $10.000$
* **Subtask 4 (30 puncte)**: restrictiile initiale
* pentru 20% din teste se garanteaza ca T &le; 10 si M &le; 10
* pentru 70% din teste se granteaza ca suma celor T numere N nu va depasi 1.000
h2. Exemplu
5 1
01010
6 3
0?1?0?
0a1?0?
10 5
01?02??10?
01?02b?10?
7 3
?????0?
b?a??0?
15 20
?22??222?????10
?22??222?a?bb10
20 56
?2?02??22??2???1??1?
?a?02ab22?b2?a?1?a1?
27 21
0?20?02??2122??21?0????10??
0?20?02??2122a?21?0?a?a10??
27 16
0?20?02??2122??21?0????10??
0?1a?0a0?a1a1?a?12a?aa?a0?a
30 10
??????????????????????1??????1
???????a???a?????b????1???b??1
40 100
2??2??1???1??1??0??2?????2?????1???2?0??
2??2??1???1??1??0??2??b?b2?????1???2?0??
| 1
6
10
88
2277
735471
3
1
36
1287
0
0
0
5006
1109
48903492
|
h3. Explicaţie
Primul test: singurul mod valid de a apasa butonul este: B
Al doilea test: cele 6 moduri valide de a apasa butoanele sunt: BBH, BGH, BHI, GGH, GHI, HII
Celelalte teste: Credeti comisia pe cuvant
Primul test: singurul mod valid de a apasa butonul este: $B$
Al doilea test: cele $3$ moduri valide de a apasa butoanele sunt: $BHI$, $GHI$, $HII$
Al treilea test: singurul mod valid de a apasa butoanele este: $BCCDI$
Celelalte teste: Credeti comisia pe cuvant!
== include(page="template/taskfooter" task_id="superbec") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.