Problem D
Kan være reserveret
Siden 1989 informerer pladsresersvationssystemet i danske intercitytog den rejsende om pladsens reservationer ved hjælp af en lille elektronisk skærm over hvert sæde. Hvis pladsen er optaget ved en givet station, angiver skærmen den nuværende reservation. Hvis pladsen er ledig ved en givet station, angiver skærmen den næste reservation i rutens retning. Hvis der findes yderligere mindst en reservation efter den angivne reservation, markerer skærmen dette med en lille stjerne »*« efter den angivne reservation. Hvis reservationssystemet ikke kender til reservationer for den pågældende plads på resten af ruten, står der »KAN VÆRE RESERVERET«.
Givet en liste over stationer og reservationer, angiv skærmens indhold ved en given station.
Indlæsning
På første linje står antallet $s$ af stationer. Herefter følger $s$ linjer med rutens stationsnavne, i rækkefølge med endestationen til sidst. Alle stationsnavne er forskellige og består af højst $15$ tegn og er skrevet med store danske bogstaver, mellemrum og punktum.
På næste linje står antallet $r$ af reservationer. Herefter følger $r$ linjer med gyldige reservationer; en reservation indeholder to stationsnavne adskilte af bindestreg »-«. Reservationen $a$-$b$ betyder, at pladsen er optaget fra og med station $a$; reservationen ophører at gælde ved station $b$. Der kan altså findes en anden reservation af formen $b$-$c$. Det er givet, at $a\neq b$ og at $a$ forekommer før $b$ i stationslisten. Linjerne med reservationer kan komme i hvilken som helst rækkefølge. Der er ingen overlappende reservationer eller gentagelser.
På næste linje står antallet $q$ af forespørgsler. Herefter følger $q$ linjer med forespørgsler, hver bestående af et stationsnavn. Forespørgslerne kan komme i hvilken som helst rækkefølge, men indeholder ingen gentagelser.
Udskrift
Skriv $q$ linjer, en for hver forespørgsel: Hvad skal der stå på reservationsoversigten, når man betræder toget ved den pågældende station?
Garantier og delopgaver
Der gælder $3\leq s\leq 10^4$, $1\leq r\leq 9999$ og $1\leq q\leq 10^4$.
Opgaven er opdelt i delopgaver med stærkere garantier, som gør delopgaven nemmere at løse.
|
Delopgave |
Point |
Garanti |
|
$1$ |
$22$ |
Ruten er »KØBENHAVN H.«, »ODENSE«, »ÅRHUS H.«, og $q=1$. |
|
$2$ |
$21$ |
Ruten er »KØBENHAVN H.«, »ODENSE«, »ÅRHUS H.«. |
|
$3$ |
$20$ |
$q\leq 10$, $r\leq 5$, $s\leq 10$. |
|
$4$ |
$19$ |
$r=1$ |
|
$5$ |
$18$ |
Ingen yderligere garantier |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 KØBENHAVN H. ODENSE ÅRHUS H. 1 KØBENHAVN H.-ODENSE 1 ODENSE |
KAN VÆRE RESERVERET |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 KØBENHAVN H. ODENSE ÅRHUS H. 2 KØBENHAVN H.-ODENSE ODENSE-ÅRHUS H. 3 KØBENHAVN H. ODENSE ÅRHUS H. |
KØBENHAVN H.-ODENSE * ODENSE-ÅRHUS H. KAN VÆRE RESERVERET |
| Sample Input 3 | Sample Output 3 |
|---|---|
6 KØBENHAVN H. ROSKILDE ODENSE ÅRHUS H. AALBORG FREDERIKSHAVN 3 KØBENHAVN H.-ODENSE AALBORG-FREDERIKSHAVN ODENSE-ÅRHUS H. 6 KØBENHAVN H. ROSKILDE ODENSE ÅRHUS H. AALBORG FREDERIKSHAVN |
KØBENHAVN H.-ODENSE * KØBENHAVN H.-ODENSE * ODENSE-ÅRHUS H. * AALBORG-FREDERIKSHAVN AALBORG-FREDERIKSHAVN KAN VÆRE RESERVERET |
