Questo è un problema interattivo a più passaggi (multi-pass). Ricorda di svuotare il buffer di output (flush) dopo ogni stampa. Per svuotare l'output puoi usare:
fflush(stdout)ocout.flush()in C/C++;System.out.flush()in Java e Kotlin;sys.stdout.flush()in Python.
Il concetto del gioco, illustrato da ChatGPT.
Nel classico gioco di online matching (accoppiamento online), gli archi di un grafo vengono rivelati uno alla volta. Ogni volta che viene mostrato un arco, devi decidere immediatamente e irrevocabilmente se includerlo nel tuo accoppiamento. Il tuo obiettivo è assicurarti che nessuna coppia di archi scelti condivida un vertice, massimizzando al contempo il numero totale di archi selezionati.
Sei un informatico ambizioso, assetato di fama. Come ben sai, trovare un accoppiamento massimo in un contesto online è dimostratamente impossibile con alta probabilità — persino per le classi di grafi più semplici come i grafi bipartiti. Eppure, là dove gli altri vedono una barriera fondamentale, tu vedi un'opportunità di gloria. Oggi sostieni di aver risolto l'annoso problema aperto per gli alberi e sei pronto a svelare al mondo il tuo algoritmo rivoluzionario.
C'è solo un problema: ieri hai scoperto un bug nella tua dimostrazione e non hai ancora idea di come risolverlo. Non volendo rinunciare ai riflettori, decidi di trasformare la tua dimostrazione in uno spettacolo di magia: il tuo assistente, nascosto dietro le quinte, trasmetterà un piccolo suggerimento sull'intero albero con $n$ vertici prima che il gioco abbia inizio.
Il tuo piano originale era semplice: far inviare direttamente all'assistente la risposta per ciascuna richiesta di arco. A tal fine, hai installato un auricolare segreto in grado di ricevere una singola stringa binaria di lunghezza $(n - 1)$. Ma il pubblico è scettico riguardo alla tua "scoperta". Per impedire qualsiasi trucco concordato in anticipo, pretende che gli archi vengano presentati in un ordine scelto in modo uniformemente casuale — un ordine che né tu né il tuo assistente potete prevedere o controllare.
Il palco è pronto. I riflettori sono puntati su di te. Ora dimostra la tua affermazione — senza cambiare canale.
Protocollo di Interazione
La tua soluzione viene eseguita due volte su ciascun test. Nel round prepare, la tua soluzione agirà come l'assistente. Nel round play, la tua soluzione agirà come te, il mago. In entrambi i round, la tua soluzione sarà valutata come una procedura interattiva.
Round di Preparazione (Prepare Round)
La prima riga dell'input contiene la parola prepare. La seconda riga contiene un intero $n$ ($2 \le n \le 500$) — il numero di vertici. Le successive $(n - 1)$ righe contengono ciascuna due interi $u$ e $v$ ($1 \le u, v \le n$, $u < v$), che indicano un arco non orientato tra $u$ e $v$ nell'albero.
Devi stampare una riga contenente una stringa binaria $s$ di lunghezza esattamente $(n - 1)$ composta esclusivamente dai caratteri 0 e 1. Questa è la stringa trasmessa al secondo round (play). Se il tuo output non rispetta il formato richiesto, riceverai il verdetto Wrong Answer.
Round di Gioco (Play Round)
La tua soluzione verrà riavviata per il round play.
La prima riga contiene la parola play. La seconda riga contiene l'intero $n$. La terza riga contiene la stringa binaria $s$ esattamente come l'hai stampata nel round prepare.
Dopodiché, il gioco inizia con $(n - 1)$ turni. In ciascun turno verrà fornita una riga contenente due interi $u$ e $v$ ($1 \le u, v \le n$, $u < v$). Come risposta, devi stampare una riga contenente take oppure ignore. Tutti gli archi del primo round verranno forniti esattamente una volta, e l'ordine degli archi è scelto in modo uniformemente casuale tra le $(n - 1)!$ permutazioni possibili.
Qualora venga prodotto un output in un formato non valido, il gioco terminerà immediatamente senza ulteriori informazioni dall'interattore.
Valutazione della Correttezza
Sia $M$ l'insieme degli archi scelti dalla tua soluzione. È considerato accettabile se nessun vertice è incidente a più di un arco scelto e $|M| = |M^*|$, dove $M^*$ è l'accoppiamento massimo del grafo.
Ci sono esattamente $50$ test, esclusi i test di esempio. Per superare il problema, la tua soluzione deve essere corretta su tutti i test, inclusi i test di esempio.
Si garantisce che tutti i mescolamenti sono fissati prima di ricevere l'output della soluzione. La casualità è fissata per ciascun test, implementata fissando il seme (seed) di un generatore di numeri pseudocasuali.
È fornito uno strumento di test per aiutarti a sviluppare e testare la tua soluzione.
Esempio
Esempio 1, Passaggio 1
Input
prepare 3 1 2 1 3
Output
00
Esempio 1, Passaggio 2
Input
play 3 00 1 3 1 2
Output
take ignore
Spiegazione dell'Esempio 1
Poiché $|M^*| = 1$, prendere qualsiasi arco è accettabile e il suggerimento può essere arbitrario.