Algoritmusok
Kis bemenet
Nevezzük az i. csapat útjának azokat a meccseket, ahol ez a csapat pályára léphet,
amennyiben nem esik ki korábban. Az út P mérkőzésből áll. Bizonyítható a következő lemma:
Az i. csapatra vonatkozó korlát teljesülésének szükséges és elégséges feltétele, hogy i útján legalább P-M[i] mérkőzésre jegyet kell váltani.
Ezek után a következő algoritmus adható:
- minden csapathoz felírjuk a KELL[i]=P-M[i] értéket
- alulról (az első fordulótól) indulunk
- minden csapatra megnézzük, hogy KELL[i] kisebb-e, mint a hátralévő (kezdetben P) mérkőzések száma az úton
- ha kisebb, akkor az i. csapat miatt még nem kell jegyet venni; ha egyenlő, akkor kell
- az adott meccsről való döntés után elég azt a csapatot tovább vinni, amelyre
KELL[i] nagyobb
- ha egy úton vettünk egy meccsre jegyet, akkor onnantól kezdve minden meccsre meg kell venni, egészen a döntőig
Nagy bemenet
Kódokok
Kis bemenet
Nagy bemenet
