Fișierul intrare/ieșire	roua.in, roua.out	Sursă	ONI 2017 clasa a 5-a
Autor	Cerasela-Daniela Cardaș	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.5 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Roua (clasa a 5-a)

Un copil dorește să vopsească ouăle de Paște, având la dispoziție vopsele de culoare roșie, galbenă, verde și albastră. Fiecare culoare va fi reprezentată printr-un singur caracter astfel: ‘r’ pentru culoarea roșie, ‘g’ pentru galben, ‘v’ pentru verde, ‘a’ pentru albastru. Pentru a vopsi ouăle, le așază în rând, unul după altul. Astfel, o colorare va fi o succesiune de N caractere din mulțimea {‘r’,‘g’,‘v’,‘a’}, reprezentând, în ordinea așezării, culorile celor N ouă.

Numim “roua” o secvență de R caractere cu proprietatea că dintre acestea exact R-1 caractere reprezintă culoarea roșie, iar un caracter reprezintă una dintre celelalte 3 culori. De exemplu secvențele roua de lungime 3 sunt “grr”, “rgr”, “rrg”, “vrr”, “rvr”, “rrv”,” arr “, “rar”, “rra”.

Copilul consideră că o colorare este R-frumoasă, dacă oricare R caractere consecutive din colorare formează o secvență roua. De exemplu, pentru N=11 ouă, șirul “ arrrvrrrarr” reprezintă o colorare 4-frumoasă.

Cerințe

Cunoscând N, numărul de ouă vopsite, și numărul natural R, scrieți un program care determină și afișează:

1. numărul de secvențe “roua” de lungime R existente în colorarea celor N ouă;
2. numărul total al colorărilor R-frumoase pentru cele N ouă.

Date de intrare

Fișierul de intrare roua.in conține pe prima linie un număr natural C reprezentând cerința din problemă care trebuie rezolvată (1 sau 2). A doua linie din fișier conține numerele naturale N și R, separate prin spațiu, reprezentând numărul de ouă și lungimea unei secvențe “roua”. Dacă C=1, fișierul va conține și o a treia linie pe care se află colorarea celor N ouă.

Date de ieșire

Fișierul de ieșire roua.out va conține o singură linie pe care va fi scris un număr natural, reprezentând răspunsul la cerința specificată în fișierul de intrare.

Restricții

• 3 ≤ N ≤ 10000
• 2 ≤ R < N
• Pentru rezolvarea corectă a cerinței 1 se acordă 40 puncte, pentru rezolvarea corectă a cerinței 2 se acordă 60 de puncte.
• Pentru 60% dintre testele pentru cerința 2, 3 ≤ N ≤ 70
• Pentru 40% dintre testele pentru cerința 2, N > 70
• Rezultatul la cerința 2 poate avea cel mult 2400 de cifre.

Exemplu