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

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>