P5486 [JLOI2010] World Cup House Rental

The South Africa World Cup organizing committee designated some hotels that could provide rooms for fans to rent during this period, and one of them is called Avatar. Since the number of rooms in the Avatar hotel does not exceed $26$, they can be represented by $26$ uppercase letters. One day, Manager Liu’s phone rang. He received a request to rent a room from the night of June 12 to noon of June 19. He checked the reservation table, but did not find any single room that could satisfy the request directly. For example, the owner might need to stay in their own room for personal reasons, so the tourist has to stay in one room for a few days and then move to another room for the remaining days. After carefully checking the reservation table, he told the traveler: “I will place you in $B$ for $3$ days first, and then arrange you to stay in $F$ for the rest of the trip.” Your goal is to minimize the number of times the traveler needs to move from one room to another. Note that in the hotel’s billing, the time from one night to the next day at noon is always counted as one day.

The input contains multiple test cases. For each test case, the first line contains two integers $M$ and $N$. $M$ is the number of days on the schedule, and $N$ is the number of units (rooms). The number of days does not exceed $100$, counted starting from $1$. The number of units does not exceed $26$, labeled starting from $A$. The next $M$ lines each contain $N$ letters, indicating whether the unit has already been rented from the night of day $i$ to noon of the next day. `X` means rented, and `O` means not rented. The last line contains two integers $s, t$, meaning the traveler checks in on the night of day $s$ and ends the trip at noon of day $(t+1)$. $1\leq s

For each test case, first print the testdata number, followed by a colon and a blank line. Then output a plan with the minimum number of room changes, using the following format on each line: `: -` Here, `` is the unit label, and `` and `` are the times when the traveler moves into and leaves that unit, respectively. Note that if there are multiple plans with the minimum number of room changes, output the lexicographically smallest plan. If no such plan exists, output one line: `Not available`. Print a blank line between every two test cases. Do not add an extra blank line at the end of the output.

Translated by ChatGPT 5