SCIENCE - Science
Welcome, ladies and gentlemen, to Aperture Science. Astronauts, war heroes, Olympians -- you're here because we want the best, and you are it. That said it's time to make some science.
Now I want each of you to stand on one of these buttons. Well done, we're making great progress here. Now let's do it again. Oh come on, don't stand on the same button. Move people! No, no, that button's only for the astronauts, you know who you are. What?! You say you can't do everything I ask. Ok let's start over. You there, the Olympian, figure out how many times we can do this. And make it quick, we have a lot more science to get through.
Input
The first line will contain N (2 ≤ N ≤ 200) giving the number of people (and the number of buttons) in the experiment. The next N lines will contain N characters each. If the jth character of the ith line is 'Y' it indicates that the ith person can stand on the jth button (it is 'N' otherwise). The last line of input will be a 0.
Output
If it is impossible to get everyone on the buttons at once output "NO SCIENCE" (quotes for clarity). Otherwise first output K, the maximum number of times everyone can be standing on buttons such that nobody stands on the same button more than once. After that output K lines. Each line should contain N integers separated by a space where the ith integer describes who is on the ith button. All of the lines should be valid and none of them should put the same person on the same button. If there are multiple solutions, output any of them.
Examples
Input: 3
YYY
NYY
YNY Output: 2
1 2 3
3 1 2
Input: 2
YN
YN Output: NO SCIENCE
hide comments
Mark Gordon:
2015-02-02 16:31:07
@Wesley: Yes, it appeared in Chicago's 2012 (I've listed it now). This version has larger constraints and is significantly harder, though. (Also, I am the original author of this problem)
|
|
Wesley May:
2015-02-02 16:31:07
This problem is from the 2012 University of Chicago Invitational Contest (http://icpc.cs.uchicago.edu/invitational2012/_static/ucipc2012-problems.pdf) |
|
Mark Gordon:
2015-02-02 16:31:07
Any solution is accepted by a custom judge. Your example would get AC. |
|
Francky:
2015-02-02 16:31:07
Is there any order for the answers, or any order is accepted by a custum judge ?
|
Added by: | Mark Gordon |
Date: | 2013-04-02 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | 2012 University of Chicago Invitational Contest (but with harder constraints) |