3431 - Cartonase 3

Sursa: [1]

Cerinţa

Ionel are N cartonașe. Fiecare cartonaș are înscrise două numere (un număr, s, în partea stângă, și celălalt număr, d, î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 s și d, 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 ≤ s ≤ 10.000;

1 ≤ d ≤ 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

Intrare

1

5

2 10

10 5

10 2

2 10

37 5

Ieșire

2

Exemplul 2

Intrare

2

5

2 10

10 5

5 2

2 10

37 5

Ieșire

4

Exemplul 3

Intrare

3

6

2 10

10 5

2 8

6 2

2 10

37 5

Ieșire

2

Rezolvare

<syntaxhighlight lang="python" line>

1. 3431

def num_pairs(cards):

   num_pairs = 0
   for i in range(len(cards)-1):
       if cards[i][1] == cards[i+1][0]:
           num_pairs += 1
   return num_pairs

def longest_sequence(cards):

   max_len = 1
   curr_len = 1
   for i in range(len(cards)-1):
       if cards[i][1] == cards[i+1][0]:
           curr_len += 1
           if curr_len > max_len:
               max_len = curr_len
       else:
           curr_len = 1
   return max_len

def num_max_sequences(cards):

   max_len = 1
   curr_len = 1
   num_max_len = 1
   for i in range(len(cards)-1):
       if cards[i][1] == cards[i+1][0]:
           curr_len += 1
           if curr_len > max_len:
               max_len = curr_len
               num_max_len = 1
           elif curr_len == max_len:
               num_max_len += 1
   return num_max_len

if __name__ == '__main__':

   C = int(input())
   N = int(input())
   if not 1 <= N <= 500:
       print("N trebuie sa fie intre 1 si 500.")
       exit()
   cards = []
   for i in range(N):
       s, d = map(int, input().split())
       if not (1 <= s <= 10000 and 1 <= d <= 10000):
           print("Valorile s si d trebuie sa fie intre 1 si 10000.")
           exit()
       cards.append((s, d))

   if C == 1:
       print(num_pairs(cards))
   elif C == 2:
       print(longest_sequence(cards))
   else:
       print(num_max_sequences(cards))

</syntaxhighlight>

Explicatie cod:

Acest cod este o soluție la o problemă matematică care presupune determinarea unor perechi de cărți într-un șir de cărți, în funcție de o regulă. Scopul este să se scrie un program care primește ca input o valoare C (1, 2 sau 3), un număr N (numărul de cărți din șir), și N perechi de numere s și d, reprezentând cărțile. Dacă C este 1, programul trebuie să afișeze numărul de perechi de cărți în care valoarea de pe cartea dreaptă a primei cărți este egală cu valoarea de pe cartea stângă a celei de-a doua cărți. Dacă C este 2, programul trebuie să afișeze lungimea celei mai lungi secvențe de cărți în care valoarea de pe cartea dreaptă a unei cărți este egală cu valoarea de pe cartea stângă a celei de-a doua cărți. Dacă C este 3, programul trebuie să afișeze numărul de secvențe de cărți de lungime maximă care respectă regula dată.

Funcțiile num_pairs, longest_sequence și num_max_sequences implementează cele trei cerințe ale problemei. Ele iau ca argument șirul de cărți și returnează valoarea corespunzătoare.

În blocul if name == 'main': se face validarea datelor de intrare. Se primește valoarea C și N, iar apoi se creează o listă de perechi de cărți folosind funcția map(). Dacă N nu este între 1 și 500, se afișează un mesaj de eroare și programul se termină. În plus, dacă oricare dintre valorile s sau d este mai mică decât 1 sau mai mare decât 10000, programul va afișa un alt mesaj de eroare și se va termina. În cele din urmă, se apelează funcțiile corespunzătoare în funcție de valoarea C și se afișează rezultatul.