3431 - Cartonase 3

Sursa: [1]

Cerinţa

Ionel are N cartonașe. Fiecare cartonaș are înscrise două numere (un număr, nr_cartonas_stanga, în partea stângă, și celălalt număr, nr_cartonas_dreapta, în partea dreaptă). El a așezat cartonașele într-un șir, lipite unul de celălalt, astfel încât numărul din partea dreaptă a primului cartonaș este lipit de numărul din partea stângă a celui de-al doilea cartonaș, numărul din partea dreaptă a celui de al doilea cartonaș este lipit de numărul din partea stângă a celui de-al treilea cartonaș etc. Spunem că două cartonașe alăturate “se potrivesc” dacă numărul din dreapta al primului cartonaș este egal cu numărul din stânga al celui de al doilea cartonaș.

Ionel observă că sunt perechi de cartonașe alăturate care “se potrivesc” și chiar secvențe de mai multe cartonașe alăturate, în care primul “se potrivește” cu al doilea, al doilea “se potrivește” cu al treilea etc.

Scrieți un program care să citească numărul N de cartonașe, numerele înscrise pe fiecare cartonaș și determină:

1) Numărul de perechi de cartonașe care “se potrivesc”. 2) Numărul de cartonașe din cea mai lungă secvență în care fiecare două cartonașe alăturate “se potrivesc”. 3) Numărul de secvențe cu număr maxim de cartonașe care “se potrivesc”.

Date de intrare

Programul conține doar numere naturale nenule:

pe prima linie se găsește numărul C care poate avea doar valorile 1, 2 sau 3 și reprezintă cerința care urmează a fi rezolvată. Pe a doua linie a programului se găsește numărul natural N, cu semnificația din enunț.

pe fiecare dintre următoarele N linii se află, în acestă ordine, câte două numere naturale nr_cartonas_stanga și nr_cartonas_dreapta, separate printr-un spațiu, cu semnificația din enunț pentru un cartonaș. Perechile de numere sunt date în ordinea în care cartonașele corespunzătoare lor apar în șirul lui Ionel.

Date de ieșire

Programul va conține pe prima linie un număr natural reprezentând răspunsul la cerința specificată.

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează cerintele de mai sus.

În caz contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse."

Restricţii şi precizări

1 ≤ N ≤ 500;

1 ≤ nr_cartonas_stanga ≤ 10.000;

1 ≤ nr_cartonas_dreapta ≤ 10.000

În concurs, pentru rezolvarea fiecărei cerințe se obțin câte 30 de puncte. Pe site se acordă 10 puncte pentru exemple.

Exemplul 1

Datele de intrare

Introduceti cerinta (1, 2 sau 3): 1

Introduceti numarul de cartonase: 5

Introduceti cartonasul stanga si cartonasul dreapta:2 10

Introduceti cartonasul stanga si cartonasul dreapta:10 5

Introduceti cartonasul stanga si cartonasul dreapta:10 2

Introduceti cartonasul stanga si cartonasul dreapta:2 10

Introduceti cartonasul stanga si cartonasul dreapta:37 5

Datele de ieșire

Datele sunt introduse corect.

3

Exemplul 2

Datele de intrare

Introduceti cerinta (1, 2 sau 3): 2

Introduceti numarul de cartonase: 5

Introduceti cartonasul stanga si cartonasul dreapta:2 10

Introduceti cartonasul stanga si cartonasul dreapta:10 5

Introduceti cartonasul stanga si cartonasul dreapta:10 2

Introduceti cartonasul stanga si cartonasul dreapta:2 10

Introduceti cartonasul stanga si cartonasul dreapta:37 5

Datele de ieșire

Datele sunt introduse corect.

4

Exemplul 3

Datele de intrare

Introduceti cerinta (1, 2 sau 3): 3

Introduceti numarul de cartonase: 5

Introduceti cartonasul stanga si cartonasul dreapta:2 10

Introduceti cartonasul stanga si cartonasul dreapta:10 5

Introduceti cartonasul stanga si cartonasul dreapta:10 2

Introduceti cartonasul stanga si cartonasul dreapta:2 10

Introduceti cartonasul stanga si cartonasul dreapta:37 5

Datele de ieșire

Datele sunt introduse corect.

3

2

Rezolvare

<syntaxhighlight lang="python" line>

1. 3431

def validate_input(n, cards):

   if n != len(cards):
       return False
   for card in cards:
       if len(card) != 2:
           return False
       if not all(1 <= x <= 10000 for x in card):
           return False
   return True

def find_matching_pairs(cards):

   matching_pairs = 0
   max_sequence = 1
   current_sequence = 1
   for i in range(len(cards) - 1):
       if cards[i][1] == cards[i + 1][0]:
           matching_pairs += 1
           current_sequence += 1
           max_sequence = max(max_sequence, current_sequence)
       else:
           current_sequence = 1
   return (matching_pairs, max_sequence)

def find_max_sequences(cards):

   max_sequence_length = 1
   sequence_lengths = {}
   current_sequence_length = 1
   for i in range(len(cards) - 1):
       if cards[i][1] == cards[i + 1][0]:
           current_sequence_length += 1
       else:
           if current_sequence_length in sequence_lengths:
               sequence_lengths[current_sequence_length] += 1
           else:
               sequence_lengths[current_sequence_length] = 1
           max_sequence_length = max(max_sequence_length, current_sequence_length)
           current_sequence_length = 1
   if current_sequence_length in sequence_lengths:
       sequence_lengths[current_sequence_length] += 1
   else:
       sequence_lengths[current_sequence_length] = 1
   max_sequence_count = sequence_lengths[max_sequence_length]
   return max_sequence_count

if __name__ == '__main__':

   c = int(input("Introduceti cerinta (1, 2 sau 3): "))
   n = int(input("Introduceti numarul de cartonase: "))
   cards = [list(map(int, input("Introduceti cartonasul stanga si cartonasul dreapta:").split())) for _ in range(n)]

   if not validate_input(n, cards):
       print("Datele nu corespund restrictiilor impuse.")
   else:
       print("Datele sunt introduse corect.")
       if c == 1:
           matching_pairs, max_sequence = find_matching_pairs(cards)
           print(matching_pairs + 1)
       elif c == 2:
           matching_pairs, max_sequence = find_matching_pairs(cards)
           print(max_sequence)
       elif c == 3:
           max_sequence_count = find_max_sequences(cards)
           print(max_sequence_count)

</syntaxhighlight>

Explicatie cod:

Acest cod reprezintă o soluție pentru o problemă care are trei cerințe diferite.

Funcția `validate_input` verifică dacă datele introduse corespund unor anumite restricții. Mai precis, verifică dacă numărul de cartonașe introduse corespunde valorii `n` și dacă fiecare cartonaș este format din două numere întregi cuprinse între 1 și 10000.

Funcția `find_matching_pairs` primește o listă de cartonașe și calculează numărul de perechi de cartonașe care se potrivesc și lungimea cea mai mare a unei secvențe de cartonașe consecutive care se potrivesc.

Funcția `find_max_sequences` primește o listă de cartonașe și calculează numărul de secvențe maximale de cartonașe consecutive care se potrivesc.

În `main`, utilizatorul trebuie să introducă numărul cerinței (`c`) și numărul de cartonașe (`n`) și apoi cartonașele propriu-zise. Dacă datele introduse sunt valide, se apelează funcția corespunzătoare cerinței și se afișează rezultatul. Pentru cerința 1, se afișează numărul de perechi de cartonașe care se potrivesc plus 1. Pentru cerința 2, se afișează lungimea cea mai mare a unei secvențe de cartonașe consecutive care se potrivesc. Pentru cerința 3, se afișează numărul de secvențe maximale de cartonașe consecutive care se potrivesc.