10446 - The Marriage Interview :-)

[DemonCris]

In C, I used data type "unsigned long long int" but I get WA.
Is it overflow??

[cytse]

My AC program used unsigned long long as well.

[turuthok]

If you can have unsigned long long, you should be able to get it accepted (I used Java during the contest and honestly I don't know if Java have that kind of data-type, so I had to precalc inputs with n=60) ....

If not, probably since you don't handle negative-values as inputs to trib() function.

-turuthok-

[DemonCris]

I got WA when input n is negative^^ .. thx

[hank]

I already solved this problem and got AC.
But my program still have a small bug.
When n>=32 and back>=32 , the output is wrong!

input:

32 32
50 50
60 60

output:

Case 1: 1
Case 2: 1
Case 3: 1

It is very strange why I still can got AC?

[Subeen]

my program prints 1 when input is negative.
but getting WA.
please give me some test input / output to test my program.

[Subeen]

I spend a lot of time but can't get this problem AC yet. What's the problem is my code? Here is it:
[c]#include <stdio.h>

typedef unsigned long long int datatype;

void main()
{
datatype t[65][65];
int i, j, k, n=61, back, kase;
datatype temp;

for(i=0; i<=n; i++) t[0] = t[1] = 1;

for(i=2; i<=n; i++)
{
for(j=1; j<=n; j++)
{
temp = 1;
for(k=1; k<=j; k++)
{
if(i-k < 0)
{
temp += j - k + 1;
break;
}
temp += t[i-k][j];
}
t[j] = temp;
}
}
kase = 0;
while(2==scanf("%d%d", &n, &back))
{
if(n > 60) break;
printf("Case %d: ", ++kase);
if(n < 0) printf("1\n");
else
printf("%llu\n", t[n][back]);
}
}[/c]

please help me to identify my problem...

[popel]

Hi Everyone,
This problem seems very interesting, but I don't know why I am getting WA! I think my answers are correct.
Here dynamic technique memoization is used
For negative values of n, it program prints 1.
And I have used "unsigned long long"

Would you please check the code below?

[cpp]
#include<stdio.h>

typedef unsigned long long ll;
ll table[61][61];

ll trib(int n, int back)

{
if(n<2)return 1;
else if(table[n][back])return(table[n][back]);
else{
int i;
ll sum=0;
for(i=1;i<=back;i++)sum+=trib(n-i,back);

table[n][back]=sum+1;

return(sum+1);
}


}


void main()

{
int a,b,casen=0;
for(b=0;b<61;b++)table[0]=1;
for(a=0;a<2;a++){
for(b=0;b<61;b++)table[a]=1;
}
for(b=1;b<61;b++)trib(61,b);

while(scanf("%d %d",&a,&b)==2){
if(a>60)break;
else if(a<0 || b<0)printf("Case %d: 1\n",++casen);
else printf("Case %d: %llu\n",++casen,table[a]);
}

}

[/cpp]

Thank you all.

[the LA-Z-BOy]

hello,
your problem is here...[cpp] for(b=1;b<61;b++)trib(61,b);[/cpp]
when you call something like trib(61,2)... your function tries to access table[61][2] which is illegal(array out of bound), because you declared[cpp]typedef unsigned long long ll;
ll table[61][61];[/cpp]
change this to[cpp] for(b=1;b<61;b++)trib(60,b);[/cpp]
( n actually needn't be >60) and everything is okay (i've tested your prog with ALL kind of inputs) .
greetings...

[popel]

hi,
Thank you very much for checking my code. Actually it is very tiresome verifying others code. Sometimes I get stuck with these types of small but *fatal* errors, which I should take care.

Finally I got accepted.
My WA's in this problem mean that gcc++ compiler throws exception SIGSESV if invalid memory reference is used for writing.
I thought exception is thrown both for reading and writing.

[Subeen]

I spend a lot of time but can't get this problem AC yet. What's the problem is my code? Here is it:
[c]now AC[/c]

please help me to identify my problem...

[Subeen]

I spend a lot of time but can't get this problem AC yet. What's the problem is my code? Here is it:
[c]now AC[/c]

please help me to identify my problem...

[david]

What compiler are you using?
I guess it is caused by the printf code not working properly with long long's.
When I run my accepted program under Linux and compiled with gcc I get the correct output (34359738369 for 32 32), but when I run it under Windows with dev-cpp (using gcc 3.3.1) it displays 1, which is the lower 32-bit word of the result.

[Mata]

Hi, I try this problem but i got wrong answer, i have correct answer for the sample input, what can be wrong with this

Code: Select all

#include <iostream>
unsigned long long recur(int n, int b);
int main()
{
	int n=0, b=0, conta=0;
	while(scanf("%d %d",&n,&b)==2&&n<61)
	{
		conta++;
		if(n<=1)
			printf("Case %d: 1\n",conta);
		else
			printf("Case %d: %llu\n",conta,recur(n,b));
	}
}
unsigned long long recur(int n, int b)
{
	if(n<=2)
		return b+1;
	else
		return 2*recur(n-1,b)-1;
}

[smilitude]

i tested your program against my program for these inputs

Code: Select all

2 -3
15 8
18 2
9 2
4 1
60 1
111 111

your program gave these outputs

Code: Select all

Case 1: 4294967294
Case 2: 65537
Case 3: 131073
Case 4: 257
Case 5: 5
Case 6: 1

while they should be

Code: Select all

Case 1: 1
Case 2: 64897
Case 3: 8361
Case 4: 109
Case 5: 4
Case 6: 60

if you want my suggestion, avoid a recursion which seems right. rather, try to find a simple way to memoize the given function so that it would return the number of times it has been run.

best wishes!