程序设计在线评测(Online Judge)


问题 1060. -- 2010欧洲西南分区赛:Fake scoreboard

1060: 2010欧洲西南分区赛:Fake scoreboard

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 0
[提交][状态][讨论版]

题目描述

As you know, after the award ceremony of SWERC it is customary to publish a complete scoreboard
with detailed information on the submissions and verdicts received. However, due to the buggy contest
management system, most of the relevant data are not being recorded today. Clearly such state of a airs
fails to meet the high standards we are committed to, so the judges have resolved to make up the rest of the
data based on whatever shred of information left, and hope contestants are unable to tell the di erence. To
make our lives even simpler, we kindly ask you to provide a solution for us, or else today's scoreboard will
remain forever veiled in mystery (even the fake one).
What we will know by the end of the contest is the number T of teams, the number P of problems, and
the number of accepted submissions by each team. From the number and colour of balloons
oating around
on the premises we will also be able to infer how many teams solved each of the problems. Your task is to
gure out which teams solved which problems.
Our counting skills are not up to par, so your program should be able to detect when the data we
collected must be wrong (see sample input 1). Otherwise you should output a possible solution, represented
as a sequence of T strings of P characters each, in the following way. Both problems and teams are assigned
with distinct integers, from 1 to P and 1 to T, respectively. For team number i (1  i  T), write the string
on alphabet N,Y such that its j-th (1  j  P) character is Y if the team managed to get problem j accepted,
and N otherwise. For example, the following three strings form a solution to the second sample case, where
the score of each of three teams is 2; 1; 2, and the count of accepted submissions for each of three problems
is 1; 2; 2:
        NYY
        NNY
        YYN
There is at least one other solution, namely
        NYY
        NYN
        YNY
When several solutions are possible we ask you to supply the one giving rise to the lexicographically
smallest string, when each of the T rows are concatenated in order. In the example above we prefer the rst
solution, since NYYNNYYYN comes before NYYNYNYNY in lexicographical order. (String S comes before S0 in
lexicographical order if the rst di erent character between the two is N in S but Y in S0).

输入

Each input case is described by three lines:
The rst contains two space-separated integers T (the number of teams) and P (the number of problems),
with 1  T; P  80. The second contains T space-separated integers between 0 and 90 (inclusive), the i-th of
which indicates the number of problems solved by team i. The third (and last) line has P integers between
0 and 90, the j-th of which describes the number of teams successfully solving problem j.
Di erent input cases are separated by a blank line. The last line of the input le will be 0 0.

输出

If the input data has a solution, print T lines of P characters each, depicting the lexicographically smallest
solution as explained above. Otherwise output a single line with the word Impossible. In any case a blank
line should separate outputs for di erent test cases.

样例输入

2 2
1 2
1 1

3 3
2 1 2
1 2 2

3 5
3 3 1
3 1 1 0 2

0 0

样例输出

Impossible

NYY
NNY
YYN

YNYNY
YYNNY
YNNNN

提示

来源

[提交][状态][讨论版]