UVA571Jugs题解--简单数论(其实是瞎搞)

题目链接

https://cn.vjudge.net/problem/UVA-571

分析

刚做了道倒水问题的题想看看能不能水二倍经验,结果发现了这道题

题意翻译:https://www.cnblogs.com/devymex/archive/2010/08/04/1792288.html

设A容量\(x\),B容量\(y\)

我们把将水倒入A视为\(+x\),将倒空B视为\(-y\),若A满,就倒入B视为\(-x\)

由于\(a,b\)是互质的,根据裴蜀定理一定有\(x,y\)保证有\(ax+by=gcd(a,b)=1\),又因为\(y>=c>=x>=0\)那么也就保证了一定存在非负整数\(x\)和一个整数\(y\)使得\(ax+by=c\).

于是一开始我的思路是运用扩展\(GCD\)求出一组解后将\(x\)转化为一个非负数解.然后按步骤模拟就好了

然而在我写模拟步骤时忽然发现完全不用扩欧啊,我们的模拟过程其实就是:

若A空,则将A倒满
若B满,将B倒空
若A满,将A中水倒入B中

由于题目要求输出一种解就好了于是我们直接模拟就好了,至于为什么会这样,我好像还找不到较为严谨的数学证明

代码

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cctype>

#include <vector>

#define ll long long

#define ri register int

using std::min;

using std::max;

using std::swap;

template <class T>inline void read(T &x){

	x=0;int ne=0;char c;

	while(!isdigit(c=getchar()))ne=c=='-';

	x=c-48;

	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;

	x=ne?-x:x;return ;

}

int ex_gcd(int a,int b,int x,int y){

	if(!b){

		x=1,y=0;

		return a;

	}

	int d=ex_gcd(b,a%b,x,y);

	int z=x;x=y,y=z-(a/b)*y;

	return d;

}

int a,b,c;

int main(){

	int x,y,lef;

	int bot[3];

	while(scanf("%d %d %d",&a,&b,&c)!=EOF){

		//int d=ex_gcd(a,b,x,y);

		bool flag=1;

		if(b==c){

			puts("fill B");

			puts("success");

			flag=0;

		}

		bot[1]=bot[2]=0;

		//if(x>0){

			while(1&&flag){

				if(bot[2]==c){

					puts("success");

					break;

				}

				if(!bot[1]){

					bot[1]=a;

					puts("fill A");

				}

				else if(bot[2]==b){

					puts("empty B");

					bot[2]=0;

				}

				else if(bot[1]){

					lef=b-bot[2];

					if(lef<bot[1]){

						bot[1]-=lef;

						bot[2]+=lef;

					}

					else {

						bot[2]+=bot[1];

						bot[1]=0;

					}

					puts("pour A B");

				}

				//printf("%d %d\n",bot[1],bot[2]);

				//system("PAUSE");

			}

		//}

		/*else{

			int k=(-c*x)/b+1;

			x=c*x+k*b,y=c*y-k*a;

		}*/

	}

	return 0;

}

巴特西

UVA571Jugs题解--简单数论(其实是瞎搞)

题目链接

分析

代码

最新文章

热门文章