Problem is that i don't have any idea how would i calculate number of possible tilings ? I do know bit of introductory combinatorics and permutation combination but here i am completly stuck . Second problem is limit for n is too large - 10^6 , so answer can be too too large , printing last 4 digit is no problem though we could print it using mod but computing number of possible tilings is giving me trouble !
With combinatorics there are two issue: (a)
- Make sure to count them all
- Don't repeat elements
Considering your problem:
Let's define a `perfect tiling' as the one that does not have a vertical division.
So in a 2x2 room = is a perfect tiling but || is not.
Now if you want to tile a room of 2xn you could do a perfect tiling, or do a perfect tiling to the left and decorate the right as you please
That gives the formula N(K) = P(K) + \sum_{J=1}^{K-1} P(J) N(K-J)
show that it respects (a)
With vertical division I mean a vertical line of length 2. As if you took a handsaw and cut the floor.
So in a 2x1 the `perfect tiling' will be a vertical bar
2x2, two horizontal bars
2x3, there are two ways, both with the L shape.
N() is the number of possible tilings
P() is the number of perfect tilings
2xK is the dimension of the room
J just an iterator
Okay , i understood whole of your last post , but your first post formula is still mystery to me , i still can't understand what those notations mean a '\' before sum , what sum_{J=1}^{k-1} meaned and what was k .
And also it would be very helpful your formulae for some small input - like for 2x3 , number of possible tiling is 5 as shown in example of link .
& Thankyou before hand :D
Okay , let me try P(k)=2 @mik2718 , but i don't think it should be always 2 , else @ne555 would have not put P(n) in formula and instead put 2 in place of P(k) !
Yeah , i think its my mistake , the concept seems easy a bit now but its getting more & more tricky to implement the simple concept , this erroneous code is not giving the required output :(
1 2 3 4 5 6 7 8 9 10 11 12 13
#include<iostream>
usingnamespace std;
int valueofp(int a) {if (a==1 || a==2) return 1; elsereturn 2;}
int main() {
int i,n[1000]={0,1,2},p,sum=0,k;
cin>>k;
sum=valueofp(k);
for (i=1;i<k;i++) {
sum+=valueofp(i)*n[k-i];
}
cout<<sum;
system("PAUSE");
}
'n' array is used to store all previous n(k) . Yeah i didn't did mod part , i will add that later but before it i put input as 13 and it prints wrong answer as given in example of question ! Thats why i left that mod part for debugging purpose :)
Well , i exactly didn't get what you meant by 'where' .
But obviously n[k] will store n(k) , n[k+1] stores n(k+1) and so on and first three , ie k=1,2,3 are exception to that p(k)=2 so i have initialized these exception as n[0]=0,n[1]=1,n[2]=2 .
Yeah you are correct @ne555 . I have already tried many variations , and i am trying more so dont think that i have left this question :) If still i wont be able to get this simple implementation , i will let you know , thankyou once again