Tävlingsprogrammering/Uppgifter/Tennisklubben
Tennisklubben - Uppgift 5 - Onlinekvalet till PO 2007
I en tennisklubb finns n spelare. De är alla rankade från den bäste med rankingnummer 1 till den sämste som har rankingnummer n. Men tennis är en oberäknelig sport och det kan bli så att den som är rankad 99:a någon gång vinner mot 32:an. Om 32:an i sin tur slår 85:an, som i sin tur slår 44:an som slår 1:an, innebär det att 99:an har en kedja med bara fyra länkar till toppen! Du ska skriva ett program som för en given spelare räknar ut längden av den kortaste kedjan upp till toppen, eller avgör att ingen sådan kedja finns. För den som direkt har vunnit mot 1:an är längden alltså 1 och för 1:an själv är förstås längden 0.
Indata
På första raden står två heltal n och k, (1 ≤ n ≤ 100 och 1 ≤ k ≤ n), där n är antalet spelare och k är rankingnumret för den spelare som vi är intresserade av. På andra raden står ett heltal m, (1 ≤ m ≤ 1000), antalet matcher som har spelats. Därefter följer m rader, vardera beskrivande en match. På var och en av dessa rader står två heltal i intervallet 1..n. Det första talet är rankingnumret för den spelare som vann matchen och det andra talet är rankingnumret för den spelare som förlorade matchen. Observera att samma par av spelare kan ha mötts flera gånger med samma eller olika resultat.
Utdata
Programmet ska skriva ut ett heltal: längden av den kortaste vinstkedjan från spelare k upp till toppen, eller talet -1 (alltså minus ett) om ingen sådan kedja finns.
Exempel: Indata
5 4 8 1 3 2 5 4 2 5 2 3 4 5 1 2 3 1 4
Exempel: Utdata
3
Lösning
[redigera]Vi börjar med att konvertera indatan från ett antal matcher till en lista över vilka spelare varje person vunnit över. Denna lista heter nod i exempellösningen nedan, där nod[i][j] är sann om spelare i vunnit över spelare j. Vi skapar även en lista där vi sparar den kortaste kedjan från varje spelare till startspelaren. Denna lista heter dist i exempellösningen. Vi löser sedan uppgiften med bredden-först-sökning genom att successivt gå igenom vilka spelare vi kan nå med en länk, med två länkar o.s.v. ända tills vi når toppspelaren eller vi inte längre kan nå några nya spelare. För att åstadkomma detta börjar vi med att markera dist[startSpelaren] = 0. Vi går sedan igenom alla spelare startSpelaren vunnit över och markerar dem med 1 i dist-listan. Därefter går vi igenom alla spelare som blev markerade med 1 och loopar igenom alla deras vinster. Kommer vi till en ny spelare som vi inte redan markerat, markerar vi denna spelare med 2. Sedan upprepar vi samma procedur för alla spelare som blev markerade med 2 och markerar alla nya spelare vi kan nå med 3. När vi markerar dist[0], alltså toppspelaren, kan vi avsluta loopen eftersom vi då garanterat vet hur kort den kortaste länken är. Om vi kommer till en punkt där vi inte längre kan markera några nya spelare kan vi också avsluta loopen eftersom vi då vet att det inte finns någon kedja alls som når dist[0].
Exempellösningen fungerar så här:
- Läs in matcherna och konvertera dem till en vinstlista
- Markera dist[startSpelaren] = 0 och sätt cStep = 0
- Markera alla nya spelare vi kan nå med cStep + 1 steg
- Öka cStep med ett
- Upprepa proceduren från steg 3 tills vi når toppspelaren, eller tills vi inte längre markerar nya spelare
- Skriv ut svaret
Exempellösning i C++:
//Onlinekvalet 2007 //Uppgift 5 - Tennisklubben #include <iostream> using namespace std; #define INF -1 //värde som motsvarar omarkerad int main(void){ int i, j, cStep; int nodFrom, nodTo; int nMatch, nPlayer, startPlayer; bool nod[100][100]; //vilka spelare varje person har vunnit emot int dist[100]; //dist[i] anger hur många steg som krävs från startSpelaren till spelare nr i bool running, done; //----------- Initiera nod-listan och dist-listan ------------ for(i = 0; i <= 99; i++){ //loopa igenom varje nod for(j = 0; j <= 99; j++){ //loopa igenom varje länk nod[i][j] = false; //defaultvärde } } for(i = 0; i <= 99; i++) dist[i] = INF; //defaultvärde är INF //---------------------------------------------------------------------------- //-------------------------- Läs in datan ------------------------------- cin >> nPlayer >> startPlayer >> nMatch; //läs in antalet spelare, startSpelaren och antalet matcher startPlayer--; //vi börjar på noll i indexet och inte ett for(i = 1; i <= nMatch; i++){ //loopa igenom varje match cin >> nodFrom >> nodTo; //läs in vinnaren och förloraren nod[nodFrom - 1][nodTo - 1] = true; //spara att nodFrom vunnit över nodTo } //-------------------------------------------------------------------------------- dist[startPlayer] = 0; cStep = 0; //noll steg för att nå oss själva running = true; done = false; if(startPlayer == 0) running = false; //vi är redan klara //----------------------- Gå steg för steg igenom de spelare vi kan nå ------------------------ while(running){ running = false; //blir sant om vi kommer till minst en ny spelare for(i = 0; i <= nPlayer - 1; i++){ //loopa igenom alla spelare if(dist[i] == cStep){ //en spelare vi precis nått for(j = 0; j <= 99; j++) if(nod[i][j] && dist[j] == INF){ //undersök vilka nya spelare vi kan nå ifrån spelare i... dist[j] = cStep + 1; //...vi kan nå spelare j med cStep + 1 steg if(j == 0) done = true; //...vi har nått toppen och är klara! running = true; //...vi hittar fortfarande nya spelare } } } if(done == true) running = false; //vi behöver inte fortsätta ifall vi är klara cStep++; //vi har gått ett steg till } //------------------------------------------------------------------------------------------------------------------------ cout << dist[0] << "\n"; //printa antalet steg som krävdes return 0; }