hi don please tell me where am i wrong in this maths in solving this
question.
let x = number of times to press up button
let y = number of times to press down button
k = g -s
so we have
u*x - d*y = k ----------->(1)
we have to minimize x + y
so from (1) x = (k+d*y)/u;
x + y = (k + d*y)/u + y
now if u analyze (k + dy ) should be integer
so (k + d* y) %u = 0
k%u + (d*y)%u = 0;
(dy)%u = u - (k%u)
dy = pu + (u - (k%u))
where p is any integer
y = pu/d +(u -(k%u))/d
so for y to be minimum
p = 0;
so y = (u - (k%u))/d;
if we know y we can get x and x + y
CORRECT ME IF I AM WRONG
On Tue, Nov 15, 2011 at 4:12 AM, Don <[email protected]> wrote:
> I solved this one with a breadth-first search.
> Don
>
> On Nov 14, 8:27 am, Anshul AGARWAL <[email protected]> wrote:
> > problem ishttp://www.spoj.pl/problems/ELEVTRBL/
> > and my solution is give wrong answer on spoj . Plz help me to find in
> which
> > case my solution give wrong answer.
> >
> > *
> > #include<iostream>
> > **
> > #include<stdio.h>
> > using namespace std;
> > int main()
> > {
> > long long int f,s,u,d,g,c,p;
> >
> > scanf("%lld%lld%lld%lld%lld",&f,&s,&g,&u,&d);
> >
> > p=0;
> >
> > if(s==g)
> > printf("0\n");
> > if(s>g&&u==0&&d!=0)
> > {
> > int temp=s-g;
> > if((temp/d)*d==temp)
> > {
> > p=temp/d;
> > printf("%lld\n",p);
> >
> > }
> > else
> > printf("use the stairs\n");
> >
> > }
> > else if(s>g)
> > {
> > int temp =s;
> > s=g;
> > g=temp;
> >
> > // cout<<"2"<<endl;
> > }
> > //cout<<"1"<<endl;
> > c=s;
> > if(s<g)
> > { while(1)
> > {
> > int temp=g-c;
> > int q;
> > if(u==0)
> > {
> > if(c==g)
> > {
> > printf("0\n");
> > break;
> > }
> > else
> > {
> > printf("use the stairs\n");
> > break;
> > }
> > }
> > if(temp/u==(temp/u)*u)
> > {
> > q=temp/u;
> >
> > }
> > else
> > q=temp/u+1;
> >
> > if((c+q*u)<=f)
> > { // cout<<"1"<<endl;
> > p=p+q;
> > c=(q)*u+c;
> > //cout<<c<<endl;
> > }
> > else
> > {//cout<<"2"<<endl;
> > p=p+temp/u;
> > c=(temp/u)*u+c;
> > }
> > if(c==g)
> > {
> > // cout<<"3"<<endl;
> > printf("%lld",p);
> > break;
> > }
> > if(u==d||d==0||((u%d==0)&&d!=0)||(d%u==0&&u!=0))
> > {
> >
> > printf("use the stairs\n");
> > break;}
> > if(c-d>=0)
> > { // cout<<"4"<<endl;
> > c=c-d;
> > p+=1;
> > // cout<<c<<endl;
> > }
> > else
> > {
> > // cout<<"5"<<endl;
> > printf("use the stairs\n");
> > break;
> > }
> > }
> > }
> >
> > }
> >
> > Anshul Agarwal
> > Nit Allahabad
> > Computer Science**
> > *
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
*UTKARSH SRIVASTAV
CSE-3
B-Tech 3rd Year
@MNNIT ALLAHABAD*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
