首页 > 代码库 > POJ1780 Code
POJ1780 Code
KEY公司开发出一种新的保险箱。要打开保险箱,不需要钥匙,但需要输入一个正确的、由
n位数字组成的编码。这种保险箱有几种类型,从给小孩子玩的玩具(2位数字编码)到军用型的
保险箱(6位数字编码)。
当正确地输入最后一位编码后,保险箱就立刻打开了。保险箱上没有“确定”键。当你输入
超过n位数字,则只有最后n位数字有效。例如,对一种4位数字编码的型号,如果正确的编码
为4567,你想输入的编码为1234567890,则保险箱的门会在你输入数字7后马上就打开了。
为了达到这种效果所需要设计的软件其实很简单。对n位数字编码的型号,保险箱始终处于
10
(n-1)
种内部状态之一。保险箱的当前状态只需用最后输入的n-1位数字表示,其中有一种状态(例
如,对前面的例子,就是456)被记为“开锁状态”。如果保险箱处于“开锁状态”,且输入最后
一位正确的数字(例如,在上面的例子中就是7),保险箱的门就打开了;否则保险箱切换到对应
的新状态。例如,如果保险箱的当前状态为456,接着输入8,则保险箱的状态切换到568。
为了开保险箱,一个繁琐的策略是一位接一位地输入所有可能的编码。然而,在最坏情况下,
这需要按键n×10
n次(有10
n组可能的编码,每个编码有n位)。而选择一个好的数字序列,最
多只需要按键10
n
+ n - 1次就可以打开保险箱了:你需要做的就是找到一个数字序列包含所有的
n位数一次且仅一次。KEY公司宣称,对军用型号(n = 6),当今最快的计算机也需要数十亿年
的时间才能找到这样的数字序列,但是很显然他们不知道有些程序员能在几分钟就能找到这样的
数字序列。
这个题目实际上就是欧拉回路的旋转鼓轮的应用。
把前一个数的后n-1位与后一个数的前n-1位相同时即能够前后相连接
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 using namespace std; 6 #define M 100000 7 int list[M]; 8 int stack[M*10];//用数组模拟栈结构 9 char ans[M*10];10 int s,a;11 void search(int v,int m)12 {13 int w;14 while(list[v]<10){15 w=v*10+list[v];16 list[v]++;17 stack[s++]=w;18 v=w%m;19 }20 }21 int main()22 {23 int n,m,i,v;24 while(scanf("%d",&n)&&n!=0){25 if(n==1) {printf("0123456789\n");continue;}26 s=0,a=0,v=0;27 m=pow(10.0,n-1);28 for(i=0;i<m;i++) list[i]=0;29 search(v,m);30 while(s){31 v=stack[--s];32 ans[a++]=v%10+‘0‘;33 v/=10;34 search(v,m);35 }36 for(i=1;i<n;i++) printf("0");37 while(a) printf("%c",ans[--a]);38 printf("\n");39 }40 return 0;41 }
POJ1780 Code