【编程比赛】《小学生游戏 》

无言的梦

最多6，那就是最多3^6=700多种情况……应该挺简单的吧……

BTW, 哪里可以提交？

Eastsun

直接把代码发上来就可以了。

“提交”?

无言的梦

只用long的算法，是问原题在哪里可以提交？

1. 
   
2. 
   
3. #include <stdio.h>
   
4. 
   
5. long num1=1985429,num2=2006;
   
6. int cnt;
   
7. char flag;
   
8. 
   
9. void exe(long x,long y,int c)
   
10. {
    
11. if (flag) return;
    
12. if (x==y) {flag=1;cnt=c;return;}
    
13. if (c>=6) return;
    
14. if (x+num1<=y) exe(x+num1,y,c+1);
    
15. if (x+num2<=y) exe(x+num2,y,c+1);
    
16. if (x*2<=y) exe(x*2,y,c+1);
    
17. return;
    
18. }
    
19. int main()
    
20. {
    
21. long a,b;
    
22. while (scanf("%d%d",&a,&b)!=EOF)
    
23. {
    
24.   flag=0;
    
25.   exe(a,b,0);
    
26.   if (flag) printf("%d\n",cnt);
    
27.   else printf("-1\n");
    
28. }
    
29. }
    
30. 
    
31. 
    

复制代码

Eastsun

楼上的代码貌似有问题（我没装C编译工具，无法测试）。

楼上的程序求出的n不一定是满足条件最小的n。

另外现在无法提交了，比赛已经结束，学校的Online Judge 暂时没有开放。

无言的梦

!!!

好象真是不一定是最小的。。。

哪个学校的OJ？

无言的梦

修改了下……

1. 
   
2. 
   
3. #include <stdio.h>
   
4. 
   
5. long num1=1985429,num2=2006;
   
6. int cnt;
   
7. 
   
8. void exe(long x,long y,int c)
   
9. {
   
10. if (x==y) {if (cnt>c) cnt=c;return;}
    
11. if (c>=6) return;
    
12. if (x+num1<=y) exe(x+num1,y,c+1);
    
13. if (x+num2<=y) exe(x+num2,y,c+1);
    
14. if (x*2<=y) exe(x*2,y,c+1);
    
15. return;
    
16. }
    
17. int main()
    
18. {
    
19. long a,b;
    
20. while (scanf("%d%d",&a,&b)!=EOF)
    
21. {
    
22.   cnt=8;
    
23.   exe(a,b,0);
    
24.   if (cnt==8) cnt=-1;
    
25.   printf("%d\n",cnt);
    
26. }
    
27. }
    
28. 
    
29. 
    

复制代码

Eastsun

【编程比赛】《小学生游戏 》
出两个题给大家，活跃一下板块气氛。

这些题是我们学校举行的编程大赛中的题目（已经结束），大家可以试试，把你代码贴上来，最好有注释，方便大家看。

ps：为简单起见，不需考虑题中的高精度数计算，用long 代替即可。



小学生游戏

  程序文件名: pupil.cpp/pupil.pas/...  
　　某天，无聊的小杰叫上几个同学玩游戏，其中有比较笨的小凤，比较傻的小雪，可爱的小鑫和自以为是的小练。他们去找聪明的小艺去给他们当裁判。判定谁取得游戏胜利。而这个游戏是：由小艺给出一个数 a ，再给出一个数 b ，经过规定的运算，使得数 a 变换成数 b ，且使用最少的变换次数 n .谁先说对这个 n ，谁就取得胜利。当然，因为都是小学生，所以假定如果n>6 ，就算是没有答案。那么裁判小艺试图通过编程来使自己尽快的获得答案。请你帮帮他吧......

问题描述：
　　题目给出数a(a是一个正整数，不超过50位)，再给出目标数b(同样是一个正整数，不超过50位)，
数的运算有三种：
　　1：使当前数加上1985429
　　2：使当前数加上2006
　　3：使当前数乘2

　　需要你求出这个最小的n，如果n>6，输出-1。(此为负一)。

例1：小艺给出数a=1，给出数b=1987437
　　那么最快我们经过3次指定运算可以使1变成1987437
　　1*2=2；（第3种变换）
　　2+1985429=1985431；（第1种变换）
　　1985431+2006=1987437；（第2种变换）

例2：小艺给出数a=1，给出数b=128
　　那么最快我们经过7次指定运算可以使1变成128
　　1*2*2*2*2*2*2*2=128（均采用第3种变换），但是因为n>6，所以按题意输出-1。




  输入 （请使用标准输入输出，而不要读写文件）

　　输入仅包含两个整数A、B，每行一个数字，0<A<1e+50，0<B<1e+50。


输出 （请使用标准输入输出，而不要读写文件）

　　输出只有一行，即为最少的变换次数 n ，若 n>6 则输出-1。


样例输入1样例输出11
19874373样例输入2样例输出21
128-1

参考代码:

1. //JAVA,支持高精度数
   
2. 
   
3. import java.util.*;
   
4. import java.io.*;
   
5. import java.math.BigInteger;
   
6. public class Pupil{
   
7. private static final int MAX_DEPTH =6;
   
8. private static final BigInteger x =new BigInteger("1985429"),y =new BigInteger("2006"),z =new BigInteger("2");
   
9. private static BigInteger iB;
   
10. private static int        depth,min;
    
11. private static void search(BigInteger a){
    
12.   if(depth>=min||depth>MAX_DEPTH||a.compareTo(iB)>0) return;
    
13.   if(iB.equals(a)){
    
14.    min =depth;
    
15.    return;
    
16.   }
    
17.   depth++;
    
18.   search(a.add(x));
    
19.   search(a.add(y));
    
20.   search(a.multiply(z));
    
21.   depth--;
    
22. }
    
23. public static int solve(BigInteger a,BigInteger b){
    
24.   iB =b;
    
25.   min =MAX_DEPTH+1;
    
26.   depth =0;
    
27.   search(a);
    
28.   if(min ==MAX_DEPTH+1) return -1;
    
29.   else                  return min;
    
30. }
    
31. public static void main(String[] args){
    
32.   Scanner scan =new Scanner(System.in);
    
33.   System.out.println(solve(scan.nextBigInteger(),scan.nextBigInteger()));
    
34. }
    
35. }
    
36.   
    
37. 
    
38.   

复制代码

1. //GVmaker
   
2. 
   
3. #define MAX_LEN   10
   
4. #define MAX_DEP    6
   
5. char numKey[]="0bnmghjtyu";
   
6. long numB,min,depth;
   
7. long getNum(int x,int y){
   
8.      char buf[MAX_LEN+2],key;
   
9.      long num,n,k;
   
10.      buf[MAX_LEN+1] =0;
    
11.      n =0;
    
12.      while(1){
    
13.         memset(buf+n,' ',MAX_LEN+1-n);
    
14.         buf[n] ='_';
    
15.         TextOut(x,y,buf,0x41);
    
16.         key =getchar();
    
17.         if(key==0x0d) break;
    
18.         if(key==0x1b) exit(0);
    
19.         if(key==23&&n>0) n--;
    
20.         else{
    
21.           for(k=0;k<10&&numKey[k]!=key;k++);
    
22.           if(k>=10||n>=MAX_LEN) continue;
    
23.           buf[n++]=k+'0';
    
24.         }
    
25.      }
    
26.      num =0;
    
27.      for(k=0;k<n;k++) num =num*10+buf[k]-'0';
    
28.      return num;
    
29. }
    
30. void search(long a){
    
31.      if(depth>=min||depth>MAX_DEP||a>numB) return;
    
32.      if(a==numB){
    
33.         min =depth;
    
34.         return;
    
35.      }
    
36.      depth++;
    
37.      search(a+1987437);
    
38.      search(a+2006);
    
39.      search(a<<1);
    
40.      depth--;
    
41. }
    
42. void main(){
    
43.      long numA;
    
44.      while(1){
    
45.           ClearScreen();
    
46.           Refresh();
    
47.           numA =getNum(2,2);
    
48.           numB =getNum(2,16);
    
49.           min  =MAX_DEP+1;
    
50.           depth=0;
    
51.           search(numA);
    
52.           if(min==MAX_DEP+1) printf("-1\n");
    
53.           else               printf("%d\n",min);
    
54.           getchar();
    
55.      }   
    
56. }
    
57.      

复制代码

[此贴子已经被作者于2006-5-10 4:05:12编辑过]