VIRTUAL JUDGE | Recent Contest | F.A.Qs | Forum | Home | ProblemSet | Status | Ranklist | Contest | Login | Register | Exam |
---|

Submit: 12 Solved: 0

[Submit][Status][Forum]

So many students are interested in participating in this year's regional programming contest that we have decided to arrange a screening test to identify the most promising candidates. This test may include as many as 100 problems drawn from as many as 20 categories. I have been assigned the job of setting problems for this test. At first the job seemed to be very easy, since I was told that I would be given a pool of about 1,000 problems divided into appropriate categories. After getting the problems, however, I discovered that the original authors often wrote down multiple category-names in the category fields. Since no problem can used in more than one category and the number of problems needed for each category is fixed, assigning problems for the test is not so easy.

The input file may contain multiple test cases, each of which begins with a line containing two integers,*n*_{k} and
*n*_{p},
where *n*_{k} is the number of categories and is the number of problems in the pool. There will be between 2 and 20 categories and at most 1,000 problems in the pool.
The second line contains *n*_{k} positive integers, where the ith integer specifies the number of problems to be included in category i ( 1<=i<=*n*_{k}) of the test. You may assume that the sum of these nk integers will never exceed 100. The jth ( 1<=j<=*n*_{p}) of the next *n*_{p} lines contains the category information of the jth problem in the pool. Each such problem category specification starts with a positive integer specifying the number of categories in which this problem can be included, followed by the actual category numbers.
A test case containing two zeros for *n*_{k} and *n*_{p} terminates the input.

For each test case, print a line reporting whether problems can be successfully selected from the pool under the given restrictions, with 1 for success and 0 for failure.
In case of successful selection, print *n*_{k} additional lines where the ith line contains the problem numbers that can be included in category i. Problem numbers are positive integers not greater then *n*_{p} and each two problem numbers must be separated by a single space. Any successful selection will be accepted.

3 15 3 3 4 2 1 2 1 3 1 3 1 3 1 3 3 1 2 3 2 2 3 2 1 3 1 2 1 2 2 1 2 2 1 3 2 1 2 1 1 3 1 2 3 3 15 7 3 4 2 1 2 1 1 1 2 1 2 1 3 3 1 2 3 2 2 3 2 2 3 1 2 1 2 2 2 3 2 2 3 2 1 2 1 1 3 1 2 3 0 0

1 8 11 12 1 6 7 2 3 4 5 0

HOME Back

한국어 中文 English

All Copyright Reserved 2008-2010 SDIBT TEAM

GPL2.0 2003-2010 HUSTOJ Project TEAM

Anything about the Problems, Please Contact Admin:admin