2458 - Hobby

Enunt

În școala lui Gigel copiii se pregătesc pentru vacanță. Ei vor să-și petreacă timpul liber în mod diferit în funcție de hobby-urile pe care le au. În concluzie, urmează să formeze grupuri, pe baza preferințelor. Totuși, a apărut o problemă. Unii sunt dispuși să renunțe la propriul hobby și preferă să facă parte dintr-un grup din care face parte și un anumit prieten al lor. În școala lui Gigel sunt n copii, numerotați de la 1 la n.

Cerinţa

Cunoscând prietenul preferat și hobby-ul fiecărui copil, scrieți un program care determină numărul grupurilor care se vor forma și numărul grupurilor formate din copii care au hobby-uri identice; doi copii vor face parte din același grup, dacă cel puțin unul din cei doi l-a numit pe celălalt ca prieten.

Date de intrare

Pe prima linie a fișierului de intrare hobby1.in se află un număr natural n, reprezentând numărul copiilor. Pe fiecare din următoarele n linii se află câte o pereche de numere naturale, unde primul număr reprezintă numărul de ordine al copilului având ca prieten preferat copilul identificat cu cel de al doilea număr. Pe următoarele n linii se află, pe fiecare, câte un șir de caractere format din litere mici ale alfabetului englez, reprezentând hobby-urile copiilor în ordinea în care sunt numerotați copiii.

Date de ieșire

Pe prima linie a fișierului de ieșire hobby1.out veți scrie numărul gr al grupurilor de copii. Pe următoarea linie veți afișa numărul grupurilor în care toți copiii au același hobby.

Restricţii şi precizări

• 1 ≤ n ≤ 700.
• 1 ≤ lungime_denumire_hobby ≤ 10.
• 1 ≤ gr ≤ 400.
• numărul de ordine al fiecărui copil apare o singură dată pe prima poziție a unei perechi.
• un copil poate fi prietenul mai multor copii.
• numărul maxim al hobby-urilor: 20.
• La concurs s-au dat 10 puncte din oficiu, aici sunt date pe exemplu.

Exemplu

hobby.in

8
1 2
3 4
5 6
7 7
8 3
2 1
4 3
6 2
baschet
baschet
tenis
fotbal
baschet
baschet
muzica
tenis

hobby.out

3
2

Explicație

Avem 3 grupuri: 1: 1 2 5 6 2: 7 3: 3 4 8 Toți copiii din primul grup (cu numerele de ordine 1 2 5 6) au ca hobby baschetul, copilul 7 este singur, iar în al treilea grup hobby-urile diferă. Deci avem 2 grupuri în care copiii au același hobby.

Rezolvare

<syntaxhighlight lang="python" line> def form_groups(n, preferences, hobbies):

   groups = {}  # Dicționar pentru a înregistra grupurile

   for i in range(1, n+1):
       friend = preferences[i]
       hobby = hobbies[i]

       # Verificăm dacă prietenul preferat este deja într-un grup
       if friend in groups:
           # Adăugăm copilul curent în grupul prietenului său
           groups[friend].append(i)
           groups[i] = groups[friend]  # Actualizăm grupul pentru copilul curent
       else:
           # Creăm un nou grup pentru ei
           groups[i] = [i]

   return groups

def count_same_hobbies(groups, hobbies):

   same_hobby_groups = 0

   for group in groups.values():
       # Verificăm dacă toți copiii din grup au același hobby
       same_hobby = all(hobbies[child] == hobbies[group[0]] for child in group)
       if same_hobby:
           same_hobby_groups += 1

   return same_hobby_groups

def main():

   with open("hobby.in", "r") as fin:
       n = int(fin.readline())
       preferences = {}
       hobbies = {}

       for _ in range(n):
           child, friend = map(int, fin.readline().split())
           preferences[child] = friend

       for _ in range(n):
           hobbies[i] = fin.readline().strip()

   # Formăm grupurile
   groups = form_groups(n, preferences, hobbies)

   # Numărăm grupurile cu aceleași hobby-uri
   same_hobby_groups = count_same_hobbies(groups, hobbies)

   # Scriem rezultatul în fișierul de ieșire
   with open("hobby.out", "w") as fout:
       fout.write(str(len(groups)) + "\n")
       fout.write(str(same_hobby_groups) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>