[UVA][dp] 10826 - Hot or Cold
Problem G
Hot
or Cold?
Input: Standard Input
Output: Standard Output
You are playing a number-guessing game with a friend. He is thinking of an integer between 1 and N
inclusive. You have unlimited guesses
to figure it out, but of course you want to do it in as few guesses as
possible. He won't actually tell you if
you guess correctly; the only information he will give you is that, on every
guess except the first, he will say "warmer" or "colder"
depending on whether this guess is nearer or farther than the previous guess.
(If the distance is exactly the same, either may be said) When you are certain that your last guess
was correct, you tell your friend, winning the game.
Note that your guesses must all be genuine guesses, consistent with all the information you have. You can't guess a number that has no chance of being correct, even though you might want to!
At worst, how many guesses will it take you?
Input
Every case consists of a line containing N, 1≤N≤300. Input will end on a case where N=0. This case should not be processed.
Output
For each case, output a line containing the maximum number of guesses it should take to guess the number.
Sample Input Output for Sample Input
|
75 75 0 |
10 guess(es) required. 10 guess(es) required. |
Problem setter: Derek Kisman
Special Thanks: Md. Kamruzzaman
給 [1, n] 範圍，其中有一個數字已經給定了。
接著開始猜這個數字為何，每次新選的數字，會回答比前一個選的數字靠近還是遠。
如果距離相同時，隨便一個都有可能。求猜數字的最少次數為何。
題目解法：
由於第一次選的數字沒有給定，第一次選的數字也不會做任何回答，這部分需要窮舉來完成。
dp[i][j] 表示 [1, i] 前一個數字選 j 的情況。
接著窮舉所有可能下一個選的位置，取小值。
對於一個新選的位置會遭遇到靠近或遠離，兩個可能問題中取大。
// 這一題得麻煩點在於初始化，而劃分回小問題時，j < 0 是有可能的。
// 也有可能 j > i，我們盡可能將這問題映射到同一個子問題中。
// 嘗試了很多 WA 才拿到 AC，以下的代碼只剩下神知道了。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[305][605]; // [size][last_guess]
int used[305][605] = {};
#define OFFSET 300
int dfs(int n, int prev_guess) {
if(n <= 1)
return 0;
if(n == 2) {
return (prev_guess == 1 || prev_guess == 2) ? 2 : 3;
}/*
if(n == 3)
return 3;*/
if(prev_guess > n)
prev_guess = - (prev_guess - n - 1);
if(prev_guess + OFFSET < 0 || prev_guess + OFFSET >= 605 || prev_guess > n)
puts("err2");
// printf("%d %d\n", n, last_guess);
if(used[n][prev_guess + OFFSET])
return dp[n][prev_guess + OFFSET];
int &ret = dp[n][prev_guess + OFFSET];
ret = 0xfffffff;
used[n][prev_guess + OFFSET] = 1;
int m;
for(int i = 1; i <= n; i++) {
if(i + prev_guess < 0)
m = (i + prev_guess-1) / 2;
else
m = (i + prev_guess) / 2;
//if(m == n || n-m+1 >= n) continue;
//if(n-m+1 == n && i-m+1 == prev_guess) continue;
if(i == prev_guess) continue;
//printf("[%d %d] %d %d %d %d\n", n, prev_guess, m, i, n-m+1, i-m+1);
if(i == prev_guess-1)
ret = min(ret, max(dfs(i, i), dfs(n-i, 0))+1);
else if(i == prev_guess+1)
ret = min(ret, max(dfs(i-1, i), dfs(n-i+1, 1))+1);
else if(i < prev_guess) {
if((prev_guess - i)%2 != 0)
ret = min(ret, max(dfs(m, i), dfs(n-m, i-m))+1);
else {
if(n-m+1 > n) puts("err1");
ret = min(ret, max(dfs(m, i), dfs(n-m+1, i-m+1))+1); // hotter, colder
}
}
else {
if((i - prev_guess)%2 != 0)
ret = min(ret, max(dfs(n-m, i-m), dfs(m, i))+1);
else {
if(n-m+1 > n) //printf("err2 %d %d %d\n", prev_guess, n, i);
ret = min(ret, dfs(n, i)+1);
else
ret = min(ret, max(dfs(n-m+1, i-m+1), dfs(m, i))+1); // hotter, colder
}
}
}
return ret;
}
int main() {
int n;
//freopen("in.txt","r+t",stdin);
//freopen("out.txt","w+t",stdout);
while(scanf("%d", &n) == 1 && n) {
int ret = 0xfffffff;
for(int i = 1; i <= n; i++)
ret = min(ret, dfs(n, i));
printf("%d guess(es) required.\n", ret + 1);
}
return 0;
}