login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A276128 a(n) is the minimum cost to determine a number among 1...n by multiple guesses, where the cost of each guess is the guessed value and the answer is whether the guess is low, high, or correct. 1
0, 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 21, 24, 27, 30, 34, 38, 42, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 86, 90, 94, 98, 102, 106, 110, 114, 119, 124, 129, 134, 139, 144, 149, 154, 160, 166, 172, 178, 182, 186, 190, 194, 198, 202, 206, 210, 214, 218, 222, 226, 230, 234, 238, 242, 246, 250, 254, 258, 262, 266, 270, 274, 278, 282, 286, 290 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Definition of a(n): For a positive integer n, let the single-player game G(n) be as follows: x is a number in {1, 2, ..., n}, but unknown to the player. The player can guess as many times as he wants to determine the value of x. For each guess, the player can propose a possible value c in {1, 2, ..., n}, but such guess will cost the player c dollars. After each guess, the player will get response to show whether c<x, c=x, or c>x.

A guess strategy will consist a series of guesses to determine x. The cost of multiple guesses is defined to be the sum of the cost of each guess. The cost of guess strategy is defined to be the worse case of the cost of the guess series. The optimal guess strategy for the game G(n) is the guess strategy that has the minimum cost. a(n) is the cost of the optimal guess strategy.

LINKS

Robert Israel, Table of n, a(n) for n = 1..1000

EXAMPLE

For n = 3, the best strategy is to use only one guess with value 2. So the cost is 2.

For n = 4, the best strategy is first make a guess with value 3. If the target value is less than 3, then make another guess 1. So the cost is 3+1=4.

MAPLE

f:= proc(a, b) option remember;

local t;

     if b-a <=0 then return 0

     elif b-a = 1 then return a

     else min(seq(t + max(procname(a, t-1), procname(t+1, b)), t=a..b))

     fi

end proc:

map2(f, 1, [$1..100]); # Robert Israel, Sep 08 2016

MATHEMATICA

A276128[n_] := (

   (*Allocate Memory*)

   dp = Table[0, {first, 1, n + 1}, {last, 1, n + 1}];

   (*Buttom-up Dynamic Programming*)

   For[length = 2, length <= n, length++,

       For[first = 1, first <= n + 1 - length, first++,

           (*[First, Last) contains n elements in total*)

           last = first + length;

           dp[[first, last]] = Min[Table[mid + Max[dp[[first, mid]], dp[[mid + 1, last]]], {mid, first, last - 1}]]; ]];

   (*Achieve Results*)

   Table[dp[[1, idx + 1]], {idx, 1, n}]);

PROG

(C++)

// O(n^2) dynamic-programming:

// Let k0[first, last] = max{k: dp[first, k] <= dp[k+1, last]}, then

// max{dp[first, k], dp[k+1, last]} = dp[first, k] if k0[first, last]<k<=last

//                            else dp[k+1, last]

// So dp[first, last]

//    = min{max{dp[first, k], dp[k+1, last]}+k : first<=k<last}}

//    = min{f1[first, last], f2[first, last]}

// where f1[first, last] = min{first<=k<=k0[first, last]: dp[k+1, last]+k}

//       f2[first, last] = min{k0[first, last]<k<last: dp[first, last]+k}

//                      = dp[first, k0] + k0 + 1

int A276128(int n) {

    vector<vector<int>> dp(n + 1, vector<int>(n + 1));

    for (int last = 2; last <= n; ++last) { // for each last (included)

        int k0 = last - 1; // init k0

        deque<pair<int, int>> f1Cands; // candidates of f1

        for (int first = last - 1; first > 0; --first) { // for each first

            while (dp[first][k0 - 1] > dp[k0 + 1][last]) {

                if ((!f1Cands.empty()) && (f1Cands.front().second == k0)) {

                     f1Cands.pop_front(); // out of range, remove

                }

                --k0; // update k0

            }

            int vn = first + dp[first + 1][last]; // new entry into the range

            while ((!f1Cands.empty()) && (vn < f1Cands.back().first)) {

                f1Cands.pop_back();

            }

            f1Cands.emplace_back(vn, first);

            // update dp[first][last]

            int f1 = f1Cands.front().first;

            int f2 = dp[first][k0] + k0 + 1;

            dp[first][last] = min(f1, f2);

        }

    }

    return dp[1][n];

}

CROSSREFS

Sequence in context: A276463 A187350 A118070 * A152966 A066122 A119766

Adjacent sequences:  A276125 A276126 A276127 * A276129 A276130 A276131

KEYWORD

nice,nonn

AUTHOR

Zhiqing Xiao, Aug 21 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 13 14:58 EST 2017. Contains 295958 sequences.