Editing 3823 - A - Flipped Cards

== Cerinţa ==
După ce Le Quack și-a pierdut toți banii dați de mama lui să cumpere pâine la Blackjack, acesta a decis să își creeze propriul joc de cărți unde își poate bate prietenii și să câștige banii înapoi. Jocul se joacă cu un pachet de N cărți. Pachetul de cărți este reprezentat că un șir binar cum va fi descris în cele ce urmează.Cărțile pot fi așezate pe față sau pe spate fără a conta culoarea sau valoarea cărții, pentru simplitate codificăm o care întoarsă prin cifra 0 și o carte pe față prin cifra 1 . Fiecare jucător poate face un număr nelimitat de operații de următorul tip: se alege un index i și se întorc toate cărțile din secvență de cărți i...n, adică o carte de valoare 0 se transformă în carte de valoare 1 și invers. Acum este rândul lui Le Quack, el va prezintă configurația curentă a cărților și voi trebuie să îl ajutați cu 2 cerințe, el va poate răsplăti cu un posibil loc I la concurs.

Cerinta 1: Stiind configuratia cartilor sunteti rugati sa aflati lungimea maxima a unei secvente de carti, astfel incat costul de a transforma aceasta secventa intr-o secventa de carti care contin doar valori de 1 este maxim K.

Certina 2: Stiind configuratia cartilor sunteti intrebati care este numarul secventelor de carti pentru care numarul minim de operatii pentru a devni o secventa care contine numai valori de 1 este fix K.

== Date de intrare ==
Pe prima linie sunt scrise valorile C, N si K, reprezentand numarul cerintei, numarul de carti respectiv valoarea K descrisa in enunt. Pe a doua linie sunt N valori binare reprezentand sirul de carti. Numerele se citesc din fisierul flipc.in.
== Date de ieșire ==
Se va tiparii un singur numar, reprezentand raspunul la cerinta aferenta. Numerele se tiparesc in fisieru flipc.out.
== Restricţii şi precizări ==
* Cerinta I:
Pentru 40/40 p : N <= 1.000.000 , K <= N
Pentru 30/40 p : N <= 200.000 , K <= N
Pentru 10/40 p : N <= 10.000 , K <= min(N , 100)
* Cerinta II:
Pentru 60/60 p : N <= 1.000.000 , K <= N
Pentru 50/60 p : N <= 200.000 , K <= N
Pentru 15/60 p : N <= 10.000 , K <= min(N , 100)
O carte NU se poate roti de 2 ori in aceasi mutare !
== Exemplul 1 ==
; flipc.in

  1 5 2
  10001
; flipc.out

  5
; flipc.in

  2 13 4
  1010011111101
; flipc.out

  15
= Explicație ==
Pentru primul exemplu : putem transforma tot stringul in valori de 1 in 2 operatii, prima operatie la
pozitia 2 si a doua la pozitia 5.
Pentru al doilea exemplu : niste exemple de secvente care contin doar valori de 1 si sunt formate prin
4 operatii ar avea capetele: {1,6}, {2,6}, {1,9} .....
<br>

== Exemplul 2 ==
; 
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
def max_length_of_sequence(N, K, cards):
    max_len = 0
    count_zeroes = 0
    left, right = 0, 0

    while right < N:
        if cards[right] == '0':
            count_zeroes += 1

        while count_zeroes > K:
            if cards[left] == '0':
                count_zeroes -= 1
            left += 1

        max_len = max(max_len, right - left + 1)
        right += 1

    return max_len

def count_sequences(N, K, cards):
    count = 0
    count_zeroes = 0
    left, right = 0, 0

    while right < N:
        if cards[right] == '0':
            count_zeroes += 1

        while count_zeroes > K:
            if cards[left] == '0':
                count_zeroes -= 1
            left += 1

        if count_zeroes == K:
            count += N - right

        right += 1

    return count

def solve_problem(C, N, K, cards):
    if C == 1:
        return max_length_of_sequence(N, K, cards)
    elif C == 2:
        return count_sequences(N, K, cards)

def read_input(file_name):
    with open(file_name, 'r') as file:
        line = file.readline().strip().split()
        C, N, K = map(int, line)
        cards = file.readline().strip()
    return C, N, K, cards

def write_output(file_name, result):
    with open(file_name, 'w') as file:
        file.write(str(result))

def main():
    C, N, K, cards = read_input("flipc.in")
    result = solve_problem(C, N, K, cards)
    write_output("flipc.out", result)

if __name__ == "__main__":
    main()

</syntaxhighlight>