3065 - trio

Cerința

Trio este un joc ce conține N piese de aceeași formă, așezate una lângă alta pe o tablă de joc și numerotate de la stânga la dreapta cu valori de la 1 la N. Fiecare piesă are marcate pe ea trei zone, iar în fiecare dintre ele este scrisă câte o cifră. Se consideră că o piesă pe care sunt scrise în ordine, de la stânga la dreapta, cifrele C1, C2 și C3 are următoarele proprietăți: este identică cu o altă piesă, dacă această piesă conține exact aceleași cifre, în aceeași ordine cu ale ei sau în ordine inversă. Astfel, piesa C1|C2|C3 este identică cu o altă piesă de forma C1|C2|C3 și cu o piesă de forma C3|C2|C1. este prietenă cu o altă piesă dacă aceasta conține exact aceleași cifre ca piesa dată, dar nu neapărat în aceeași ordine. Astfel, piesa C1|C2|C3 este prietenă cu piesele: C1|C2|C3, C1|C3|C2, C2|C1|C3, C2|C3|C1, C3|C1|C2 și C3|C2|C1. Se observă că două piese identice sunt și prietene! Un grup de piese prietene este format din TOATE piesele prietene între ele, aflate pe tabla de joc. 1) Alegeți o piesă de pe tabla de joc, astfel încât numărul M al pieselor identice cu ea să fie cel mai mare posibil și afișați numărul M determinat; 2) Afișați numărul grupurilor de piese prietene existente pe tabla de joc; 3) Afișați numărul maxim de piese dintr-o secvență ce conține piese așezate una lângă alta pe tabla de joc, pentru care prima piesă și ultima piesă din secvență sunt prietene.

Date de intrare

Fișierul de intrare trio.in conține - pe prima linie un număr natural C care reprezintă numărul cerinţei şi poate avea valorile 1, 2 sau 3. - pe cea de-a doua linie un număr natural N ce reprezintă numărul pieselor de joc; - pe următoarele N linii, câte trei cifre, despărțite prin câte un spațiu, ce reprezintă, în ordine, cifrele scrise pe câte o piesă de joc. Piesele sunt date în ordinea numerotării acestora pe tabla de joc.

Date de ieșire

Fișierul de ieșire trio.out va conține pe prima linie un singur număr natural ce reprezintă rezultatul determinat conform fiecărei cerințe.

Restricții și precizări

• 2 ≤ N ≤ 100.000
• Există cel puțin două piese identice pe tabla de joc;
• O piesă ce nu e prietenă cu nicio altă piesă de pe tabla de joc formează singură un grup;

Exemplu 1

Intrare

1
6
1 3 3
4 5 9
1 3 3
9 5 4
3 3 1
9 4 5

Iesire

2

Rezolvare

<syntaxhighlight lang="python" line> def reverse_piece(piece):

   """Returnează piesa inversată."""
   return piece[::-1]

def are_friends(piece1, piece2):

   """Verifică dacă două piese sunt prietene."""
   if piece1 == piece2:
       return True
   if piece1 == reverse_piece(piece2):
       return True
   c1, c2, c3 = piece1
   for i in range(3):
       if piece2 == c2 + c3 + c1 or piece2 == c3 + c1 + c2:
           return True
       c1, c2, c3 = c3, c1, c2  # permutăm cifrele
   return False

def cerinta1(pieces):

   """Determină M al pieselor identice cu cea selectată."""
   from collections import Counter
   counter = Counter(pieces)
   most_common_piece, count = counter.most_common(1)[0]
   return count

def cerinta2(pieces):

   """Numărul grupurilor de piese prietene."""
   n = len(pieces)
   visited = [False] * n

   def dfs(i):
       stack = [i]
       while stack:
           node = stack.pop()
           if not visited[node]:
               visited[node] = True
               for j in range(n):
                   if not visited[j] and are_friends(pieces[node], pieces[j]):
                       stack.append(j)

   groups = 0
   for i in range(n):
       if not visited[i]:
           groups += 1
           dfs(i)

   return groups

def cerinta3(pieces):

   """Numărul maxim de piese dintr-o secvență ce conține piese prietene."""
   n = len(pieces)
   max_length = 0
   current_length = 0

   for i in range(n):
       if i == 0 or are_friends(pieces[i], pieces[i - 1]):
           current_length += 1
       else:
           max_length = max(max_length, current_length)
           current_length = 1

   max_length = max(max_length, current_length)
   return max_length

def main():

   with open('trio.in', 'r') as f:
       data = f.read().splitlines()

   c = int(data[0].strip())
   n = int(data[1].strip())
   pieces = [line.strip().replace(" ", "") for line in data[2:2 + n]]

   assert 2 <= n <= 100000, "N trebuie să fie între 2 și 100000"
   assert all(len(piece) == 3 for piece in pieces), "Fiecare piesă trebuie să aibă exact 3 cifre"

   if c == 1:
       result = cerinta1(pieces)
   elif c == 2:
       result = cerinta2(pieces)
   elif c == 3:
       result = cerinta3(pieces)
   else:
       raise ValueError("C trebuie să fie 1, 2 sau 3")

   with open('trio.out', 'w') as f:
       f.write(f"{result}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>