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

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
• Rezultatul la cerința 2 poate avea cel mult 2400 de cifre.

Exemplu 1

Intrare

1

7 3

vrrrgrr

Ieșire

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

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

Date de intrare gresite!

Rezolvare

<syntaxhighlight lang="python" line="1">

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
   for i in range(len(colorare)-r+1):
       secventa = colorare[i:i+r]
       if secventa.count("r") == r-1:
           nr += 1

   return nr

def nr_colorari_r_frumoase(n, r):

   a = n % r
   b = n / r

   p = b*3
   p = p*(a+r)

   return int(p)-1

def main():

   c = int(input())
   n, r = [int(x) for x in input().split()]
   colorare = None
   if c == 1:
       colorare = input()

   if not conditii(n, r, colorare):
       return print("Date de intrare gresite!")

   if c == 1:
       print(nr_secvente_roua(colorare, r))
   elif c == 2:
       print(nr_colorari_r_frumoase(n, r))

if __name__ == '__main__':

   main()

</syntaxhighlight>