Submission

(-----)

Score: 0

User: Namkhing

Problemset: Ice cream

Language: cpp

Time: 0.002 second

Submitted On: 2025-04-23 17:31:41

#include "ice_cream.h"
#include <bits/stdc++.h>
using namespace std;

const int seed = 1;
const double inf = 1e9;

const int N = 1510;
int n, a[N];
double dp[N];

double solve(int i) {
    if (dp[i] != inf) return dp[i];
    for (int j = 1; j <= i / 2; j++) {
        double val = (double) (solve(j) - solve(i - j) + 1) * j / i + solve(i - j) + 1;
        if (dp[i] > val) dp[i] = val, a[i] = j;
    }
    return dp[i];
}

int guess(int N) {
    // write your solution here
    srand(seed);
    n = N;
    solve(n);
    int l = 1, r = n;
    while (l < r) {
        int sz = r - l + 1;
        int opt = a[sz];
        int b = l + opt;
        int e = r - opt;
        int x = rand() & 1;
        if (x) {
            bool f = ask(l, b - 1);
            if (f) r = b - 1;
            else l = b;
        }
        else {
            bool f = ask(e + 1, r);
            if (f) l = e + 1;
            else r = e;
        }
    }
    return l;
}