1315 . Gungodman's New Job
TopCoder
Description
Gungodman is a busy programar. One day, he got a new job. The job is to arrange the school timetable for an elementary school. At first he felt that it's such an easy job, so he completely ignored this job. After a few day, however, he
suddenly found that the deadline is tomorrow!!!
Therefore he ask you for help and of course, you agreed becuase you are a good man. A Goodgunman, in fact.
The detail of the job is as follow:
A week have five weekdays, and of every day there're nine lessons(The j'th lesson of i'th day will be numbered (i-1)*9+j). There are n teachers in total(teachers will be numbered from 1 through n). The i'th teacher have to teach ai lessons (Σai = 45). However, every teacher have different available time. That is, a teacher can only teach on some of the 45 lessons, so he can only pick among those time that he is available for teaching.
Given you every teachers' available time,please print a valid arrangement of the timetable. If there are no valid arrangement, please print "Oops!".
Warn: 本題有 specialjudge
Input Format
First line contains a number T, denoting the number of testcases.
Each test case start with one line containing an integer n denoting the number of teachers. i'th line of the next n lines start with ai and li, where li denotes the number of i'th teacher's available period, then follows li number, denoting the li periods teacher ai is available.
T<=100
1<=n<=45
Σai = 45
1<=ai,li<=45
The available period for a teacher will be specified exactly once. (i.e. no period will appear more than one time in a teacher's available time list)
Output Format
For each testcase, if there is some valid arrangement, print 5 lines. Each line contain nine number separated by exact one space. The i'th number of j'th line denote the teacher's id who is arranged at i'th lesson of j'th day.
If we cannot find a valid arrangement, print "Oops!" in a line.
NOTE: The special judge is very strict! So You can't print redundant space or new line(i.e. no space is allowed at the end of line, and no extra new line at end of all outputs).
Sample Input 1
2 9 5 10 1 2 3 4 5 6 7 8 9 10 5 10 6 7 8 9 10 11 12 13 14 15 5 10 11 12 13 14 15 16 17 18 19 20 5 10 16 17 18 19 20 21 22 23 24 25 5 10 21 22 23 24 25 26 27 28 29 30 5 10 26 27 28 29 30 31 32 33 34 35 5 10 31 32 33 34 35 36 37 38 39 40 5 10 36 37 38 39 40 41 42 43 44 45 5 10 41 42 43 44 45 1 2 3 4 5 5 9 10 1 2 3 4 5 6 7 8 9 10 9 10 10 11 12 13 14 15 16 17 18 19 9 10 19 20 21 22 23 24 25 26 27 28 9 10 28 29 30 31 32 33 34 35 36 37 9 10 37 38 39 40 41 42 43 44 1 2
Sample Output 1
1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 Oops!
Hints
Problem Source
Migrated from old NTUJ.
dreamoon
Subtasks
| No. | Testdata Range | Score |
|---|