Hi this is about problem http://codeforces.com/contest/471/problem/C
In the tutorial it shows that (N+F)%3==0 is needed for a house with F floors to be valid.
But I don't understand how this condition is enough for the requirement that "each floor has fewer rooms than the floor below it".
I mean, suppose we have make F=3 floors from 6 rooms. Then those floors can be arranged as having 3,2,1 rooms, which meet the requirement. But we could wrongly arrange the house as having 2,2,2 rooms as well. In both cases (N+F)%3==0.
In this example it doesn't matter. But how do we know in some case we would not be counting a wrong configuration of floors? Of course I cannot come up with a counterexample, I'm sure the tutorial is correct, but I just don't understand how "divisible by 3" also implies "decreasing rooms on each floor".
Thanks!
If you can arrange rooms according to requirement you have to count it not all combinations has to be correct just we need 1 possible combination for each height , but it seems that you misunderstood or something blind to you I will give it a try:
Just ask yourself one question
what is the minimum number of houses you need to build say 3 floors in the house ?
begin from the highest floor
so the order will be 1 2 3
what's the minimum number of rooms in highest floor ( Just 1 room ) and next one just 2 rooms and lowest one just 3 rooms so now you see the house like a triangle
in one floor number of cards needed is (number of rooms)*3 -1
so if N less than minimum number of cards needed to build 3 floors house so you can't build it
if N equal to this number so you can build it.
last case if N is greater than this number
so now you build a house with minimum number of cards but you still have cards
to add one extra room to any floor you will need 3 cards just draw it and you will see.
if the number of remaining cards is divisible by 3 so you can build a house with the same height just build remaining rooms in the lowest floor hope It's clear now.
Great explanation, from the last few lines ("just build remaining rooms in lowest floor") I got it finally. Thank you!