1739 - Proiecte 1

Enunt

În oraşul Iaşi, cele N firme IT derulează în prezent M proiecte din acest domeniu (printre care şi ONI 2012). Firmele sunt identificate prin numere naturale de la 1 la N, iar proiectele sunt identificate prin numere naturale de la 1 la M. Fiecare proiect are una sau mai multe etape, o etapă fiind executată de o singură firmă IT. Spunem că o firmă coordonează un proiect dacă execută mai mult de jumătate din etapele proiectului.

Cerinţa

Cunoscând numărul firmelor IT, numărul proiectelor, numărul de etape ale fiecărui proiect şi firmele ce execută fiecare etapă, să se determine firma/firmele care coordonează cel mai mare număr de proiecte.

Date de intrare

Fişierul de intrare proiecte.in conţine, pe prima linie, numerele naturale N şi M, separate printr-un spaţiu, cu semnificaţia de mai sus. Pe fiecare dintre următoarele M linii se află informaţii despre câte un proiect, în ordinea numerelor de identificare a acestora. Astfel, pe linia corespunzătoare proiectului i (1≤i≤M), se află un număr natural nri, urmat de nri numere naturale f1f2…fnri , reprezentând numărul de etape ale acestui proiect, respectiv firmele care execută fiecare etapă din proiect (firma fk

execută etapa k, 1≤k≤nri). Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire proiecte.out va conţine o singură linie, pe care va fi scris numărul de identificare al firmei/firmelor care coordonează cel mai mare număr de proiecte. Dacă sunt mai multe astfel de firme, numerele de identificare ale acestora se vor afişa pe aceeaşi linie, în ordine crescătoare, separate prin câte un spaţiu.

Restricţii şi precizări

• 1 ≤ M ≤ 200
• 1 ≤ N ≤ 1000000
• 1 ≤ nri ≤ 200000 (1≤i≤M)
• 1 ≤ M*nri ≤ 320000 (1≤i≤M)
• 1 ≤ fk≤ N, (1≤k≤nri)
• există întotdeauna cel puţin un proiect coordonat de o firmă.

Exemplul 1

proiecte.in

 5 4
 2 3 3
 3 1 2 1
 5 3 4 3 3 1
 1 1

proiecte.out

 1 3

Explicație

Numărul maxim de proiecte coordonate de aceeaşi firmă este 2: firma 1 coordonează proiectele 2 şi 4, iar firma 3 coordonează proiectele 1 şi 3.

Rezolvare

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

   with open("proiecte.in", "r") as fin:
       N, M = map(int, fin.readline().split())
       projects = [list(map(int, fin.readline().split()))[1:] for _ in range(M)]

   project_count = {i: 0 for i in range(1, N + 1)}

   for project in projects:
       firms_count = {f: 0 for f in project}
       for firm in project:
           firms_count[firm] += 1
       max_count = max(firms_count.values())
       for firm, count in firms_count.items():
           if count > len(project) / 2:
               project_count[firm] += 1

   max_projects = max(project_count.values())
   coordinating_firms = [firm for firm, count in project_count.items() if count == max_projects]

   with open("proiecte.out", "w") as fout:
       fout.write(" ".join(map(str, coordinating_firms)))

if __name__ == "__main__":

   main()

</syntaxhighlight>