Rezolvare PBinfo #2135

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ța

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 și precizări

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

Exemplul 1

roua.in

1
7 3
vrrrgrr

roua.out

4

Explicație

Cerinţa este 1. Există N=7 ouă. Secvențele roua de lungime 3 existente în colorare sunt "vrr", "rrg", "rgr", "grr".

Exemplul 2

roua.in

2
4 3

roua.out

15

Explicație

Cerinţa este 2. Există 4 ouă. Colorările 3-frumoase ale celor 4 ouă sunt "grrg", "grrv", "grra", "vrrg",
"vrrv", "vrra", "arrg", "arrv", "arra", "rgrr", "rvrr", "rarr", "rrgr", "rrvr", "rrar".