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); }