La Celebritat U49842

Suposem que una celebritat apareix a una festa. En aquesta festa hi ha $n > 0$ persones (celebritat inclosa). Cada persona s’identifica amb un nombre entre $0$ i $n-1$.

Què és una celebritat? Una celebritat és algú que no coneix ningú a la festa, però tothom coneix la celebritat.

Suposem que tenim una matriu $n \times n$ de booleans, diguem-ne $M$, per determinar si alguna persona $i$ coneix alguna altra persona $j$: $M[i][j] = \texttt{True}$ si la persona $i$ coneix la persona $j$. La matriu no té per què ser simètrica (encara que $i$ conegui $j$, no té per què passar que $j$ conegui $i$). Anomenarem matriu de coneixences aquesta matriu $M$.

Feu una funció troba_celebritat(M), on $M$ és la matriu de coneixences, que faci servir una pila per determinar de manera eficient si una celebritat és present i, si n’hi ha una, identificar qui és aquesta celebritat.

Pista: Fixeu-vos en el següent:

• Donats dos $i$ i $j$ ($i \neq j$), si $M[i][j]$ aleshores $i$ no pot ser la celebritat

• Donats dos $i$ i $j$ ($i \neq j$), si $not\ M[i][j]$ aleshores $j$ no pot ser la celebritat

Precondició

$M$ és una matriu de booleans: $M[i][j] = \texttt{True}$ si la persona $i$ coneix la persona $j$. $M[i][j] = \texttt{False}$ altrament.

Entrada

Primer ens proporcionen el nombre $n > 0$ de convidats a la festa. Després trobem $n^2$ nombres $1$ ($\texttt{True}$) o $0$ ($\texttt{False}$) que ens descriuen la matriu de coneixences.

Vegeu els exemples que formen el joc de proves públic.

Sortida

Cal escriure l’identificador de la celebritat, o no hi ha celebritat en cas que no hi hagi cap celebritat.

Vegeu els exemples que formen el joc de proves públic.

Observacions

Heu de baixar-vos el fitxer code.py (icona de la serp). Aquest fitxer és un programa amb tot el que cal per executar els jocs de prova públics. Només falta, clar, la funció que us demana l’enunciat. Aquest fitxer l’heu de completar amb el codi que falta, i això, tot, és el que heu d’enviar al Jutge com a solució.

Si $n$ és el nombre de participants a la festa (celebritat inclosa), la funció demanada ha de tenir complexitat $O(n)$. Això no ho pot detectar el Jutge perquè només la lectura de la matriu de coneixences ja té un cost $O(n^2)$.

L’eficiència i la qualitat de la solució es tindran en compte a la correcció manual. Cap funció amb cost quadràtic $O(n^2)$ serà considerada bona.