Fişierul intrare/ieşire:roua.in, roua.outSursăONI 2017 clasa a 5-a
AutorCerasela-Daniela CardasAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.5 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

roua.inroua.outExplicaţii
1
7 3
vrrrgrr
4
Explicaţii
Cerinţa este 1. Există N=7 ouă. Secvenţele roua de lungime 3 existente în
colorare sunt "vrr", "rrg", "rgr", "grr".
2
4 3
15
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".
Trebuie sa te autentifici pentru a trimite solutii. Click aici