10743 - Blocks on Blocks

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

Beautiful proof

Post by ranjit » Sat Jan 01, 2005 5:25 am

Really nice proof. Thanks for it.

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Sat Jan 01, 2005 6:52 am

Hi Cho, I am really interesed about your proof, but unfortunately I can't open the file format you have used. :cry: do you have any other file format like .pdf or plz mention what software will support the file, I will collect it then. :roll:
Jalal : AIUB SPARKS

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Jan 01, 2005 8:04 am

My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Jan 01, 2005 8:47 am

CodeMaker wrote:do you have any other file format like .pdf
here is the pdf format: 10743.pdf

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 10743 - Blocks on Blocks

Post by Angeh » Sat Aug 14, 2010 2:11 am

hi alll ....
can somebody help
it doesnt work for n==999 ... returns negative number .....
why???????!!!!!!

Code: Select all

#include<iostream>
using namespace std;
const long long Mode=10000;
#define FOR(i,n) for(int i=0;i<n;++i)
long long matrix[3][3]={0,0,4,1,0,-7,0,1,5},result[3][3],temp[3][3];
void power(int n ){
	if(n==1) FOR(r,3)FOR(c,3)result[r][c]=matrix[r][c];
	else if(n%2==1){
		power(n/2);
		FOR(r,3)FOR(c,3)temp[r][c]=0;
		FOR(r,3)FOR(c,3)FOR(i,3)temp[r][c] = (temp[r][c]+result[r][i]*result[i][c])%Mode ;
		
		FOR(r,3)FOR(c,3)result[r][c]=0;
		FOR(r,3)FOR(c,3)FOR(i,3)result[r][c] = (result[r][c] + temp[r][i]*matrix[i][c])%Mode;
	}
	else {
		power(n/2);
		FOR(r,3)FOR(c,3)temp[r][c]=0;
		FOR(r,3)FOR(c,3)FOR(i,3)temp[r][c] = (temp[r][c] + result[r][i]*result[i][c] )%Mode;
		
		FOR(r,3)FOR(c,3)result[r][c]=temp[r][c];
	}
	return ;
}
int main(){
	//freopen("in.txt","r",stdin);
	int cas,n,res;
	scanf("%d",&cas);
	for(int ca=0;ca<cas;++ca){
		scanf("%d",&n);
		if(n==1)res=1;
		else if(n==2)res=2;
		else if(n==3)res=6;
		else if(n==4)res=19;
		else {
			power(n-4);
			res= ( result[0][2]*2 + result[1][2]*6 + result[2][2]*19 )%Mode;
		}
		if(n<9)printf("Case %d: %d\n",ca+1,res);
		else printf("Case %d: %04d\n",ca+1,res);
	}
	return 0;
}
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

dull_jester
New poster
Posts: 17
Joined: Fri Oct 21, 2016 12:58 pm
Location: NS, Canada

Re: 10743 - Blocks on Blocks

Post by dull_jester » Wed Nov 16, 2016 2:56 am

Ok, from Cho's hints I've been able to go as far as this:

a_n = \sum_{k=1}^{n}b_{n,k},
b_{n,k} = \sum_{t=1}^{n-k}(t+k-1)b_{n-k,t}

I can take this one step further, but how to get to the formula a_n = ?a_{n-1} + ?a_{n-2} + ?a_{n-3}?
Cho's derivation is no longer accessible.

Post Reply

Return to “Volume 107 (10700-10799)”