Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2016-07-13 09:21:15.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:superbec.in, superbec.outSursăJunior Challenge 2016
AutorAlexandru PetrescuAdăugată deJuniorChallenge2015JuniorChallenge2016 JuniorChallenge2015
Timp execuţie pe test0.4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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:

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

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).

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.

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.

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<=1.000.000.000
  • N<=10.000
  • T<=100
  • pentru 75% din punctaj, N*T<=1.000

Exemplu

superbec.insuperbec.out
2
10 5
0120122101
7 3
?????0?
0
0

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?