Un problema alle olimpiadi regionali chiedeva di risolvere questo(il problema si chiama Bilancino): (riassumo brevemente) dati n numeri e m coppie di numeri che indicano un confronto(in modo tale che la coppia (a;b) sia a<b) determinare se si riesce a ordinare tutti gli n numeri avendo a disposizione solo le m coppie o sono necessarie altri confronti. Il programma deve restituire 0 se si riesce a ordinarli, 1 se è necessario solo un altro confronto, 2 se sono necessari più confronti. Ho cercato vari modi ma non sono riuscito a risolverlo...Avete qualche idea?
Per chiarire mostro un input e il risultato
n=3 ; m=3;
3 2
1 2
3 1
output=0. Questo perchè 3<2, 1<2, 3<1. Quindi 3<1<2. (se fate confusione con i numeri usate delle lettere).
Il corrispettivo con le lettere sarebbe:
a <b
c <b
a <c
Quindi a<c<b. Spero di essere stato chiaro.
Rispondi quotando