10943 - How do you add?

[smilitude]

i tried to solve it using recursion and dp;
whats wrong with my code? is it my formulation , is my formulation wrong? this is a small code, i hope someone will answer soon...

Code: Select all

/* 
 * 10943 how do you add?
 * submission 1 WA
 * code finished at 2:20pm on dec25, 05
 *
 * this is a perfect example for memoization
 *
 */

#include <stdio.h>
#include <string.h>

long cache[105][105];

long sum(int N, int K) {
	int i;
	long summ=0;

	if(cache[N][K]!=-1) return cache[N][K];
	if(N==0||K==0) return 1;
	if(K==1) return N;
	if(K==2) return N+1;
	
	for(i=0;i<=N;i++) 
		summ+=sum(N-i,K-1)%1000000;
	cache[N][K]=summ;	
return summ;
}

int main() {
	int N,K;
	int i;
	for(i=0;i<101;i++)
 		memset(cache,-1,sizeof(cache[0])*101);
	while(scanf("%d %d",&N,&K)==2) {
		if(!N && !K) break;
		printf("%ld\n",sum(N,K)%1000000 );
	}
return 0;
}

[misof]

On the first sight, the memset part looks wrong to me.
Replace it with memset(cache, -1, sizeof(cache));

[smilitude]

thanks, thanks for reply~! though i still have WA...

[mamun]

whats wrong with my code?

Ya, what's wrong? WA or TLE? I guess WA.
What should be the output for

Code: Select all

2 1

[smilitude]

whats wrong with my code?

Ya, what's wrong? WA or TLE? I guess WA.
What should be the output for

Code: Select all

2 1

you are so helping mamun bhai!
thanks a lott!
i got ac, though i am regreting why didnt i notice that thing before?

[vinay]

thanks for the i\o

[abhiramn]

Code: Select all

#include<stdio.h>
int main()
{
	int dp[202][102],i,j;
	for(i=0;i<202;dp[i][0]=1,dp[i][1]=i,i++);
	for(i=1;i<202;i++)
		for(j=2;j<102;j++)
			dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%1000000;
	while(1)
	{
		scanf("%d%d",&i,&j);
		if(!i&&!j)
			break;
		printf("%d\n",dp[i+j-1][i]);
	}
	return 0;
}

WRONG ANSWER! I have tested this for all inputs on the forum. It gives correct output. Please tell me where the problem could be.

[Jan]

Test the cases.

Input:

Code: Select all

2 1
2 2
0 0

Output:

Code: Select all

1
3

Hope these help.

[DD]

This is a DP problem, and my recurrence relation formula is way[N][K] = sigma 0<=i<=N (way[N-i][K-1])