## 11001 - Necklace

Moderator: Board moderators

Ankur Handa
New poster
Posts: 6
Joined: Mon May 15, 2006 11:34 am
hi everyone i am getting wrong answer for this question .
I have tried many times but everytime i got wrong answer my program is
working for all of the test cases given in the forum , can anybody tell me
where am i going wrong .
My logic is if V is divisible by 2*V0 then print the number V/(2*V0)
else find n = V/(2*V0) and then u will have to check for 2 values floor(n)
and floor(n)+1 and if the Max length is coming out to be same then print
0 otherwise print round(n).
here is the Code

Code: Select all

``````#include<stdio.h>
#include<iostream>
#include<math.h>
int main(void)
{
int V,V0;
double n,n1,L1,L2,x,z;
while(1)
{
scanf("%d%d",&V,&V0);
L1=0;L2=0;
if(V==0 && V0==0) break;
if((V%(2*V0))==0) printf("%d\n",V/(2*V0));
else
{
n  = (double)V/(2*(double)V0);
n1 = n;
n  = floor(n);
z = (double)V/(double)n ;
x = (double)V/(double)(n+1);
if(n!=0 && z>V0)
{
L1 = (n)*(0.3)*sqrt(z-(double)V0);
}
if(x>V0)
L2 = (n+1)*(0.3)*sqrt(x-V0);

if(L1==L2 || V==V0)printf("0\n");

else printf("%.lf\n",n1);
}

}
}``````
Thanks a lot
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Ankur Handa wrote:hi everyone i am getting wrong answer for this question .
I have tried many times but everytime i got wrong answer my program is
working for all of the test cases given in the forum , can anybody tell me
where am i going wrong .
Actually, your solution is not working even for the second test case in the problem statement. (Small hint: never compare floats directly by a == b, because even small precision errors may lead to a different answer than you expect.)
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
I cant get any clue

I got correct output for all the inputs posted in this thread ....still WA !!

would anyone check my code, please ?

Code: Select all

``removed after AC``
Last edited by Kallol on Tue Jul 04, 2006 3:05 pm, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Kallol wrote:I cant get any clue

I got correct output for all the inputs posted in this thread ....still WA !!

Code: Select all

``````47 47
0 0``````
Check the following part of your code:
Kallol's code wrote:......if(v0>vt)
......{
.........printf("0\n");
.........continue;
......}
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
Thanx a lot Martin Macko,
I finally got ACC.
It was just a mistake of a symbol but it made me so crazy and wasted a lot of my time . I think this has become a regular event for me. I think about a problem get the solution way and then code it but do not get ACC for some silly reasons.Anyway you were so helpful and so expert to find out the bug in my code . Thank u once again.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
sarah
New poster
Posts: 7
Joined: Tue Aug 30, 2005 2:54 pm
Location: Iran
Contact:

### Why WA?

Can someone help me why I get WA for this problem?
I've checked all the test case here and my program outputs the correct numbers, but WA!
In my code, if Vt % (2*V0) is zero I output Vt / (2*V0) as n, and if it is not zero, I check which of n1=Vt/(2*V0) & n2=Vt/(2*V0) produces a bigger length, and output it. And if they are equal, I output zero. And whenever I find n, I check if (Vt/n)-V0>=0 . If it is negative I output 0 as n.
In order to see if the two lengths are equal or not, each time I get the leftmost digit of the two numbers and compare them. then I omit this leftmost digit and continue this procedure until the number becomes zero. But there is a problem that I dont know how many times should I continue this procedure. If you could suggest me a better way to compare two doubles, then it's so kind of you!
Here's my code:

Code: Select all

``````# include <iostream.h>
//# include <fstream>
# include <math.h>

//using namespace std;

void main()
{
int vt,v0,i,j,r1,r2;
double res1,res2,vf;
int n,n1,n2;
for (cin>>vt>>v0 ; vt || v0 ; cin>>vt>>v0)
{
if (vt<=v0)
cout<<"0"<<endl;
else
{
if ((vt)%(2*v0)==0)
{
n=vt/(2*v0);
if (vt/n>=v0)
{}
else
n=0;
}
else
{
n1=vt/(2*v0);
n2=n1+1;
vf=vt;
if (vt/n1>=v0)
res1=0.3*n1*sqrt(vf/n1-v0);
else
res1=-1;
if (vt/n2>=v0)
res2=0.3*n2*sqrt(vf/n2-v0);
else
res2=-1;
if (res1==-1 && res2==-1)
n=0;
else
{
for (i=0 ; ; i++)
if (((int)(res1/pow(10,i)))==0)
break;
for (j=0 ; ; j++)
if (((int)(res2/pow(10,j)))==0)
break;
if (i>j)
n=n1;
else
if (i<j)
n=n2;
else
{
if (!i)
{
i++;
res1*=10;
res2*=10;
}
while(1)
{
r1=res1/pow(10,i-1);
r2=res2/pow(10,i-1);
if (r1>r2)
{
n=n1;
break;
}
if (r2>r1)
{
n=n2;
break;
}
res1-=(r1*pow(10,i-1));
res2-=(r1*pow(10,i-1));
res1*=10;
res2*=10;
if (res1==0)
{
if (res2==0)
{
n=0;
break;
}
n=n2;
break;
}
else
{
if (res2==0)
{
n=n1;
break;
}
}
}
}
}
}
cout<<n<<endl;
}
}
}
``````
leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil
My code get the correct output for all the inputs here, bat get WA when I submit. What's wrong? Anyone can help me, please!

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int calculaMaiorTamanho(int volume1, int volume2);

int main(){

int volume1, volume2, maiorTamanho;

scanf("%d%d", &volume1, &volume2);

while (volume1 != 0 || volume2 != 0){

if (volume1 <= volume2){
printf("0\n");
}
else{
maiorTamanho = calculaMaiorTamanho(volume1, volume2);
printf("%d\n", maiorTamanho);
}
scanf("%d%d", &volume1, &volume2);
}
return 0;
}

int calculaMaiorTamanho(int volume1, int volume2){

double tamanho1, tamanho2;

if (volume1 % (2*volume2) == 0){
}
else{
n = volume1 / (2*volume2);
tamanho1 = 0.3 * n * sqrt((double)((double)volume1/n - volume2));
tamanho2 = 0.3 * (n+1) * sqrt((double)((double)volume1/(n+1) - volume2));
if (fabs(tamanho1 - tamanho2) < 0.0000000000000001){
}
else{
if (tamanho1 > tamanho2){
}
else{
}
}
}

}
``````
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: Why WA?

sarah wrote:Can someone help me why I get WA for this problem?
I've checked all the test case here and my program outputs the correct numbers, but WA!
Your solution gives a Floating point exception on the following input:

Code: Select all

``````250 249
0 0``````
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
leocm wrote:My code get the correct output for all the inputs here, bat get WA when I submit. What's wrong? Anyone can help me, please!
Try the following input:

Code: Select all

``````36584 8
8134 363
45029 46
47250 24
10545 215
10927 565
34317 1
36947 155
23547 21
59272 112
0 0``````
My AC's output is:

Code: Select all

``````0
11
489
984
25
10
0
119
561
265``````
leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil
Martin Macko wrote:
leocm wrote:My code get the correct output for all the inputs here, bat get WA when I submit. What's wrong? Anyone can help me, please!
Try the following input:

Code: Select all

``````36584 8
8134 363
45029 46
47250 24
10545 215
10927 565
34317 1
36947 155
23547 21
59272 112
0 0``````
My AC's output is:

Code: Select all

``````0
11
489
984
25
10
0
119
561
265``````

Now, I get AC. But I didn't understand why... I just only changed the code

Code: Select all

``````      if (fabs(tamanho1 - tamanho2) < 0.0000000000000001){
}``````
to the new code

Code: Select all

``````		if (fabs(tamanho1 - tamanho2) < 0.000000000001){
}
``````

and now got AC! Why this happened? I really don't understand the reason. Somebody could explain me?
Thank you.
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
leocm wrote:I really don't understand the reason. Somebody could explain me?
Thank you.
double just does not have such a big precision, therefore you got a rounding error. Personaly, I am comparing doubles with error tolerance about 1e-9.
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Contact:
I've have used just 'int'

Code: Select all

``````n = vt / v0 / 2;
if ((vt * n - v0 * n * n) == (vt * (n + 1) - v0 * (n + 1) * (n + 1)))
/*  */
``````
marthapfhui
New poster
Posts: 7
Joined: Sat Mar 10, 2007 7:03 pm
Hi, I am getting WA though passing the test cases posted here. The way I do the question is similar.

Would anyone give me a hand to tell if there's anything wrong? Thanks a lot in advance.

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(int argc, char **argv)
{
double vt, v0;
double minn, d1, d2;
int n1, n2;

while(scanf("%lf%lf", &vt, &v0))
{
if(vt == 0 && v0 == 0) break;
if(vt <= v0)
{
printf("0\n");
continue;
}
else if(fabs(v0-vt) < 0.000000001)
{
printf("0\n");
continue;
}

minn = vt/2.0/v0;

if(((double)fabs(minn - round(minn))) < 0.000000001)
{
n1 = round(minn);

if(fabs(vt/n1 - v0) < 0.000000001)
{
printf("0\n");
}
else if(vt/n1 < v0)
{
printf("0\n");
}
else
{
printf("%d\n", n1);
}
}
else
{
n1 = floor(minn);
n2 = ceil(minn);

if(n1 != 0)
{
if(fabs(vt/n1 - v0) < 0.000000001) n1 = 0;
else if(vt/n1 < v0) n1 = 0;
}

if(fabs(vt/n2 - v0) < 0.000000001) n2 = 0;
else if(vt/n2 < v0) n2 = 0;

if(n1 == 0 && n2 == 0)
{
printf("0\n");
}
else if(n1 == 0)
{
printf("%d\n", n2);
}
else if(n2 == 0)
{
printf("%d\n", n1);
}
else
{
d1 = n1 * 0.3 * sqrt((vt/n1) - v0);
d2 = n2 * 0.3 * sqrt((vt/n2) - v0);

if(fabs(d1-d2) < 0.00000001)
{
printf("0\n");
}
else if(d1 < d2)
{
printf("%d\n", n2);
}
else
{
printf("%d\n", n1);
}
}
}
}
}
``````
New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
Darko wrote:for the input:

Code: Select all

``````40000 3
40000 9
50000 3
60000 7
60000 9
60000 11
0 0``````
output:

Code: Select all

``````6667
2222
8333
4286
3333
2727``````
Darko
BUT MY AC PROGRAM GIVES THE FOLLOWING OUTPUT:
6666
2222
8333
4285
3333
2727

Martin maco wrote:for the input:

Code: Select all

``````Try the following input:

Code:
36584 8
8134 363
45029 46
47250 24
10545 215
10927 565
34317 1
36947 155
23547 21
59272 112
0 0
``````

Code: Select all

``````My AC's output is:

Code:
0
11
489
984
25
10
0
119
561
265
``````
Martin maco
BUT MY OUTPUT IS
0
11
489
984
24
9
0
119
560
264

WHICH ONE'S IS CORRECT?
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm