Submission

(%%T%T)

Score: 0

User: Namkhing

Problemset: Ice cream

Language: cpp

Time: 1.066 second

Submitted On: 2025-04-23 17:06:16

#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];

int guess(int N) {
    // write your solution here
    srand(seed);
    n = N;
    for (int i = 2; i <= n; i++) dp[i] = inf;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            double val = (double) (dp[j] - dp[i-j] + 1) * j / i + dp[i-j] + 1;
            if (dp[i] > val) dp[i] = val, a[i] = j;
        }
    }
    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r) / 2;
        bool f = ask(l, mid);
        if (f) r = mid;
        else l = mid + 1;
    }
    return l;
}