Fișierul intrare/ieșire roua.in, roua.out Sursă ONI 2017 clasa a 5-a
Autor Cerasela-Daniela Cardaș Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.5 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip full
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in roua.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii