Dominatori di torneo

Il torneo amatoriale di Rocca Caprina per N giocatori prevede lo scontro diretto di ogni partecipante con tutti gli altri, ossia Nx(N-1)/2partite.
Poiché l’intero torneo dura una settimana, le partite vengono interrotte allo scadere della settimana.

Per l’assegnazione del montepremi (orecchiette, cavatelli, intorchiate, taralli, diavulaccé, taràtufulu e scagliozzi), sono considerate valide soltanto le M partite in cui è stata assegnata una vittoria, dove M ≤ Nx(N-1)/2.
Non potendo sempre stabilire un singolo vincitore del torneo, tale montepremi viene assegnato a una coalizione di dominatori, che esiste sempre ed è definita come segue.

Una coalizione è un gruppo di giocatori tali che nessun giocatore del gruppo ha mai vinto contro un altro giocatore dello stesso gruppo.

Numerati in modo univoco i giocatori da 1 fino a N, i giocatori dominati da una coalizione G sono tutti quei giocatori C per i quali almeno una delle seguenti condizioni è soddisfatta (dove 1 ≤ A, B, C ≤ N sono tre numeri distinti che individuano altrettanti giocatori):

  • C appartiene alla coalizione G oppure
  • esiste un giocatore A in G che ha vinto la partita contro C oppure
  • esiste un giocatore A in G che ha vinto la partita contro un qualche giocatore B e, a sua volta, B ha vinto la partita contro C.

Lo scoperto di una coalizione è il numero di giocatori non dominati da essa.

Una coalizione di dominatori è quindi una coalizione con scoperto pari a 0.

Scrivete un programma che aiuti a individuare una coalizione.

Dati in Input

Il file input.txt è composto da M+1 righe, dove M è un intero positivo.

  • La prima riga contiene due interi positivi N e M che rappresentano rispettivamente il numero N di giocatori e il numero M di partite in cui è stata assegnata una vittoria.
  • Le successive M righe contengono i risultati delle partite in cui è stata assegnata una vittoria. Ciascuna di tali righe è composta da due interi distinti I e J separati da uno spazio per indicare che I ha vinto nella partita contro J, dove 1 ≤ I, J ≤ N (quindi il primo intero è il vincitore mentre il secondo intero è il perdente).

Dati in Output

Il file output.txt è composto da una sola riga contenente i numeri, separati da uno spazio, che identificano i giocatori di una coalizione.

Assunzioni

  • 2 ≤ N ≤ 1000
  • 1 ≤ M ≤ Nx(N-1)/2

Valutazione delle soluzioni

Il punteggio è pari a 0 nel caso in cui l’output non rappresenti una coalizione.
Altrimenti, sia Z lo scoperto della coalizione restituita.
Il punteggio viene assegnato secondo la seguente regola:

  • punteggio pieno pari a D=3 se Z=0 (coalizione di dominatori);
  • punteggio pari a 1 se 0 < Z ≤ N/2;
  • punteggio pari a 0 altrimenti.

Esempi

input.txt output.txt
1 4 4
1 2
4 2
3 4
3 2
1 3
2 7 8
1 5
6 1
6 2
4 2
4 1
2 3
3 6
3 4
6 4 7
3 7 8
1 5
6 1
6 2
4 2
4 1
2 3
3 6
3 4
1 3 7

 

Note

  • Poiché una coalizione di dominatori esiste sempre, per gli esempi forniti è stato reputato utile elencare una delle coalizioni di dominatori, ma ovviamente una soluzione parziale è ammessa come risposta e soggetta alla valutazione di cui sopra.
Notice: This work is licensed under a BY-NC-SA. Permalink: Dominatori di torneo

Comments are closed.