11001 - Necklace

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

Moderator: Board moderators

Ankur Handa
New poster
Posts: 6
Joined: Mon May 15, 2006 11:34 am

Post by Ankur Handa » Tue May 23, 2006 4:23 pm

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

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

Post by Martin Macko » Sun May 28, 2006 8:51 pm

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.)

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Thu Jun 15, 2006 9:21 pm

I cant get any clue :-?

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

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
Bangladesh

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

Post by Martin Macko » Sun Jun 18, 2006 6:30 pm

Kallol wrote:I cant get any clue :-?

I got correct output for all the inputs posted in this thread ....still WA !! :cry:
Your code's not working for:

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;
......}

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Tue Jul 04, 2006 3:03 pm

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
Bangladesh

sarah
New poster
Posts: 7
Joined: Tue Aug 30, 2005 2:54 pm
Location: Iran
Contact:

Why WA?

Post by sarah » Wed Jul 19, 2006 2:21 pm

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

Post by leocm » Fri Jul 21, 2006 9:51 am

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){
	
	int n, maiorQuantidadeAneis = 0;
	double tamanho1, tamanho2;
	
	if (volume1 % (2*volume2) == 0){
		maiorQuantidadeAneis = volume1 / (2*volume2);
	}
	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){
				maiorQuantidadeAneis = 0;
		}
		else{
			if (tamanho1 > tamanho2){
				maiorQuantidadeAneis = n;
			}
			else{
				maiorQuantidadeAneis = n+1;
			}
		}
	}
	
	return maiorQuantidadeAneis;
	
}

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

Re: Why WA?

Post by Martin Macko » Sun Jul 23, 2006 7:17 pm

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

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

Post by Martin Macko » Sun Jul 23, 2006 7:19 pm

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

Post by leocm » Sun Jul 23, 2006 10:21 pm

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){
            maiorQuantidadeAneis = 0;
      }
to the new code

Code: Select all

		if (fabs(tamanho1 - tamanho2) < 0.000000000001){
				maiorQuantidadeAneis = 0;
		}

and now got AC! Why this happened? I really don't understand the reason. Somebody could explain me?
Thank you.

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

Post by Martin Macko » Sun Jul 23, 2006 10:42 pm

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.

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

Post by Nazmul Quader Zinnuree » Wed Sep 06, 2006 9:31 am

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)))
/*  */
:wink:

marthapfhui
New poster
Posts: 7
Joined: Sat Mar 10, 2007 7:03 pm

Post by marthapfhui » Sat Mar 10, 2007 7:07 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);
				}
			}
		}
	}
}

SHAHADAT
New poster
Posts: 23
Joined: Thu Jun 22, 2006 8:55 am
Location: sust,bangladesh

Post by SHAHADAT » Fri Apr 06, 2007 6:15 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? :o :o

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Apr 06, 2007 1:23 pm

The outputs of Darko and Martin maco are correct, as my accepted code returns same output.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 110 (11000-11099)”