hdu 1226 슈퍼 비밀번호 bfs+나머지 판정 중

슈퍼 비밀번호
Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2808    Accepted Submission(s): 897
Problem Description
Ignatius 는 일주일 의 시간 을 들 여 전설의 보물 을 찾 았 습 니 다.보물 은 한 방 에 놓 여 있 고 방 의 문 은 비밀번호 로 잠 겨 있 습 니 다.문 옆 벽 에 비밀번호 에 대한 알림 메시지 가 있 습 니 다.
비밀 번 호 는 C 진수 이 며 주어진 M 개의 숫자 로 만 구성 되 어 있 습 니 다.또한 비밀 번 호 는 주어진 10 진법 정수 N(0<=N<=5000)의 정수 배(조건 을 만족 시 키 는 숫자 가 여러 개 존재 한다 면 가장 작은 것 은 비밀번호 입 니 다)입 니 다.만약 에 이런 비밀 번 호 를 입력 하면 문 이 열 립 니 다.이런 비밀 번 호 는 존재 하지 않 는 다 면...............................................
주의:보물 의 역사가 오래 되 었 기 때문에 그 당시 시스템 은 최대 500 개의 비밀 번 호 를 저장 할 수 밖 에 없 었 습 니 다.따라서 얻 은 암호 의 길이 가 500 보다 크 면 방문 을 열 수 없 었 습 니 다.이런 경우 에 도 비밀 번 호 는 존재 하지 않 는 다 고 여 겨 집 니 다.
 
Input
입력 한 데이터 의 첫 줄 은 하나의 정수 T(1<=T<=300)로 테스트 데이터 의 수량 을 표시 합 니 다.각 그룹의 테스트 데이터 의 첫 줄 은 두 개의 정수 N(0<=N<=5000)과 C(2<=C<=16)입 니 다.그 중에서 N 은 문제 설명 에서 주어진 10 진 정수 이 고 C 는 암호 의 진수 입 니 다.테스트 데이터 의 두 번 째 줄 은 하나의 정수 M(1<=M<=16)입 니 다.암 호 를 구성 하 는 숫자의 수량 을 표시 합 니 다.그 다음 에 M 개의 숫자 는 비밀 번 호 를 구성 하 는 숫자 를 표시 합 니 다.두 테스트 데이터 사이 에 빈 줄 이 있 습 니 다.
주의:제 시 된 M 개의 숫자 중 10 이 넘 는 숫자 가 존재 한다 면 우 리 는 A 로 10,B 로 11,C 로 12,D 로 13,E 로 14,F 로 15 를 표시 하기 로 약속 합 니 다.입력 데이터 가 모두 합 법 적 이 라 고 보장 합 니 다.
 
Output
각 그룹의 테스트 데이터 에 대해 요구 하 는 암호 가 존재 하면 이 암 호 를 출력 하고 암호 가 존재 하지 않 으 면"give me the bomb please"를 출력 합 니 다.
메모:비밀 번 호 를 구성 하 는 숫자 가 모두 사용 되 는 것 은 아 닙 니 다.비밀 번 호 는 매우 길 수 있 습 니 다.전체 변수 로 비밀 번 호 를 저장 하려 고 하지 마 십시오.나 는 비밀번호 의 최고 위 치 는 0 이 아니 라 는 것 을 보증한다.
 
Sample Input
3
22 10
3
7 0 1
2 10
1
1
25 16
3
A B C
 
Sample Output
110
give me the bomb please
CCB
Hint
Hint
 
Huge input, scanf is recommended.
제목 은 말 할 필요 가 없습니다.중국어 입 니 다.
처음에는 생각 이 없 었 다.문 제 를 보고 풀 었 더 니 이 문 제 는 동 여 판 으로 다시 풀 수 있다 는 것 을 알 게 되 었 다.
우리 모두 알 고 있 습 니 다(n+m)%mod=(n%mod+m%mod)%mod
이 문제 에 대해 서도 다음 과 같은 결론 을 얻 을 수 있다.
하면,만약,만약... 높 은 자리 에서 낮은 자리 까지 ab, ;
그러면 이 거 는 이 숫자 에 맞 춰 서... , (a*10+b)%mod 는(a%mod)*10+b)%mod 에 해당 합 니 다.여기 mod 는 n 이 고 10 은 진법 c 입 니 다.
이 문 제 를 알 게 되면 기본적으로 이 문제 의 절반 을 해결 할 수 있다.
그리고 검색 을 해 보 겠 습 니 다. 고위 구조 에서 낮은 위치 까지 끊임없이 높 은 자 리 를 모형 으로 만 든 다음 에 사용한다. ((a%mod)*10+b)%mod 이 식 으로 다음 모드 를 구 합 니 다.
그리고 얻 은 모든 모델 은 가장 작은 숫자 로 얻 을 수 있 습 니 다.왜냐하면 우리 가 검색 하 는 과정 에서 숫자 가 어 릴 때 부터 큰 것 이기 때문에 가장 먼저 얻 은 나머지 가 가장 좋 습 니 다.뒤의 것 을 다시 찾 으 면 사용 하지 않 습 니 다.
last 를-1 로 초기 화하 고 last[i]!=-1.그러면 여 이 는 이미 지 났 기 때문에 더 이상 입단 하지 않 을 것 이다.이것 이 바로 여 판 중 이다.

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std; 

char num[6000];//    dig 
int last[6000];//       : last[i]=j   i         j      
int dig[20];//         
int len[6000];//   i         ,             500  
 
void find(int tem)
{
	if(last[tem]!=0)
		find(last[tem]);
	printf("%c",num[tem]);
}
void bfs(int n,int c,int m)
{
	sort(dig,dig+m);
	queue<int> q;
	memset(last,-1,sizeof last);
	if(n==0)
	{
		if(dig[0]==0) printf("0
");  
        else printf("give me the bomb please
");  
        return ;  
	}


	for(int i=0;i<m;i++)
	{
		if(dig[i])//      0;
		{
			int tem=dig[i]%n;
			if(last[tem]==-1)
			{
				q.push(tem);
				if(dig[i]<=9)
					num[tem]=dig[i]+'0';
				else
					num[tem]=dig[i]+'A'-10;
				last[tem]=0;
				len[tem]=1;
			}
		}
	}

	int now;
	while(!q.empty())
	{
		now=q.front();
		q.pop();
		if(now==0) break;
		if(len[now]==500)
		{
			printf("give me the bomb please
");  
			return ;
		}

		for(int i=0;i<m;i++)
		{
			int tem=(now*c+dig[i])%n;
			if(last[tem]==-1)
			{
				last[tem]=now;
				if(dig[i]<=9)
					num[tem]=dig[i]+'0';
				else
					num[tem]=dig[i]+'A'-10;
				q.push(tem);
				len[tem]=len[now]+1;
			} 
		} 
	} 
	if(now!=0)
	{
		printf("give me the bomb please
");  
		return ;
	}
	find(0);
	puts("");
	return ;
}



int main()
{
	int t,n,c;// n      c  
	int m;//m    
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&c);
		scanf("%d",&m);


		for(int i=0;i<m;i++)
		{
			char tem[2];
			scanf("%s",tem);
			if(tem[0]>='0'&&tem[0]<='9')
				dig[i]=tem[0]-'0';
			else
				dig[i]=tem[0]-'A'+10;
		}
		bfs(n,c,m);
	}
	return 0;
}
/*


3
22 10
3
7 0 1

*/