Problem F:The Balance(扩展欧几里德)

2023-11-07 00:48

本文主要是介绍Problem F:The Balance(扩展欧几里德),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

POJ2142http://poj.org/problem?id=2142

扩展欧几里德+(x+y)取最小

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. 

 

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 Code

#include<iostream>
using namespace std;
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y)
{if(!b){x=1;y=0;return a;}ll gcd=exgcd(b,a%b,x,y);ll temp=x;x=y;y=temp-a/b*y;return gcd;
}
int main()
{ll a,b,d;ll gcd;ll x1,x2,y1,y2,ans1,ans2;while(cin>>a>>b>>d&&(a+b+d)){ll x,y;gcd=exgcd(a,b,x,y);x1=x*d/gcd;x1=(x1%(b/gcd)+(b/gcd))%(b/gcd);y1=(d-a*x1)/b;if(y1<0)y1=-y1;ans1=x1+y1;y2=y*d/gcd;y2=(y2%(a/gcd)+(a/gcd))%(a/gcd);x2=(d-b*y2)/a;if(x2<0)x2=-x2;ans2=x2+y2;if(ans1<=ans2)cout<<x1<<' '<<y1<<endl;else cout<<x2<<' '<<y2<<endl;}return 0;
}

这篇关于Problem F:The Balance(扩展欧几里德)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/360115

相关文章

Java常用注解扩展对比举例详解

《Java常用注解扩展对比举例详解》:本文主要介绍Java常用注解扩展对比的相关资料,提供了丰富的代码示例,并总结了最佳实践建议,帮助开发者更好地理解和应用这些注解,需要的朋友可以参考下... 目录一、@Controller 与 @RestController 对比二、使用 @Data 与 不使用 @Dat

Spring组件初始化扩展点BeanPostProcessor的作用详解

《Spring组件初始化扩展点BeanPostProcessor的作用详解》本文通过实战案例和常见应用场景详细介绍了BeanPostProcessor的使用,并强调了其在Spring扩展中的重要性,感... 目录一、概述二、BeanPostProcessor的作用三、核心方法解析1、postProcessB

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

Spring框架5 - 容器的扩展功能 (ApplicationContext)

private static ApplicationContext applicationContext;static {applicationContext = new ClassPathXmlApplicationContext("bean.xml");} BeanFactory的功能扩展类ApplicationContext进行深度的分析。ApplicationConext与 BeanF

PHP7扩展开发之数组处理

前言 这次,我们将演示如何在PHP扩展中如何对数组进行处理。要实现的PHP代码如下: <?phpfunction array_concat ($arr, $prefix) {foreach($arr as $key => $val) {if (isset($prefix[$key]) && is_string($val) && is_string($prefix[$key])) {$arr[

PHP7扩展开发之字符串处理

前言 这次,我们来看看字符串在PHP扩展里面如何处理。 示例代码如下: <?phpfunction str_concat($prefix, $string) {$len = strlen($prefix);$substr = substr($string, 0, $len);if ($substr != $prefix) {return $prefix." ".$string;} else

PHP7扩展开发之类型处理

前言 这次,我们将演示如何在PHP扩展中如何对类型进行一些操作。如,判断变量类型。要实现的PHP代码如下: <?phpfunction get_size ($value) {if (is_string($value)) {return "string size is ". strlen($value);} else if (is_array($value)) {return "array si

PHP7扩展开发之依赖其他扩展

前言 有的时候,我们的扩展要依赖其他扩展。比如,我们PHP的mysqli扩展就依赖mysqlnd扩展。这中情况下,我们怎么使用其他扩展呢?这个就是本文讲述的内容。 我们新建立一个扩展,名字叫 demo_dep , 依赖之前的say扩展。 在demo_dep扩展中,我们实现demo_say方法。这个方法调用say扩展的say方法。 代码 基础代码 确保say扩展的头文件正确安装到了php