Problem E
MGP
Til musikkonkurrencen MGP kan tilskuere sende SMS’er for at stemme på de $N$ deltagere. En gyldig stemme på deltager $i$ er en SMS der starter med teksten »Sang« efterfulgt af præcis ét mellemrum og et positivt heltal $i$ uden foranstillede nuller, hvor $1 \leq i \leq N$. Det er tilladt at skrive »Sang« med en vilkårlig kombination af store og små bogstaver. F.eks. er »SANG« og »SaNg« også gyldige måder at skrive »Sang« på, men »Snag« er ikke. Hvis SMS’en ikke er gyldig, svarer maskinen med »Ugyldig stemme!«.
Tilskuere (identificerede med unikke telefonnumre) kan stemme på så mange forskellige deltagere, som de har lyst til. Første gang, en tilskuer sender en gyldig stemme på den $i$’te deltager, modtager tilskueren svaret »Tak for din stemme paa <deltagernavn>.«. Men hver tilskuer kan kun stemme på samme deltager én gang. Når en tilskuer sender en gyldig stemme på den samme deltager mere end én gang, svarer maskinen med »Du har allerede stemt paa <deltagernavn>!«.
Desværre er stemmeoptællingsmaskinen gået i stykker. Kan du hjælpe med at lave en ny?
Indlæsning
På første linje af indlæsningen er der to heltal $N$ og $Q$, hvor $N$ er antallet af deltagere i MGP og $Q$ er antallet af modtagne SMS’er.
Derefter følger $N$ linjer, hvor den $i$’te linje angiver deltagernavnet for den $i$’te sang. Man kan kun deltage i MGP med én sang, så alle disse navne er forskellige.
Derefter følger $2 \cdot Q$ linjer. Hvert par af linjer indeholder en beskrivelse af en modtaget SMS. Den første linje indeholder afsenderens $8$-cifrede telefonnummer og den anden linje indeholder teksten fra SMS’en.
Udskrift
Skriv $Q$ linjer, hvor den $j$’te linje er det korrekte svar til den $j$’te SMS.
Garantier og delopgaver
Der gælder altid:
-
$1 \leq N \leq 10^5$
-
$1 \leq Q \leq 10^5$
-
Alle linjer indeholder kun cifre, engelske bogstaver (a-z og A-Z) og mellemrum.
-
Ingen linjer starter eller slutter med et mellemrum.
Opgaven er opdelt i delopgaver med stærkere garantier, som gør delopgaven nemmere at løse.
|
Delopgave |
Point |
Garanti |
|
$1$ |
$30$ |
$N \leq 1000, Q \leq 1000$ og SMS’en er garanteret gyldig |
|
$2$ |
$30$ |
$N \leq 1000, Q \leq 1000$ |
|
$3$ |
$40$ |
Ingen yderligere garantier |
| Sample Input 1 | Sample Output 1 |
|---|---|
2 3 Anne Gadegaard Razz 22222222 Sang 2 22222222 sang 1 22222222 SANG 2 |
Tak for din stemme paa Razz. Tak for din stemme paa Anne Gadegaard. Du har allerede stemt paa Razz! |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 2 Cool Kids 23456789 Sang 1 23456789 Sang 2 |
Tak for din stemme paa Cool Kids. Ugyldig stemme! |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 11 SEB 23456789 Sang 2 23456789 Test 1 2 3 4 23456789 Sang sang 1 23456789 SEB 23456789 Sang 01 23456789 Sang SEB 23456789 Sang 1e0 23456789 Sanga 1 23456789 Sang1 23456789 Sang 0x1 23456789 Sang 1 1 |
Ugyldig stemme! Ugyldig stemme! Ugyldig stemme! Ugyldig stemme! Ugyldig stemme! Ugyldig stemme! Ugyldig stemme! Ugyldig stemme! Ugyldig stemme! Ugyldig stemme! Ugyldig stemme! |
| Sample Input 4 | Sample Output 4 |
|---|---|
2 3 Anne Gadegaard Razz 22222222 Sang 2 22222220 sang 1 22222221 SANG 2 |
Tak for din stemme paa Razz. Tak for din stemme paa Anne Gadegaard. Tak for din stemme paa Razz. |
