시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 49 | 1 | 1 | 25.000% |
Finally Egypt has reached the FIFA World Cup for the first time since its last appearance in 1990!
In the world cup the teams are divided into groups, with 4 teams in each group, but in this problem we will generalize it and say the group will consist of N teams (numbered from 1 to N), and we will simulate the matches of just one group. The following are the rules of the groups stage (it’s a bit different than the actual rules):
You are given the results of the first N − 2 rounds of one group, and your task is to calculate for each team if they still have a chance to be qualified to the next round or if they are disqualified for sure no matter what.
Your program will be tested on one or more test cases. The first line of the input will be a single integer T (1 ≤ T ≤ 100) representing the number of test cases. Followed by T test cases.
Each test case starts with a line containing an integer N (4 ≤ N ≤ 1, 000) representing the number of teams followed by (N − 2) × (N/2) lines, which are the results of the first N − 2 rounds, each line is the result of one match.
Each match result line will start with 2 integers A and B separated by a space (1 ≤ A < B ≤ N), then another space and a character which will be either ‘W’ (means team A won), ‘L’ (means team B won) or ‘D’ (means the match ended in draw).
Within each test case, it’s guaranteed that each team will appear in exactly N − 2 matches, and no pair of teams will play more than once against each other.
For each test case print a single line containing a string of N characters, the first character is for team 1, the second character is for team 2 and so on. The character should be ‘1’ if the corresponding teams might still be qualified to the next round, or ‘0’ if that team is disqualified for sure no matter what.
2 4 1 2 W 3 4 W 1 4 W 2 3 L 6 1 2 D 1 3 D 1 4 D 1 5 D 2 3 D 2 4 D 2 6 D 3 5 D 3 6 D 4 5 D 4 6 D 5 6 D
1010 111111
In the first test case, teams 1 and 3 got 6 points so far, and teams 2 and 4 got 0 points. No matter what happens in the last round, teams 2 and 4 can’t be in the top 2 teams.
In the second test case, all matches ended in draw, so all teams still have a chance to be qualified.