POJ 2142 The Balance(扩展欧几里德解方程)

POJ 2142 The Balance(扩展欧几里德解方程)

The Balance
Time Limit: 5000MS   Memory Limit: 65536K
Total Submissions: 2490   Accepted: 1091

Description

Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. For example, to measure 200mg of aspirin using 300mg weights and 700mg weights, she can put one 700mg weight on the side of the medicine and three 300mg weights on the opposite side (Figure 1). Although she could put four 300mg weights on the medicine side and two 700mg weights on the other (Figure 2), she would not choose this solution because it is less convenient to use more weights.

You are asked to help her by calculating how many weights are required.



POJ 2142 The Balance(扩展欧几里德解方程)

Input

The input is a sequence of datasets. A dataset is a line containing three positive integers a, b, and d separated by a space. The following relations hold: a != b, a <= 10000, b <= 10000, and d <= 50000. You may assume that it is possible to measure d mg using a combination of a mg and b mg weights. In other words, you need not consider “no solution” cases.

The end of the input is indicated by a line containing three zeros separated by a space. It is not a dataset.

Output

The output should be composed of lines, each corresponding to an input dataset (a, b, d). An output line should contain two nonnegative integers x and y separated by a space. They should satisfy the following three conditions.

  • You can measure dmg using x many amg weights and y many bmg weights.
  • The total number of weights (x + y) is the smallest among those pairs of nonnegative integers satisfying the previous condition.
  • The total mass of weights (ax + by) is the smallest among those pairs of nonnegative integers satisfying the previous two conditions.

No extra characters (e.g. extra spaces) should appear in the output.

Sample Input

700 300 200
500 200 300
500 200 500
275 110 330
275 110 385
648 375 4002
3 1 10000
0 0 0

Sample Output

1 3
1 1
1 0
0 3
1 1
49 74
3333 1

Source

 
 
 
代码:
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
int extend_gcd(int a,int b,int &x,int &y)
{
    int m,tmp;
    if(b==0&&a==0) return -1;
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }    
    m=extend_gcd(b,a%b,x,y);
    tmp=x;
    x=y;
    y=tmp-(a/b)*y;
    return m;
}    
int main()
{
    
    int a,b,d;
    int x,y;
    int X,Y;
    int X1,Y1;
    while(scanf("%d%d%d",&a,&b,&d))
    {
        if(a==0&&b==0&&d==0) break;
        int flag=0;
        if(a<b)
        {
            flag=1;
            int t=a;
            a=b;
            b=t;
        }    
        int gcd=extend_gcd(a,b,x,y);
        x*=d/gcd;
        y*=d/gcd;
        
        int tmp=a/gcd;//Y=y-tmp*t;
        double t=(double)y/tmp;
        int t1=(int)floor(t);
        
        X=x+(b/gcd)*t1;
        Y=y-tmp*t1;
        if(t1!=t)//t是小数
        {
            t1=t1+1;
            X1=x+(b/gcd)*t1;
            Y1=y-tmp*t1;
            if(abs(X1)+abs(Y1)<abs(X)+abs(Y))
            {
                X=X1;
                Y=Y1;
            } 
            else if(abs(X1)+abs(Y1)==abs(X)+abs(Y) && a*abs(X1)+b*abs(Y1)<a*abs(X)+b*abs(Y))
            {
                X=X1;
                Y=Y1;
            }    
        }       
        if(flag==0)
            printf("%d %d\n",abs(X),abs(Y));
        else
             printf("%d %d\n",abs(Y),abs(X));
    }   
    return 0; 
}    

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/110424.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • SSL协议原理详解

    SSL协议原理详解SSL可参考:SSL技术原理SSL简介SSL和TLS:SSL(SecureSocketsLayer)安全套接层。是由Netscape公司于1990年开发,用于保障WordWideWeb(WWW)通讯的安全。主要任务是提供私密性,信息完整性和身份认证。1994年改版为SSLv2,1995年改版为SSLv3.TLS(TransportLayerSecurity)安全传输层协…

  • ac测评题库_awing

    ac测评题库_awing杭州人称那些傻乎乎粘嗒嗒的人为 62(音:laoer)。杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。不吉利的数字为所有含有 4 或 62 的号码。例如:62315,73418,88914 都属于不吉利号码。但是,61152 虽然含有 6 和 2,但不是 连号,所以不属于不吉利数字之列。你的任务是,对于每次给出的一个牌照号区间 [n,m],推断出交管局今后又要实际上给多少辆新的士车上牌

  • 人工智能猴子摘香蕉问题状态过程_人工智能原理猴子吃香蕉问题

    人工智能猴子摘香蕉问题状态过程_人工智能原理猴子吃香蕉问题题目:利用一阶谓词逻辑求解猴子摘香蕉问题:房内有一个猴子,一个箱子,天花板上挂了一串香蕉,其位置如图1所示,猴子为了拿到香蕉,它必须把箱子搬到香蕉下面,然后再爬到箱子上。请定义必要的谓词,列出问题的初始化状态(即下图所示状态),目标状态(猴子拿到了香蕉,站在箱子上,箱子位于位置b)。(附加:从初始状态到目标状态的谓词演算过程。)1.定义描述环境状态的谓词。AT(x,w):x在w处,个体域:x?{monkey},w?{a,b,c,box};HOLD(x,t):x手中拿着t,个体域:t?{box,ba

  • Matlab 绘图颜色选择「建议收藏」

    Matlab 绘图颜色选择「建议收藏」barh(1,1,1,’FaceColor’,[0.5,0.3,0.5]);holdonbarh(2,1,1,’FaceColor’,[1,0.2,1]);holdonbarh(3,1,1,’FaceColor’,[1,0.6,0.1]);holdonbarh(4,1,1,’FaceColor’,[0.2,0.5,0.9]);holdon如上四行命令,是

  • python lambda表达式_Python进阶

    python lambda表达式_Python进阶Lambda表达式lambda表示的是匿名函数,不需要用def来声明,一句话就可以声明出一个函数语法函数名=lambda参数:返回值注意点1.函数的参数可以有多个,多个参数之间用逗号隔

  • 未能连接一个windows服务器,Win7出现未能连接一个Windows服务的解决办法

    未能连接一个windows服务器,Win7出现未能连接一个Windows服务的解决办法近日有网友“所爱隔山海”Win7电脑在开机的时候遇到了开机很慢,开机后提示:未能连接一个Windows服务。如果遇到电脑出现未能连接一个Windows服务该如何解决呢?这就是小编今天要分享的一个电脑小技巧。Win7出现“未能连接一个Windows服务”错误提示,主要是由于电脑系统中的“SystemEventNotification”服务没有正常开启导致的,可能是用户在使用一些第三方安全软件优化…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号