SGU 126 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=126

126. Boxes

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

There are two boxes. There are A balls in the first box, and B balls in the second box (0 < A + B < 2147483648). It is possible to move balls from one box to another. From one box into another one should move as many balls as the other box already contains. You have to determine, whether it is possible to move all balls into one box.

现在有两个盒子。第一个盒子有A个球,另一个盒子有B个球 (0 < A + B < 2147483648).有一种移动球的方式.从一个盒子移动球到另一个盒子,但要求被移动的球的数量要与另一个盒子已有的球的数量相同.你必须算出是否有可能将其中一个盒子清空。

Input

The first line contains two integers A and B, delimited by space.

第一行包含两个整数 A 和 B,以空格隔开.

Output

First line should contain the number N - the number of moves which are required to move all balls into one box, or -1 if it is impossible.

第一行输出整数 N -如果可以清空其中一个盒子所需要的移动次数,如果不可能,则输出-1.

Sample Input

2 6

Sample Output

2

这是一道我不是很拿手的找规律的题。不过在纸上多写几组规律就出来了。

a->a/gcd(a,b)
b->b/gcd(a,b)
if a+b=2^k then
  print k
else
  print -1

CODE

#include<stdio.h>
 
int gcd(int a,int b)
{
  int r;
  while(b){
      r=a%b;
      a=b;
      b=r;
  }
  return a;
}
 
int main()
{
  int a,b,c,k;
  scanf("%d%d",&a,&b);
  c=gcd(a,b);
  a/=c;b/=c;
  a+=b;
  b=1;k=0;
  while(b<a){
      b*=2;
      k++;
      if(b==a){
	  printf("%dn",k);
	  break;
      }else if(b>a||b<0){
	  printf("-1n");
	  return 0;
      }
  }
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:

Leave a Comment

NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>