boj 62

Description

    champ最近发现了一种奇怪的数，这种数是由m个连续的x后面跟上n个连续的y组成的十进制数，形如xxx...xxxyyy...yyy并且满足条件(0 < x <= 9, 0 <= y <= 9, x!=y)。
    由于这种数的特性，champ把这种数叫做二部数。
    现在champ有一个正整数K，他希望找到一个最小的(x,y)二部数使得它是champ给出的正整数的整数倍。

Input
第一行测试组数 N
N行，每行三个数 K x y (0 < K <= 65536,x和y满足描述中的条件)


Output
N行，如果结果存在，两个数m n,以空格分隔。如果结果不存在，输出"No such number!" 

Sample Input

4
370 1 0
500 3 4
573 5 7
9997 5 9

Sample Output

3 1
No such number!
22 16
48 36

Source
champ

 

对于xxxx，可以构造出xxxxy和xxxxx，通过bfs，位数从2开始，构造二部数，需要注意x和y的大小关系，找出最小的二部数

代码：

#include<stdlib.h>
#include<stdio.h>
#include<queue>
using namespace std;
#define N 65536
bool flag[N];
bool flagx[N];
struct node{
	int x;
	int y;
	int num;
	bool flagx;
};
int main()
{
	int n;
	scanf("%d",&n);
	while(n--)
	{
		int k,x,y,numx = -1,numy = -1;
		memset(flag,0,sizeof(flag));
		memset(flagx,0,sizeof(flagx));
		queue<node>q;
		scanf("%d %d %d",&k,&x,&y);
		node tmp;
		tmp.x = 1;
		tmp.y = 0;
		tmp.num = x%k;
		tmp.flagx = true;
		q.push(tmp);
		while(q.size()!=0)
		{
			node temp = q.front();
			if(numx!=-1&&numx+numy<temp.x+temp.y)break;
			int num = (temp.num*10+y)%k;
			if(num==0)
			{
				if(numx==-1||numx+numy>temp.x+temp.y+1)
				{
					numx = temp.x;
					numy = temp.y+1;
				}
				else if(numx+numy==temp.x+temp.y+1)
				{
					if((x>y&&numx>temp.x)||(x<y&&numx<temp.x))
					{
						numx = temp.x;
						numy = temp.y+1;
					}
				}
			}
			else
			{
				if(temp.flagx==true)
				{
					int tmpnum = (temp.num*10+x)%k;
					if(flagx[tmpnum]==false)
					{
						tmp.x = temp.x+1;
						tmp.y = temp.y;
						tmp.num = tmpnum;
						tmp.flagx = temp.flagx;
						q.push(tmp);
					}
					flagx[tmpnum] = true;
				}
				if(flag[num]==false)
				{
					flag[num] = true;
					temp.y++;
					temp.num = num;
					temp.flagx = false;
					q.push(temp);
				}
			}
			q.pop();
		}
		if(numx==-1)printf("No such number!\n");
		else printf("%d %d\n",numx,numy);
	}
}