Benzar Ioan: Pagină nouă: == 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...

2024-06-03T03:53:24Z

Pagină nouă: == 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...

New page

== 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>

3065 - trio - Revision history