HDOJ 1172猜数【暴力列挙】

2632 ワード

数字を当てる
Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2483    Accepted Submission(s): 1443
Problem Description
デジタルゲームはgameboyが一番好きなゲームの一つです.ゲームのルールは、コンピュータがランダムに4桁を生成し、プレイヤーがこの4桁が何なのかを推測することです.1つの数を当てるたびに、コンピュータはプレイヤーにいくつかの数字を当てて、その中にいくつかの数字が正しい位置にあることを教えます.
例えば、コンピュータがランダムに生成した数字は1122である.プレイヤーが1234を当てると、1,2の2つの数字が同時にこの2つの数の中に存在し、1がこの2つの数の中で同じ位置にあるため、コンピュータはプレイヤーに2つの数字を当てて、そのうちの1つが正しい位置にあることを教えます.プレイヤーが1111を当てると、コンピュータは2つの数字を当てて、2つが正しい位置にあることを教えてくれます.
今gameboyとコンピュータの会話の過程をあげます.あなたの任務はこの会話に基づいてこの4桁が何なのかを確定することです.
 
Input
入力データは複数組あります.各グループの第1の行為には正の整数N(1<=N<=100)があり、この会話にはN回の問答があることを示している.次のN行では、各行に3つの整数A,B,Cがある.gameboyはこの4桁をAと推測し、コンピュータはBの数字を当てたと答え、そのうちCは正しい位置にある.N=0の場合、入力データは終了する.
 
Output
各入力データのセットは、1行の出力に対応します.この会話に基づいてこの4桁を特定できれば、この4桁を出力し、できなければ「Not sure」を出力します.
 
Sample Input

   
   
   
   
6 4815 2 1 5716 1 0 7842 1 0 4901 0 0 8585 3 3 8555 3 2 2 4815 0 0 2999 3 3 0

 
Sample Output

   
   
   
   
3585 Not sure

時間は1万ミリ秒なので、暴力の列挙を試してみることができます.
#include <stdio.h>
#include <string.h>
int ans, num, num1, num2;
bool arr[10002];
char numstr[5], buf[5];

bool cmp(int k){
	int i = 0, com = 0, com1 = 0, j;
	while(k){
		buf[i++] = k % 10 + '0';
		k /= 10;
	}
	buf[i] = '\0'; //  
	for(i = 0; i < 4; ++i)
		if(numstr[i] == buf[i]) ++com1;
	
	for(i = 0; i < 4; ++i){		
		for(j = 0; j < 4; ++j)
			if(numstr[i] == buf[j]){
				++com;
				buf[j] = '9' + 1;
				break;
			}
	}
	if(com == num1 && com1 == num2) return true;
	return false;
}

void judge(){
	int i = 0;
	while(num){
		numstr[i++] = num % 10 + '0';
		num /= 10;
	}
	numstr[i] = '\0'; //  	
	for(i = 1000; i < 10000; ++i){
		if(!arr[i] && !cmp(i)){
			arr[i] = 1;
			--ans;
		}
	}
}

int main(){
	int n;
	while(scanf("%d", &n), n){
		memset(arr, 0, sizeof(arr));
		ans = 9000;
		while(n--){
			scanf("%d%d%d", &num, &num1, &num2);
			judge();
		}
		//printf("ok...%d
", ans); if(ans > 1){ printf("Not sure
"); continue; } //printf("ok...%d
", ans); for(int i = 1000; i < 10000; ++i) if(!arr[i]){ printf("%d
", i); break; } } return 0; }