ZOJ Problem Set - 1530
Find The Multiple
Time Limit: 1 Second
Memory Limit: 32768 KB
Special Judge
Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
InputThe input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero (0) terminates the input.
OutputFor each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.
Sample Input26190
Sample Output10100100100100100100111111111111111111
Source:
Asia 2002, Dhaka (Bengal)
此题DFS(BFS，看你的性格，不过我相信C coder选DFS，BFS的queue还得自己搞，C++直接模板。。。)，模拟一下高精度除法，这里在《C语言经典算法大全》里截个图
此题本人用了一个随机化才0ms，这是为了避免有“左倾”或者“右倾”——一味的搜索做字数或者右子树，左倾的话AC大概30ms。
随机化的判断开始用
if(rand()%2);//判断奇偶，不过时间代价太大，原因在于取模运算太慢
后来用
if(rand()/2>RAND_MAX);//除法也太慢
于是换成代码中的乘法
/********************************************
*problem name:zoj 1530 find the multiple *
*coder:mike *
*date:2011-02-05 *
*email:creativewang@163.com *
*note:nothing *
*********************************************/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#define MAX_LEN 99
int finish=0;
void print(int*base,int len)
{
int i=0;
while(i<len)
printf("%d",base[i++]);
putchar('/n');
return;
}
int dfs(int* lnum,int depth,int remainder,int n)
{
if(depth>MAX_LEN)
return 0;
int tmp=remainder*10;
if(!(tmp+1)%n)
{
lnum[depth-1]=1;
finish=1;
print(lnum,depth);
}
if(!(tmp%n))
{
lnum[depth-1]=0;
print(lnum,depth);
finish=1;
}
if(rand()*2>RAND_MAX)
{
if(finish)
return 0;
lnum[depth-1]=0;
dfs(lnum,depth+1,tmp%n,n);
if(finish)
return 0;
lnum[depth-1]=1;
dfs(lnum,depth+1,(tmp+1)%n,n);
}
else
{
if(finish)
return 0;
lnum[depth-1]=1;
dfs(lnum,depth+1,(tmp+1)%n,n);
if(finish)
return 0;
lnum[depth-1]=0;
dfs(lnum,depth+1,tmp%n,n);
}
return 0;
}
int main(void)
{
srand((unsigned)time(NULL));
int n;
int num[MAX_LEN];
while(scanf("%d",&n)!=EOF)
{
if(!n)
break;
finish=0;
memset(num,0,sizeof(int)*MAX_LEN);
num[0]=1;
dfs(num,2,1,n);
}
return 0;
}
另一个傻傻的TLE版本
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define BASE 10
#define MAX_LEN 120
int hash[2][BASE]= /**< hash[m][n]；m->0-1串末尾数字；n->n末位数字*/
{
{0,1,5,7,5,2,5,3,5,9},
{1,9,5,3,5,4,5,7,5,1}
};
int add(int* lnum,int len,int addend)
{
int carry=0;
int i;
lnum[len-1]+=addend;
for(i=len-1;i>=0;i--)
{
lnum[i]+=carry;
carry=lnum[i]/10;
lnum[i]%=10;
if(carry==0)
break;
}
return 0;
}
int check(int*lnum,int len)
{
while(len-->0)
if(lnum[len]>1)
return 0;
return 1;
}
int print(int* lnum,int len)
{
int i=0;
while(lnum[i]==0)
i++;
while(i<len)
printf("%d",lnum[i++]);
putchar('/n');
return 0;
}
int main(void)
{
int n;
int num[MAX_LEN];
int last;
while(scanf("%d",&n)!=EOF)
{
memset(num,0,MAX_LEN*sizeof(int));
last=n%10;
if(n==0)
break;
do
add(num,MAX_LEN,hash[num[MAX_LEN-1]][last]*n);
while(!check(num,MAX_LEN));
print(num,MAX_LEN);
}
return 0;
}
