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

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

• 3 ≤ N ≤ 10000
• 2 ≤ R < N
• Rezultatul la cerința 2 poate avea cel mult 2400 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ă N=7 ouă. Secvențele roua de lungime 3 existente în colorare sunt "vrr", "rrg", "rgr", "grr".

Exemplu 2

Intrare

2

4 3

Ieșire

Datele de intrare corespund restricțiilor impuse.

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".

Exemplu 3

Intrare

2

3 5

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

#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)