Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI春合宿 2011-day2 guess

問題文 : 数当て

解法 :
最初に, 1の数をO(N)時間で当てる. あとは, 1の情報を元に二分探索を行う.
Σ[i = 2, 99] ceil(log_{2}i) = 580 くらいなので, 最悪でも580 + 100 < 700 回の質問で数列を確定できる.

コード :

#include <cstdio>
#include <cstring>

using namespace std;

void print(int *p, int n)
{
	for (int i = 0; i < n; i++) printf("%d\n", p[i]);
}

int main()
{
	int n, k;
	int test[128], done[128];
	int matchNum;
	
	scanf("%d", &n);
	
	memset(done, -1, sizeof(done));
	
	while (1){
		if (n == 1){
			printf("1\n");
			fflush(stdout);
			return (!scanf("%d", &matchNum));
		}
		
		k = -1;
		do {
			k++;
			for (int i = 0; i < n; i++) test[i] = (i == k ? 1 : 2); 
			print(test, n);
			fflush(stdout);
			scanf("%d", &matchNum);
		} while (matchNum != 2);
		
		done[1] = k;
		
		for (int i = 2; i <= n; i++){
			int left = 0, right = n - 1;
			while (left != right){
				int center = (left + right) / 2;
				for (int idx = left; idx <= center; idx++){
					test[idx] = (idx != done[1] ? 1 : i);
				}
				for (int idx = center + 1; idx <= right; idx++){
					test[idx] = i;
				}
				print(test, n);
				fflush(stdout);
				scanf("%d", &matchNum);
				if (matchNum == 1) left = center + 1;
				else right = center;
			}
			done[i] = right;
		}
		
		for (int i = 1; i <= n; i++) test[done[i]] = i;
		
		print(test, n);
		fflush(stdout);
		scanf("%d", &matchNum);
		
		if (matchNum != n) printf("challenge succeeded\n");
		break;
	}
	
	return (0);
}

(2 / 18 更新)

普通に 100 + 2 * log(99) のコードになっていたので修正しました.

#include <cstdio>
#include <cstring>

using namespace std;

void print(int *p, int n)
{
	for (int i = 0; i < n; i++) printf("%d\n", p[i]);
	fflush(stdout);
}

int main()
{
	int n, k;
	int test[128];
	int matchNum;
	
	scanf("%d", &n);
	
	while (1){
		if (n == 1){
			printf("1\n");
			fflush(stdout);
			return (!scanf("%d", &matchNum));
		}
		
		k = -1;
		do {
			k++;
			for (int i = 0; i < n; i++) test[i] = (i == k ? 1 : 2); 
			print(test, n);
			scanf("%d", &matchNum);
		} while (matchNum != 2);
		
		memset(test, 0, sizeof(test));
		
		test[k] = 1;
		
		for (int i = 2; i <= n; i++){
			int left = 0, right = n - i;
			int exm[128] = {0};
			while (left != right){
				int center = (left + right) / 2;
				int ctr = 0;
				for (int j = 0; j < n; j++){
					if (test[j]){
						exm[j] = (test[j] == 1 ? 2 : 1);
					}
					else if (ctr++ <= center){
						exm[j] = 1;
					}
					else {
						exm[j] = i;
					}
				}
				print(exm, n);
				scanf("%d", &matchNum);
				if (matchNum == 1) left = center + 1;
				else right = center;
			}
			int ctr = 0;
			for (int j = 0; j < n; j++){
				if (!test[j]){
					if (ctr == left){
						test[j] = i;
						break;
					}
					ctr++;
				}
			}
		}
		
		print(test, n);
		scanf("%d", &matchNum);
		
		if (matchNum != n) printf("challenge succeeded\n");
		break;
	}
	
	return (0);
}