932 - Checking the N-Queens Problem

[adelar]

Hi friends,
someone have inputs and outputs AC to this problem?

thanks in advance.

[dreadlord]

Hello.

I wonder what corrected position should be given as output when there are more than one way to make the wrong input position to become correct.

For example, consider the following input:

8
00000000
000000X0
0000X000
0000000X
XX000000
000X0000
00000X00
00X00000

Which is not a valid position as there are two queens in the 5th row (starting from top). First row is free, and moving any of these two queens to the first row would give a valid position, so the following two outputs would be right:

Output #1:

NO
YES
X0000000
000000X0
0000X000
0000000X
0X000000
000X0000
00000X00
00X00000

Output #2:

NO
YES
0X000000
000000X0
0000X000
0000000X
X0000000
000X0000
00000X00
00X00000

Any clue about this?

Thank you in advance.

[Carlos]

if the description doesn't ask for a particular solution, you can output any of them.

[dreadlord]

WARNING:

Don't try to solve this problem with a Pascal program. I believe there is some problem with the I/O in Pascal with the input file. I tried the following extremely simple program:

Code: Select all

program hang932;

var
    TC, i, j : Integer;
    car : Char;

begin
    while eoln and not eof do readln; (* skip leading newlines *)
    readln (TC);
    i := 1;
    repeat
        j := 1;
        repeat
            car := '.';
            repeat
                if eoln then
                    readln
                else
                    read (car)
            until (car = '0') or (car = 'X');
        if j = TC then break;
            inc (j);
        until False;
    if i = TC then break;
        inc (i);
    until False;
    writeln ('NO');
    writeln ('NO')
end.

, which of course may not expect to get AC, but definitely shouldn't ever get Time Limit Exceeded, as it does. I get no problems when using this loops structure in my computer.

I believe this' something to do with the first readln(TC), as I get WA (as expected) when replacing the two outermost repeat-until loops by "for [ i | j ] := 1 to TC do". Maybe it gets zero for TC for some reason? Might this happen because the input text file contains some stranger line terminators, kind of DOS or so?

[RC's]

Is there only one test case for this problem ?
Does anybody have some I/Os ? I'm getting WA.

[RC's]

I just got AC...
It was because my program only handles one test case.. I don't know if we must read until end of file...

[dreadlord]

I just got AC...
It was because my program only handles one test case.. I don't know if we must read until end of file...

Do you mean that you got AC because you sent a version of your program that considers more that one input case??

If so, the problem description should be revised, because it says clearly that there is only one input case.

That could be a good explaination of why there are so few AC's...

[RC's]

I just change my program to handle more than one test case and I got AC..
If I'm not mistaken, it was the only change I made.
How about you ? Have you got AC as well ?

[dreadlord]

I just change my program to handle more than one test case and I got AC..
If I'm not mistaken, it was the only change I made.

Then, definitely the problem description is wrong and confusing.

How about you ? Have you got AC as well ?

Nope. So far I haven't modified my program to handle more than one test case, because I was (incorrectly) assuming that the problem description was right, as it usually is. I gave up with the problem when I made sure that my program was correct but still got WA (I supposed there were some kind of problem related to wrong text format in the input file). Now that you gave a reasonable explanation for this, I'll come back to this problem and will try it again but don't know when... Time is gold and I'm poor.

For the moment, could you please tell me how to find the end of the input? You stop when yo find zero, or something like that, for the board size, or you find EOF after the last test case with no further data afterwards?

Thank you,

[RC's]

I use like this to handle the input

Code: Select all

while (scanf("%i\n", &size) != EOF)
{
  ......
  ......
  for(i = 0; i < size; i++)
  {
        scanf(" %s ", board[i]);
        ........
        ........
  }
......
......
}

Hope you'll get AC soon

[dreadlord]

I use like this to handle the input

Code: Select all

...

Hope you'll get AC soon

Thank you for the tip and your good wishes.

[dreadlord]

Hope you'll get AC soon

Well, after modifying my program to consider more than one test case, I got AC.

It's certainly annoying to get stuck in one problem just because its description is clearly incorrect and confusing...

I shall complain about this.

Regards, and thank you again for the tip, Robin.

[RC's]

Congratulations, dreadlord...
Now you should try another problems.
Good luck

[dreadlord]

Hi friends,
someone have inputs and outputs AC to this problem?

thanks in advance.

Hi, adelar.

It's not a very large set of I/O, but could be helpful, so I drop them right here.

Input:

Code: Select all

8
0000X000
X0000000
0000X00X
00000X00
00000000
000000X0
0X000000
000X0000

8
X0000000
000000X0
0000X000
0000000X
0X000000
000X0000
00000X00
00X00000

8
X0000000
000000X0
0000X000
0000000X
000X0000
000X0000
00000X00
00X00000

5
0X000
X0000
000X0
0X000
0000X

1
X

5
00X00
X0000
000X0
0X000
0000X

       
8
X0000000
000000X0
0000X000
0000000X
000X0000
000X000X
00000000
00X00000

       
8
X0000000
000000X0
0000X000
0000000X
000X0000
000X0000
00000X00
00X00000

Output:

Code: Select all

NO
YES
0000X000
X0000000
0000000X
00000X00
00X00000
000000X0
0X000000
000X0000
YES
NO
YES
X0000000
000000X0
0000X000
0000000X
0X000000
000X0000
00000X00
00X00000
NO
YES
00X00
X0000
000X0
0X000
0000X
YES
YES
NO
NO
NO
YES
X0000000
000000X0
0000X000
0000000X
0X000000
000X0000
00000X00
00X00000

Hope it helps.

Regards,

[jurajz]

Thanks to RC's for his notice about more test cases. I have lot of WA's and when I made only one change - assuming more test cases, I have AC. The problem description should be revised for real...