Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | colors.in, colors.out | Sursă | ProSoft@NT 2017 |
| Autor | Cristina Sichim | Adăugată de |  Valentin Rosca •valiro21 |
| Timp execuţie pe test | 0.6 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Colors
Mara a primit in dar un nou set de acuarele. Spre surprinderea ei, a observat că, atunci când se combină culorile G şi V se obţine un rezultat neobişnuit. A încercat toate combinaţiile posibile şi a observat că:
- dacă toarnă V peste V obţine G;
- dacă toarnă G peste G obţine V;
- dacă toarnă G peste V obţine V;
- dacă toarnă V peste G obţine G.
Curioasă, Mara, făcut următorul experiment: a pus în n cutii alăturate, la întâmplare, doar culorile V şi G şi a început să le amestece. Ca să nu se murdărească, varsă întotdeauna o cutie peste cea mai apropiată cutie care nu este goala, aflată în stânga ei. Experimentul se încheie atunci când toată vopseaua s-a adunat în prima cutie din stânga. Fiecare modalitate de a aduna toată vopseaua în prima cutie din stânga poate fi caracterizată de n-1 operaţii de forma [i,j], cu 1≤i≤j≤n, cu semnificaţia: cutia j a fost turnată în cutia i. Două modalităţi sunt considerate identice dacă folosesc aceleaşi operaţii chiar dacă acestea nu au fost efectuate în aceeaşi ordine.
De exemplu, dacă în 4 cutii avem culorile: VVGV, şirul operaţiilor [1,2][3,4][1,3] indică succesiunea operaţiilor: toarnă cutia 2 peste cutia 1 (cutia 2 devine goală), apoi cutia 4 peste cutia 3 (cutia 4 devine goală) şi la final cutia 3 peste cutia 1. Această modalitate este identică cu cea definită de şirul operaţiilor [3,4][1,2][1,3]. .
Cerinţe
Cunoscând numărul n, şi cele n culori aflate în cutii, să se determine numărul modalităţilor în care Mara poate
combina culorile din cele n cutii pentru a obţine, în final, culoarea V, modulo 666013.
Date de intrare
Fişierul de intrare colors.in conţine pe prima linie numărul natural n şi pe linia a doua un şir de n litere din mulţimea {'V', 'G'} neseparate prin spaţiu (reprezentând, în ordine, culorile aflate în cele n cutii).
Date de ieşire
În fişierul de ieşire colors.out va conţine pe prima linie o valoarea naturală reprezentând numărul modalităţilor în care Mara poate combina culorile din cele n cutii pentru a obţine, în final, culoarea V, modulo 666013.
Restricţii
- 1 ≤ n ≤ 1000000
Exemplu
| colors.in | colors.out |
|---|---|
| 4 VVGV | 2 |
Explicaţie
Sunt 6 variante de combinare a culorilor din cele 4 cutii, definite de şirurile:
- [1,2][1,3][1,4] pentru VVGV → G-GV → V--V → G---
- [1,2][3,4][1,3] pentru VVGV → G-GV → G-G- → V---
- [2,3][1,2][1,4] pentru VVGV → VV-V →G--V → G---
- [2,3][2,4][1,2] pentru VVGV → VV-V → VG-- → V---
- [3,4][1,2][1,3] pentru VVGV → VVG- → G-G- → V---
- [3,4][2,3][1,2] pentru VVGV → VVG- → VV-- → G---
Se observa ca variantele 2. si 5. efectueaza aceleasi operatii in alta ordine deci nu se considera variante distincte.
Avem 5 variante distincte de combinare a culorilor: 1. 2. 3. 4. si 6. Pentru doua dintre aceste variante ( 2. si 4. ) se obtine in final culoarea V.
Raspunsul este 2.
