10446 - The Marriage Interview :-)

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

Moderator: Board moderators

User avatar
DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

10446 - The Marriage Interview :-)

Post by DemonCris » Wed Feb 12, 2003 8:24 am

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

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Wed Feb 12, 2003 8:41 am

My AC program used unsigned long long as well.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Wed Feb 12, 2003 9:01 am

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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

User avatar
DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

Post by DemonCris » Wed Feb 12, 2003 9:09 am

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

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

10446 (about using "unsigned long long int" )

Post by hank » Sat Apr 05, 2003 6:50 am

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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Wed Oct 08, 2003 8:33 am

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

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Sun Oct 19, 2003 9:52 pm

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
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Location: Dhaka, Bangladesh
Contact:

10446 The Marriage Interview :-(

Post by popel » Fri Jan 02, 2004 7:19 pm

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.
μδ. ταηνιπ αλ αμιη

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Tue Jan 06, 2004 9:55 pm

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) :D.
greetings...
Istiaque Ahmed [the LA-Z-BOy]

popel
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Location: Dhaka, Bangladesh
Contact:

Post by popel » Wed Jan 07, 2004 7:38 pm

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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Sat Mar 20, 2004 9:46 am

Subeen wrote: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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Sat Mar 20, 2004 9:49 am

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
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Fri Aug 13, 2004 3:59 am

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.

User avatar
Mata
New poster
Posts: 18
Joined: Mon Dec 17, 2007 11:35 pm
Location: Queretaro
Contact:

wrong answer

Post by Mata » Fri Mar 28, 2008 10:40 pm

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;
}
/********************************
********************************/

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Re: 10446 - The Marriage Interview ;-)

Post by smilitude » Thu Jun 26, 2008 11:31 am

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! ;)
fahim
#include <smile.h>

Post Reply

Return to “Volume 104 (10400-10499)”