Problem F
Knäcka lösenord

Katastrof! Programmeringsolympiadens final har börjat, men du har glömt inloggningen till din dator. Som tur är, så är du inte ett får som följer flocken. Du vägrar nämligen använda Windows och använder istället Progolymp-OS. Om du har glömt ditt lösenord i detta operativsystemet får du ledtrådar när du gör en gissning. Mer exakt, anta att lösenordet är $P$, och du gissar $G$. Då svarar systemet med

där $LCS(G,P)$ är längden på den längsta gemensamma delsekvsensen av $G$ och $P$. Den längsta gemensamma delsekvsensen av två strängar $G$ och $P$ är definierad på följande vis: låt oss beteckna alla delsekvenser av en sträng $S$ med mängden av alla strängar som man kan få genom ta bort noll eller flera bokstäver från $S$ samtidigt som man behåller den relativa ordningen av de kvarvarande bokstäverna. $LCS(G,P)$ är längden på den längsta strängen som förekommer i både $G$ och $P$:s delsekvenser.

Till exempel: om $P=$”abc” är dess delsekvenser {””, ”a”, ”b”, ”c”, ”ab”, ”ac”, ”bc”, ”abc”}. Om $G=$”ac” är dess delsekvenser {””, ”a”, ”c”, ”ac”}. Då är deras längsta gemensamma delsekvens ”ac”, och således är $LCS(G,P)=2$.

Några fler exempel: längsta gemensamma delsekvsensen av ”aggtab” och ”gxtxayb” är ”gtab”. Därmed är $LCS($”aggtab”, ”gxtxayb”$) = 4$. Två till exempel är att $LCS($”abc”, ”cba”$) = 1$ och $LCS($”po”, ”trakigt”$) = 0$.

Du får nu göra upp till 10000 gissningar innan systemet låser sig. Varje gissning består av att du ger din dator $G$, och den svarar med $LCS(G,P)$. Dessutom vill du helst använda få gissningar så att du kan komma tillbaka in i tävlingen så snart som möjligt.

Interaktion

Ditt program ska först läsa in två heltal $N$ och $K$ ($1 \leq N \leq 100$, $1 \leq K \leq 26$): antalet bokstäver i lösenordet och hur många unika bokstäver det kan innehålla. Mer exakt består lösenordet $P$ av exakt $N$ stycken bokstäver valda från de $K$ första små bokstäverna i alfabetet.

För att göra en gissning ska du skriva ut en rad på formatet ? G. $G$ måste tillfredställa $1 \le |G| \le N$ och får endast innehålla bokstäver bland de $K$ första små bokstäverna i alfabetet. ($1 \le |G| \le N$), Programmet ska sedan läsa in ett heltal, $LCS(G,P)$.

När du ska göra din slutgiltiga gissning, skriv ut en rad med tecknet !, och sedan en sträng av längd $N$, din gissning av lösenordet. Efter detta ska ditt programmet avslutas och inget mer ska skrivas ut. Denna gissningen räknas inte in i gränsen av 10000 gissningar.

Det är garanterat att strängen $P$ i varje testfall är bestämd på förhand och inte ändras adaptivt i respons till dina mätningar. Det finns inga garantier på $P$ såsom att det är ett riktigt ord eller dylikt, då det är ett starkt lösenord.

Se till att flusha outputen efter varje utskrivning, annars kan du få Time Limit Exceeded. I C++ kan detta göras med exempelvis cout << flush; eller fflush(stdout);, i Python görs detta automatiskt när du använder input(), men annars behöver man använda sys.stdout.flush(), och i Java med System.out.flush();.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. Om du misslyckas med att hitta lösenordet i något testfall får du noll poäng för gruppen det tillhör. Annars, låt $g$ vara största antalet gissningar du använt för att hitta lösenorden i en viss testfallsgrupp. Om gruppen är värd $P$ poäng får du då

poäng för den gruppen. Du får 100 poäng på hela problemet om du aldrig använder mer än 666 gissningar för ett testfall.

Tabellen nedan visar värdet på $\frac{666}{g}$ avrundat nedåt för olika antal gissningar.

För testfallsgrupperna håller följande:

Förklaring av exempelfall 1

Det hemliga lösenordet är bbacba. Notera att interaktionen inte visar en rimlig strategi, utan visar endast formatet.

6 3

? ab

2

? bacb

4

? babb

3

! bbacba