Hide

Problem D
Kan være reserveret

/problems/dpop23.kanvarereserveret/file/statement/da/img-0001.jpg
Sæde 61 og 63 i et IC3-tog.

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

Please log in to submit a solution to this problem

Log in