Editing 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<br>
6<br>
1 3 3<br>
4 5 9<br>
1 3 3<br>
9 5 4<br>
3 3 1<br>
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>