Pls Traian intră în concurs | roua

This was the problem page during the contest. Access the current page here.
Time limit: 0.08s Memory limit: 2MB Input: roua.in Output: roua.out

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 NN caractere din mulţimea {r, g, v, a}, reprezentând, în ordinea aşezării, culorile celor NN ouă.
Numim “roua” o secvență de RR caractere cu proprietatea că dintre acestea exact R1R-1 caractere reprezintă culoarea roșie, iar un caracter reprezintă una dintre celelalte 33 culori. De exemplu secvenţele roua de lungime 33 sunt grr, rgr, rrg, vrr, rvr, rrv, arr, rar, rra. Copilul consideră că o colorare este RR-frumoasă, dacă oricare RR caractere consecutive din colorare formează o secvență roua. De exemplu, pentru N=11N = 11 ouă, şirul arrrvrrrarr reprezintă o colorare 44-frumoasă.

Cerințe

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

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

Date de intrare

Fișierul de intrare roua.in conține pe prima linie un număr natural CC reprezentând cerința din problemă care trebuie rezolvată (11 sau 22). A doua linie din fișier conține numerele naturale NN și RR, separate prin spaţiu, reprezentând numărul de ouă și lungimea unei secvențe “roua”. Dacă C=1C = 1, fișierul va conţine şi o a treia linie pe care se află colorarea celor NN 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

  • 3N10 0003 ≤ N ≤ 10 \ 000
  • 2R<N2 ≤ R < N
  • Pentru rezolvarea corectă a cerinței 11 se acordă 4040 de puncte
  • Pentru rezolvarea corectă a cerinței 22 se acordă 6060 de puncte
  • Pentru 6060% dintre testele pentru cerința 22, 3N703 ≤ N ≤ 70
  • Pentru 4040% dintre testele pentru cerința 22, N>70N > 70
  • Rezultatul la cerința 22 poate avea cel mult 2 4002 \ 400 de cifre.

Exemplul 1

roua.in

1
7 3
vrrrgrr

roua.out

4

Explicație

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

Exemplul 2

roua.in

2
4 3

roua.out

4
15

Explicație

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

Log in or sign up to be able to send submissions!