Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

三种情况,各种判断呀,还用到数学了,无语,贴代码,调了两个小时,自己太衰了

Posted by peijian at 2012-04-07 20:24:48 on Problem 2142
#include <iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int x,y;
int gcd(int a,int b){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    else{
        int result=gcd(b,a%b);
        int tem=x;
        x=y;
        y=tem-a/b*y;
        return result;
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    int a,b,d;
    while(scanf("%d%d%d",&a,&b,&d)&&(a|b|d)){
        int d1=gcd(a,b);
        if(d%d1!=0)printf("no solution\n");
        else {
            a/=d1,b/=d1,d/=d1;
            gcd(a,b);
            x*=d;y*=d;
            bool f=0;
            int k1,k2,k;
            int ansx1,ansy1,ansx2,ansy2,ansx3,ansy3;
            //cout<<"x="<<x<<" "<<"y="<<y<<endl;
            //first
            k1=ceil(-x*1.0/b);
            k2=floor(y*1.0/a);
            if(b>a)k=min(k1,k2);
            else k=max(k1,k2);
            if(k>=k1&&k<=k2){
                f=1;
                ansx1=x+k*b;
                ansy1=y-k*a;
            }
            //second
            k2=ceil(y*1.0/a);
            k=max(k1,k2);
            ansx2=x+k*b;
            ansy2=-(y-k*a);
            //third
            k1=floor(-x*1.0/b);
            k2=floor(y*1.0/a);
            k=min(k1,k2);
            ansx3=-(x+k*b);
            ansy3=y-k*a;
            int ansx,ansy;
//            cout<<ansx1<<" "<<ansy1<<endl;
//            cout<<ansx2<<" "<<ansy2<<endl;
//            cout<<ansx3<<" "<<ansy3<<endl;
            if(ansx2+ansy2<ansx3+ansy3){
                ansx=ansx2;
                ansy=ansy2;
            }
            else if(ansx2+ansy2>ansx3+ansy3){
                ansx=ansx3;
                ansy=ansy3;
            }
            else{
                if(a*ansx2+b*ansy2<a*ansx3+b*ansy3){
                    ansx=ansx2;
                    ansy=ansy2;
                }
                else {
                    ansx=ansx3;
                    ansy=ansy3;
                }
            }
            if(f){
                if(ansx1+ansy1<ansx+ansy){
                    ansx=ansx1;
                    ansy=ansy1;
                }
                else if(ansx1+ansy1==ansx+ansy){
                    if(a*ansx1+b*ansy1<a*ansx+b*ansy){
                        ansx=ansx1;
                        ansy=ansy1;
                    }
                }
            }
            printf("%d %d\n",ansx,ansy);
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator