10446 - The Marriage Interview :-)
Moderator: Board moderators
10446 - The Marriage Interview :-)
In C, I used data type "unsigned long long int" but I get WA.
Is it overflow??
Is it overflow??
-
- Experienced poster
- Posts: 193
- Joined: Thu Sep 19, 2002 6:39 am
- Location: Indonesia
- Contact:
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-
If not, probably since you don't handle negative-values as inputs to trib() function.
-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
10446 (about using "unsigned long long int" )
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?
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?
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...
[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...
10446 The Marriage Interview :-(
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.
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.
μδ. ταηνιπ αλ αμιη
-
- Learning poster
- Posts: 94
- Joined: Wed Jul 31, 2002 12:44 pm
- Location: Dacca, Bangladesh
- Contact:
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...
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...
Istiaque Ahmed [the LA-Z-BOy]
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.
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.
μδ. ταηνιπ αλ αμιη
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.
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.
wrong answer
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;
}
/********************************
********************************/
********************************/
Re: 10446 - The Marriage Interview ;-)
i tested your program against my program for these inputs
your program gave these outputs
while they should be
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!
Code: Select all
2 -3
15 8
18 2
9 2
4 1
60 1
111 111
Code: Select all
Case 1: 4294967294
Case 2: 65537
Case 3: 131073
Case 4: 257
Case 5: 5
Case 6: 1
Code: Select all
Case 1: 1
Case 2: 64897
Case 3: 8361
Case 4: 109
Case 5: 4
Case 6: 60
best wishes!

fahim
#include <smile.h>
#include <smile.h>