M.J的blog

algorithm,ACM-ICPC
随笔 - 39, 文章 - 11, 评论 - 20, 引用 - 0
数据加载中……

TOJ 2219. A famous math puzzle

是个关于拓展欧几里得的问题，但是很难想到。这题也是看了结题报告的~~

关于拓展欧几里得的算法http://mj-zhang.blogbus.com/tag/拓展欧几里得/

大意是给N个瓶子，每个瓶子有个容量C，给定一个容量W，每次只能（1）灌满一个，（2）倒空一个，（3）把一个的水倒给另一个，直到一个满了或者一个空了。通过三种操作，有没有可能最后达到某个瓶子里有W的水。可以这样考虑：

1）当所有C都小于W，肯定不行；

2）如果有N个瓶子，N个瓶子的容量C1, C2, C3 ... Cn必然有个最大公约数P。

证明：假设n个水壶的容量分别为C1,C2,C3…..Cn.
必要性：不管执行三种操作的那一种，壶中所含的水一定是Ｐ的整数倍．
充分性：由欧几里德算法扩展可知，必然存在整数A1,A2,A3…..An,使得
　A1*C1+A2*C2+A3*C3+…+An*Cn=W.
    如果Ai是正数，我们就用第i个壶从水源中取Ai次水；如果Ai为负数，我们就把第i个壶倒空Ai次，这样最后必会剩下Ｗ升水

  •  1 #include<stdio.h>

     2 int gcd(int a,int b){

     3     int temp;

     4     if(a<b) {temp=b;b=a;a=temp;}

     5     if(a%b==0) return b;

     6     else  return gcd(b,a%b);

     7 }
     8 int main()
     9 {
    10     int i,j,k,n,w,flag,tep,a[102];

    11     while(scanf("%d%d",&n,&w)!=EOF){

    12         if(n==0&&w==0) break;

    13         flag=0;a[n+1]=0;

    14         for(i=1;i<=n;i++){

    15             scanf("%d",&a[i]);

    16             if(a[i]>=w) flag=1;

    17         }

    18         if(flag&&n!=1){

    19             tep=gcd(a[1],a[2]);

    20             for(i=3;i<=n;i++)

    21                 tep=gcd(tep,a[i]);

    22                 if(w%tep!=0)

    23                     flag=0;

    24         }

    25         if(n==1&&a[1]!=w) flag=0;

    26         else if(n==1&&a[1]==w) flag=1;

    27         if(flag) printf("YES\n");

    28         else  printf("NO\n");

    29     }
    30 
    31 }
    •

    posted on 2010-04-23 19:41 M.J 阅读(236) 评论(0)  编辑 收藏 引用


    只有注册用户登录后才能发表评论。
    网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理