| Fişierul intrare/ieşire: | cameleoni.in, cameleoni.out | Sursă | Prosoft@NT 2016 |
| Autor | Adrian Panaete | Adăugată de |  Paul Diac •diac_paul |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cameleoni
Cameleonii zeylanicus sunt renumiţi pentru comportamentul lor. Dacă se atinge un astfel de cameleon, atunci el îşi schimbă culoarea din roşu în verde sau din verde în roşu.
De ziua ei, Cami a primit cadou patru astfel de cameleoni. Pentru a le studia comportamentul, i-a aliniat pe o masă şi a observat că, la început, toţi sunt roşii. A început să-i atingă, la întâmplare.
După n atingeri, Cami s-a uitat la culorile cameleonilor şi şi-a pus următoarea întrebare: în câte moduri aş fi putut atinge cameleonii pentru a ajunge în acestă stare?
Cerinta
Să se scrie un program care, pentru un număr cunoscut de atingeri, n, şi o stare a celor patru cameleoni, determină numărul modalităţilor (modulo 666013) în care se poate ajunge în acea stare după exact n atingeri.
Date de intrare
Fişierul de intrare cameleoni.in conţine pe prima linie numărul n de atingeri şi pe a doua linie patru litere, separate prin spaţiu, ce codifică culorile celor patru cameleoni, de la stânga la dreapta, după n atingeri.
Date de ieşire
În fişierul de ieşire cameleoni.out va conţine pe prima linie numarul modalităţilor (modulo 666013) în care se poate ajunge în starea dată, după exact n atingeri.
Restricţii
- 1 <= n <= 2000000000 (2 * 109)
- Culorile sunt codificate prin R pentru roşu/red şi G pentru verde/green
- Configuraţia iniţială a cameleonilor este R R R R
Exemplu
| cameleoni.in | cameleoni.out | Explicatie |
|---|---|---|
| 2 R R R R | 4 | Sunt patru modalitaţi prin care se ajunge la starea dată: 1) R R R R -> G R R R ->R R R R 2) R R R R -> R G R R ->R R R R 3) R R R R -> R R G R ->R R R R 4) R R R R -> R R R G ->R R R R |
| 2 G R R G | 2 | Sunt două modalitaţi: 1) R R R R -> G R R R -> G R R G 2) R R R R -> R R R G -> G R R G |
