|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|7 초||512 MB||8||7||6||85.714%|
In the city of RedBlue, every pair of buildings is connected by a road, either red or blue. To switch from travelling along red roads to blue roads or vice versa costs one ticket. The length of a route is the number of buildings that are visited. For example, the following route has a length of five and costs one ticket.
1 — 2 — 3 — 4 — 3
If we wanted to travel on a blue road again after visiting vertex 3 for the second time, we would need another ticket, for a total of two tickets:
1 — 2 — 3 — 4 — 3 — 2
You are a travelling salesperson visiting the city of RedBlue, and you wish to visit each building at least once, while minimizing repeated visits of the same buildings. You have not yet decided which building you are starting your route from, so you would like to plan out all possible routes. Furthermore, you only have access to one ticket. For each building, you would like to find a route of minimum length that begins at that building, visits all the buildings at least once, and uses at most one ticket.
The first line will contain a single integer N (2 ≤ N ≤ 2 000), the number of buildings in RedBlue.
Lines 2 to N each contain a string, with line i containing the string Ci, representing the colours of the roads connected to building i. The string Ci = Ci,1Ci,2...Ci,i-1 has a length of i-1 and consists only of the characters
B. If Ci,j is R, then the road between buildings i and j is red. Otherwise, it is blue.
Output 2N lines. Lines 2i-1 for 1 ≤ i ≤ N should contain a single integer Mi, representing the length of the travel plan starting at building i. Lines 2i for 1 ≤ i ≤ N should each contain Mi space separated integers, describing the order in which you visit the buildings, starting at building i.
For every one of your travel plans, a score is computed. Let Ki be the length of the optimal route starting at each building, and let Mi be the length of your route. If Mi is greater than 2Ki, then your score will be 0, and you will receive a verdict of Wrong Answer. If Mi is equal to Ki, then your score will be 25. Otherwise you will a receive a score of ⌈8 + 8 × (2Ki - Mi)/(Ki - 1)⌉. Your score for the test case is the minimum score for each travel plan.
If any of your plans are invalid, your score will be 0, and you will receive a verdict of Wrong Answer.
Your submission’s score is the minimum score over all test cases.
4 R RR BRB
5 1 4 2 1 3 6 2 3 1 2 3 4 5 3 1 2 3 4 4 4 3 1 2