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

相关推荐

  • Java 文件上传 MultipartFile

    Java 文件上传 MultipartFileJava文件上传MultipartFile1. 配置MultipartResolver:用于处理表单中的file

  • sin的傅里叶变换公式_傅里叶变换的由来及复数下的傅里叶变换公式证明

    sin的傅里叶变换公式_傅里叶变换的由来及复数下的傅里叶变换公式证明1、考虑到一个函数可以展开成一个多项式的和,可惜多项式并不能直观的表示周期函数,由于正余弦函数是周期函数,可以考虑任意一个周期函数能否表示成为一系列正余弦函数的和。假设可以,不失一般性,于是得到:f(t)=A0+∑(n=1,∞)Ansin(nωt+Φn)2、将后面的正弦函数展开:Ansin(nωt+Φn)=AnsinΦncosnωt+AncosΦnsinnωt令a0/2=A0,an…

  • Python列表建议收藏

    在python中有六种内建的序列:列表、元祖、字符串、Unicode字符串、buffer对象和xrange对象。通用序列操作:1.索引(indexing)2.分片(slicing)3.

    2021年12月18日
  • php jquery教程下载,jquery 怎么下载

    php jquery教程下载,jquery 怎么下载下载jquery的方法:首先使用百度搜索“jQuery”;然后点击进入jQuery网站;最后找到适合开发的版本后进行下载即可。本教程操作环境:windows7系统、jquery3.2.1版,该方法适用于所有品牌电脑。下载jquery的方法:首先,打开您的浏览器,无论是什么浏览器都可以,只要可以连接上网络就行。使用百度搜索“jQuery”.您可以选择下图所示量项中的一项,并点击进入jQuery网站。…

  • springboot之项目打包

    springboot之项目打包

  • 广东地区电信官方DNS服务器

    广东地区电信官方DNS服务器以下是广东地区电信官方DNS服务器,简单记录,以备后用!主解析服务器:202.96.128.143202.96.128.68202.105.80.210缓存服务器(亦可作DNS解析之用)cache-b

发表回复

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

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