not understanding this problem

[saltpro15]

hey guys,

I'm getting back into the SPOJ questions, can't seem to understand what this one is asking, it can be found here

a palace of size N when N = 3 should be like

[ ] [ ] [ ]
[ ] [ ] [ ]
[ ] [ ] [ ]

with a total of 9 rooms right? so why is the output 16?

[DanielG]

maybe the N=3 is referring to the number of walls on each side?? so the number of rooms is (n+1)^2???

[saltpro15]

oh maybe, thanks Daniel

[saltpro15]

hmm, attempted, returned a wrong answer, there must still be a problem somewhere

[Tony]

The wording is ambiguous. 16 refers to the number of different ways people can be arranged inside a palace (combinatorics problem), not the number of rooms (output = n^2 makes it too simple). But I don't see where the number of people would be specified.

[saltpro15]

problem abandoned for now, I'll just try some other problems, these are good ECOO practice

[Analysis Mode]

If you're stuck on a problem, the SPOJ Forums are your best friend.

[saltpro15]

c++:

#include <iostream> #include <fstream> using namespace std; int main() { ifstream fin ("in.txt"); ofstream fout ("debug.txt"); int tc; int walls; fin >> tc; for (int a = 0; a < tc; a++); { fin >> walls; fout << (walls + 1) * (walls + 1) << endl; } return 0; }

I knew it wouldn't be that easy haha, worth a shot lol

[Analysis Mode]

why are you inputting from files? All input is done from screen.

[saltpro15]

files help me think, i just ran it and it produced some number like -399764534, so I think C++ is doing it's thing again

edit : input numbers are 1 and 3

[DanielG]

can you put up a link to the question, it will help us figure out what it's asking. just a little.

[saltpro15]

already have, it's in my first post

here it is again, just in case the link doesn't show for some

http://www.spoj.pl/problems/PALACE/

[Analysis Mode]

long longs and bignums are your friends, too.

[bbi5291]

Put in a more mathematical style, the question asks: how many distinct NxN grids are there, such that each cell is either empty or filled, and every row and column contains an odd number of filled cells?

And no, you don't need long longs / bignums, because the answer is to be outputted modulo 98777.

[CodeMonkey2000]

For N=3 these are all the possible arrangements (a block with a * means an occupied room). I'm pretty sure this is a DP problem, look at the number of ways you can place people in an (n-1) matrix. I'm pretty sure you can brute force it to find patterns.

1
[*][*][*]
[*][*][*]
[*][*][*]

2
[ ][*][ ]
[ ][*][ ]
[*][*][*]

3
[*][*][*]
[ ][*][ ]
[ ][*][ ]

4
[ ][*][ ]
[*][*][*]
[ ][*][ ]

5
[*][ ][ ]
[ ][*][ ]
[ ][ ][*]

6
[ ][ ][*]
[ ][*][ ]
[*][ ][ ]

7
[*][ ][ ]
[ ][ ][*]
[ ][*][ ]

8
[ ][ ][*]
[*][ ][ ]
[ ][*][ ]

9
[ ][*][ ]
[ ][ ][*]
[*][ ][ ]

10
[*][ ][ ]
[*][*][*]
[*][ ][ ]

11
[ ][*][ ]
[*][*][*]
[ ][*][ ]

12
[ ][ ][*]
[*][*][*]
[ ][ ][*]

13
[ ][*][ ]
[*][ ][ ]
[ ][ ][*]

14

[*][ ][ ]
[* ][ ][ ]
[*][*][*]

15
[ ][ ][*]
[ ][ ][*]
[*][*][*]

16
[*][*][*]
[*][ ][ ]
[*][ ][ ]