It seems like a mathematical solution should be possible.
What we want to do is find m >= 0 and n <= 0 so that m * u + n * d = g
- s.
Pseudocode:
If (s + u > f and s - d < 1) or (f - d < g and 1 + u > g) then
return "use the stairs".
Use the Extended GCD algorithm (http://en.wikipedia.org/wiki/
Extended_Euclidean_algorithm#Iterative_method_2), to find gcd(u,d) and
x and y so that x*u + y*d = gcd(u,d).
If (g - s) is not divisible by gcd(u,d) then
Return "use the stairs".
Set m = x * (g - s) / gcd(u,d) and n = y * (g - s) / gcd(u,d)
While m >= d and n <= -u
Set m = m - d and n = n + u
While m < 0 or n > 0
Set m = m + d and n = n - u
Return m - n.
Dave
On Nov 14, 4:42 pm, 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.
