Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 2490 | Accepted: 1091 |
Description
You are asked to help her by calculating how many weights are required.
Input
The end of the input is indicated by a line containing three zeros separated by a space. It is not a dataset.
Output
- 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账号...