Porra P72480


Statement
 

pdf   zip

thehtml

Una gran tradició del SWERC és fer una porra sobre com quedaran els tres equips de la UPC. Típicament, cada aposta consisteix en tres enters diferents p1, p2 i p3, on pi és la posició pronosticada per a UPC i. El guanyador és qui té una suma de distàncies a les posicions finals més petita. En cas d’empat a suma mínima de distàncies, tots els empatats guanyen.

Enguany un dels membres dels equips UPC ha “stalkejat” a la resta d’equips participants. Amb tota la informació aconseguida pot assegurar les posicions relatives d’alguns equips, és a dir, pot saber que l’equip x guanyarà a l’equip y, per a m parells de x i y. En total hi ha n equips, numerats entre 0 i n−1. L’equip UPC i és el i − 1.

Donada la informació de què es disposa i les 9 apostes dels membres dels equips UPC, quin d’ells té més probabilitats de guanyar? Suposeu que totes les classificacions (permutacions de {1 … n}) que són consistents amb les m restriccions són equiprobables.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i m. A continuació venen m parelles diferents d’enters x i y, tal i com s’ha explicat anteriorment. Finalment, tenim les 9 apostes dels membres dels equips UPC. Suposeu 3 ≤ n ≤ 10, 0 ≤ mn(n−1)/2, i que les m ‍restriccions donades són consistents amb almenys una classificació.

Sortida

Per a cada cas, escriviu els membres amb més probabilitats de guanyar. En cas que n’hi hagi més d’un, s’han d’escriure en ordre creixent. Els membres s’identifiquen entre 0 i 8.

Public test cases
  • Input

    10 5  4 0  5 0  6 0  0 2  2 1
    1 5 6  2 4 6  1 4 9
    2 5 8  2 6 7  2 6 5
    2 5 9  3 7 5  2 5 6
    
    3 0
    1 2 3  1 3 2  2 1 3
    2 3 1  3 1 2  3 2 1
    1 2 3  1 3 2  2 1 3
    
    4 1  2 3
    4 2 1  2 1 4  2 3 4
    3 2 1  3 2 1  3 4 2
    2 3 4  1 3 4  2 3 1
    

    Output

    7
    0 1 2 3 4 5 6 7 8
    0 8
    
  • Information
    Author
    Cesc Folch
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++