Detta är ett interaktivt flerstegsproblem (multi-pass). Kom ihåg att tömma utdatabufferten (flush) efter varje utskrift. För att tömma din utdata kan du använda:
fflush(stdout)ellercout.flush()i C/C++;System.out.flush()i Java och Kotlin;sys.stdout.flush()i Python.
Spelets koncept, illustrerat av ChatGPT.
I det klassiska online-matchningsspelet avslöjas kanterna i en graf en efter en. Varje gång en kant visas måste du omedelbart och oåterkalleligt bestämma om du vill inkludera den i din matchning. Ditt mål är att se till att inga två valda kanter delar ett hörn samtidigt som du maximerar det totala antalet valda kanter.
Du är en ambitiös datavetare, hungrig efter berömmelse. Som du mycket väl vet är det bevisligen omöjligt att med hög sannolikhet hitta en maximal matchning i en online-miljö — till och med för de enklaste grafklasserna som bipartita grafer. Men där andra ser ett fundamentalt hinder ser du en chans till ära. Idag hävdar du att du har knäckt det länge öppna problemet för träd och är redo att presentera din banbrytande algoritm för världen.
Det finns bara ett problem: igår upptäckte du en bugg i ditt bevis, och du har fortfarande ingen aning om hur du ska laga den. Ovillig att lämna rampljuset bestämmer du dig för att förvandla din demonstration till en magishow — din assistent, gömd bakom kulisserna, kommer att sända en liten ledtråd om hela trädet med $n$ hörn innan spelet börjar.
Din ursprungliga plan var enkel: låt din assistent skicka svaret på varje kantfråga direkt. För detta ändamål har du installerat en hemlig hörsnäcka som kan ta emot en enda binär sträng av längd $(n - 1)$. Men publiken är skeptisk till ditt "genombrott". För att förhindra allt förhandsarrangerat fusk kräver de att kanterna presenteras i en likformigt slumpmässig ordning — en som varken du eller din assistent kan förutse eller kontrollera.
Scenen är redo. Strålkastarna är riktade mot dig. Bevisa nu ditt påstående — utan att byta kanal.
Interaktionsprotokoll
Din lösning körs två gånger på varje test. I rundan prepare agerar din lösning som assistenten. I rundan play agerar din lösning som du, magikern. I båda rundorna utvärderas din lösning som en interaktiv procedur.
Förberedelserunda (Prepare Round)
Den första raden i indatan innehåller ordet prepare. Den andra raden innehåller ett heltal $n$ ($2 \le n \le 500$) — antalet hörn. De följande $(n - 1)$ raderna innehåller var och en två heltal $u$ och $v$ ($1 \le u, v \le n$, $u < v$), som betecknar en oriktad kant mellan $u$ och $v$ i trädet.
Du måste skriva ut en rad som innehåller en binär sträng $s$ av exakt längd $(n - 1)$ bestående enbart av tecknen 0 och 1. Detta är strängen som sänds till den andra rundan (play). Om din utdata inte följer det önskade formatet får du bedömningen Wrong Answer.
Spelrunda (Play Round)
Din lösning kommer att startas om inför rundan play.
Den första raden innehåller ordet play. Den andra raden innehåller heltalet $n$. Den tredje raden innehåller den binära strängen $s$ exakt så som du skrev ut den i rundan prepare.
Därefter startar spelet med $(n - 1)$ drag. I varje drag ges en rad som innehåller två heltal $u$ och $v$ ($1 \le u, v \le n$, $u < v$). Som svar ska du skriva ut en rad som innehåller antingen take eller ignore. Alla kanter från den första rundan kommer att ges exakt en gång, och ordningen på kanterna väljs likformigt slumpmässigt bland de $(n - 1)!$ möjliga permutationerna.
Om en utskrift sker i ogiltigt format avslutas spelet omedelbart utan vidare information från interaktorn.
Utvärdering av korrekthet
Låt $M$ vara mängden av kanter som din lösning tar. Det betraktas som godkänt om inget hörn är incident med mer än en tagen kant och $|M| = |M^*|$, där $M^*$ är den maximala matchningen i grafen.
Det finns exakt $50$ tester, exklusive exempeltesterna. För att klara problemet måste din lösning vara korrekt på alla tester, inklusive exempeltesterna.
Alla blandningar garanteras vara fastställda innan lösningens utdata tas emot. Slumpmässigheten är fixerad för varje test genom att fröet (seed) till en pseudoslumptalsgenerator är fixerat.
Ett testverktyg tillhandahålls för att hjälpa dig att utveckla och testa din lösning.
Exempel
Exempel 1, Omgång 1
Indata
prepare 3 1 2 1 3
Utdata
00
Exempel 1, Omgång 2
Indata
play 3 00 1 3 1 2
Utdata
take ignore
Förklaring av Exempel 1
Eftersom $|M^*| = 1$ är det godkänt att ta vilken kant som helst, och ledtråden kan vara godtycklig.