# PBinfo #2135 – Roua – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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ă:


numărul de secvențe “roua” de lungime R existente în colorarea celor N ouă;
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".

## Cod sursă C++

```cpp
//Cardas Daniela
#include <fstream>
using namespace std;
ifstream in("roua.in");
ofstream out("roua.out");
int N,P,R,i,nroua,p1,p2,a,b,v[2500],x,p,j,ct;
char c;
int main()
{
    in>>P;
    if(P==1)
    {
        in>>N>>R>>c;i=1;
        while(c=='r'&&i<N)in>>c,i++;
        if(c!='r'){p2=i;if(p2>=R)nroua=1;}
        if(c=='r'&&i==N){out<<0<<'\n';return 0;}
        for(i=p2+1; i<=N; i++)
        {
            in>>c;
            if(c!='r')
            {
                if(i-p2+1>R){nroua++;}
                p1=p2;p2=i;
            }
            else
            if(p1<=i-R&&i>=R&&p2>i-R){nroua++;}
        }
        out<<nroua<<'\n';
    }
    else
    {
        ///P=2
        in>>N>>R;
        a=N%R;b=N/R;
        if(N<=70)
        {
            long long p=1;
            for(i=1;i<=b;i++,p*=3);
            p=p*(2*a+R);
            out<<p<<'\n';
            return 0;
        }
        ///initializam vectorul de cifre cu numarul 2a+R
        x=2*a+R;i=0;
        while(x)v[++i]=x%10,x/=10;
        v[0]=i;
        ///inmultim vectorul de cifre v cu 3 de b ori
        for(i=1;i<=b;i++)
        {
            for(ct=0,j=1;j<=v[0];j++)
            {
                v[j]*=3;
                x=v[j]+ct;v[j]=x%10;ct=x/10;
            }
            if(ct)
            {
                v[0]++;v[v[0]]=ct;
            }
        }
        for(i=v[0];i>=1;i--)
            out<<v[i];
        out<<'\n';
    }
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2135)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2135/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2135/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)