Tävlingsprogrammering/Uppgifter/Bägare

Bägare

Algot och Ritma spelar ett spel. Algot är spelledaren och Ritma spelaren. Ritma har en bindel för ögonen så att hon inte ser vad Algot gör.

Spelet spelas med N bägare numrerade från 1 till N. Vid spelets början placerar Algot en boll i en av bägarna (Ritma vet inte vilken). Därefter utför Ritma ett antal drag, där ett drag består i att säga bokstaven 'A' eller 'B'. Varje gång Ritma säger en bokstav flyttar Algot bollen från bägaren till en annan (eventuellt den bägare där den redan befann sig). Bägaren som den flyttas till beror på bollens nuvarande position och draget som Ritma gjorde. Dvs, om bollen befinner sig i bägare K, så förflyttas den till antingen A_k eller B_k, där dessa funktioner är förutbestämda. Både Algot och Ritma känner till dessa funktioner.

Ritmas mål är att flytta bollen till bägare 1, oavsett var Algot placerade bollen i spelets början. Skriv ett program som hittar någon sekvens av bokstäver som Ritma ska säga för att få bollen till bägare 1 vid sekvensens slut. Notera att det inte räknas om bollen hamnar i bägare 1 innan sekvensens slut. Sekvensen får inte innehålla mer än 10 000 bokstäver.

Indata

Första raden innehåller ett heltal N (1 ≤ N ≤ 500), antalet bägare.

Därefter följer N rader innehållandes talen A_k och B_k. Den första av dessa rader motsvarare bägare 1, osv.

Du kan utgå ifrån att en lösning alltid kommer att finnas.

Utdata

En sekvens av bokstäverna A och B som leder till att bollen befinner sig i bägare 1 vid sekvensens slut.

Bedömning

I 10% av testfallen finns en sekvens på högst 20 tecken som gör att bollen alltid hamnar i den första bägaren.

Exempel 1: Indata

4
1 2
1 3
3 1
1 4

Exempel 1: Utdata

ABA

Exempel 2: Indata

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

Exempel 2: Utdata

ABABBBBABBB

Lösning

Istället för att låtsas som att vi inte vet i vilken bägare bollen från början befinner sig, kan vi anta att det finns en boll under var och en av de N bägarna. Målet blir att hitta en sekvens av drag som, när de är utförda över alla bollar, gör att samtliga bollar hamnar i den första bägaren vid sekvensens slut.

Vi börjar med ett enklare problem: antag att vi bara har två bollar som befinner sig i bägare x och y. Vi vill nu hitta en sekvens som gör att bollen både i x och y kommer hamnar i bägare 1. Vi löser detta problem bakifrån, dvs vi utgår ifrån att de två bollarna ligger i bägare 1. Hur kan de två bollarna ha leget tidigare för att ha hamnat här? Vi kollar vilka "A-drag" och vilka "B-drag" som båda gör att en boll hamnar i bägare 1. Då får vi fram nya positioner där vi i ett drag (antingen A eller B) har fått bollarna i bägare 1. Från dessa nya positioner söker vi vidare bakåt tills vi känner till hur vi, oberoende av de två bollarnas startposition, vet en sekvens som gör att de hamnar i bägare 1. Denna del av uppgiften är återigen en variant av en BFS-sökning.

Nu när vi vet hur vi reducerar 2 bollar till 1 (som dessutom hamnar i bägare 1) oberoende av startposition, kan vi applicera detta upprepade gånger för att gå från N bollar till N-1, till N-2 osv ända ner till 1 boll. I praktiken kommer reduktion ske mycket snabbare, då flera bollar snabbt hamnar i samma bägare bara man gör lite slumpmässiga drag. Om vi låter S vara mängden av bägaren där bollarna just nu befinner sig, väljer vi ut det par som det kräver minst drag för att nå bägare 1. Vi applicerar den sekvensen och flyttar runt alla bollar i mängden S så att vi får en ny mängd S'. Denna mängd kommer innehåller färre bollar än S. Så länge det finns fler än 1 boll kvar (eller om den enstaka bollen är i någon annan bägare än 1), så upprepar vi algoritmen. Till slut kommer alla bollar hamna i bägare 1. Det visar sig att man inte behöver bekymra sig över längden på den totala sekvensen, då den inte är i närheten av 10000 även när N=500.