Editing 2135 - Roua

==Cerinț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: <code>'r'</code> pentru culoarea roșie, <code>'g'</code> pentru galben, <code>'v'</code> pentru verde, <code>'a'</code> pentru albastru. Pentru a vopsi ouăle, le așază în rând, unul după altul. Astfel, o colorare va fi o succesiune de <code>N</code> caractere din mulţimea <code>{'r' , 'g' , 'v','a'}</code>, reprezentând, în ordinea aşezării, culorile celor <code>N</code> ouă.

Numim “roua” o secvență de <code>R</code> caractere cu proprietatea că dintre acestea exact <code>R-1</code> caractere reprezintă culoarea roșie, iar un caracter reprezintă una dintre celelalte <code>3</code> culori. De exemplu secvenţele roua de lungime <code>3</code> sunt <code>"grr"</code>, <code>"rgr"</code>, <code>"rrg"</code>, <code>"vrr"</code>, <code>"rvr"</code>, <code>"rrv"</code>, <code>"arr"</code>, <code>"rar"</code>, <code>"rra"</code> .

Copilul consideră că o colorare este R-frumoasă, dacă oricare <code>R</code> caractere consecutive din colorare formează o secvență roua. De exemplu, pentru <code>N=11</code> ouă, şirul <code>"arrrvrrrarr"</code> reprezintă o colorare 4-frumoasă.
Cunoscând <code>N</code>, numărul de ouă vopsite, și numărul natural <code>R</code>, scrieți un program care determină și afișează:

# numărul de secvențe “roua” de lungime <code>R</code> existente în colorarea celor <code>N</code> ouă;
# numărul total al colorărilor <code>R</code>-frumoase pentru cele <code>N</code> ouă.

==Date de intrare==
Fișierul de intrare <code>roua.in</code> conține pe prima linie un număr natural <code>C</code> reprezentând cerința din problemă care trebuie rezolvată (<code>1</code> sau <code>2</code>). A doua linie din fișier conține numerele naturale <code>N</code> și <code>R</code>, separate prin spaţiu, reprezentând numărul de ouă și lungimea unei secvențe “roua”. Dacă <code>C=1</code>, fișierul va conţine şi o a treia linie pe care se află colorarea celor <code>N</code> ouă.
==Date de ieșire==
Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

Pe următorul rând se va afișa un număr natural, reprezentând răspunsul la cerinţa specificată în fişierul de intrare

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

==Restricții și precizări==

* <code>3 ≤ N ≤ 10000</code>
* <code>2 ≤ R < N</code>
* Rezultatul la cerința 2 poate avea cel mult <code>2400</code> de cifre.

==Exemplu 1==
;Intrare
:1
:7 3
:vrrrgrr
;Ieșire
:Datele de intrare corespund restricțiilor impuse.
:4

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

==Exemplu 2==
;Intrare
:2
:4 3
;Ieșire
:Datele de intrare corespund restricțiilor impuse.
:15

===Explicație===
Cerinţa este 2. Există <code>4</code> ouă. Colorările <code>3</code>-frumoase ale celor <code>4</code> ouă sunt <code>"grrg"</code>, <code>"grrv"</code>, <code>"grra"</code>, <code>"vrrg"</code>,

<code>"vrrv"</code>, <code>"vrra"</code>, <code>"arrg"</code>, <code>"arrv"</code>, <code>"arra"</code>, <code>"rgrr"</code>, <code>"rvrr"</code>, <code>"rarr"</code>, <code>"rrgr"</code>, <code>"rrvr"</code>, <code>"rrar"</code>.

==Exemplu 3==
;Intrare
:2
:3 5
;Ieșire
:Datele de intrare nu corespund restricțiilor impuse.

==Rezolvare==
<syntaxhighlight lang="python" line="1">
#2135 Roua


def conditii(n, r, colorare=None):
    restrictii = (
        3 <= n <= 10_000,
        2 <= r < n,
        len(colorare) == n if colorare else True
    )

    return all(restrictii)


def nr_secvente_roua(colorare, r):
    nr = 0
    # Secționăm treptat șirul 'colorare' (colorare[0:r], colorare[1:r], colorare[2:r] ...)
    for i in range(len(colorare)-r+1):
        secventa = colorare[i:i+r]
        # Dacă secvența conține exact r-1 litere 'r'...
        if secventa.count("r") == r-1:
            # ... înseamnă că avem o secvență "rouă"
            nr += 1

    return nr


def nr_colorari_r_frumoase(nr_oua, lungime_secventa_roua):
    # Numărul de subsecvențe complete (succesiuni de "r")
    modulo = nr_oua % lungime_secventa_roua
    # Elementele rămase (diferite de "r")
    cat = nr_oua / lungime_secventa_roua

    # Cu excepția culorii "r", există alte 3 culori: "g", "v", "a"
    produs = (cat*3) * (modulo+lungime_secventa_roua)

    return int(produs) - 1


def roua(c, nr_oua, lungime_secventa_roua,  colorare=None):
    # c este numărul cerinței
    if c == 1:
        print(nr_secvente_roua(colorare, lungime_secventa_roua))
    elif c == 2:
        print(nr_colorari_r_frumoase(nr_oua, lungime_secventa_roua))


if __name__ == '__main__':
    c = int(input())
    nr_oua, lungime_secventa_roua = [int(x) for x in input().split()]
    colorare = None
    if c == 1:
        colorare = input()

    if not conditii(nr_oua, lungime_secventa_roua, colorare):
        print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        print("Datele de intrare corespund restricțiilor impuse.")
        roua(c, nr_oua, lungime_secventa_roua, colorare)

</syntaxhighlight>