Fişierul intrare/ieşire:colors.in, colors.outSursă[email protected] 2017
AutorCristina SichimAdăugată devaliro21FII Valentin Rosca valiro21
Timp execuţie pe test1.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.incolors.out
4
VVGV
2

Explicaţie

Sunt 6 variante de combinare a culorilor din cele 4 cutii, definite de şirurile:

  1. [1,2][1,3][1,4] pentru VVGV → G-GV → V--V → G---
  2. [1,2][3,4][1,3] pentru VVGV → G-GV → G-G- → V---
  3. [2,3][1,2][1,4] pentru VVGV → VV-V →G--V → G---
  4. [2,3][2,4][1,2] pentru VVGV → VV-V → VG-- → V---
  5. [3,4][1,2][1,3] pentru VVGV VVG- → G-G- → V---
  6. [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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?