Submission

Score: 0

User: a0ms1n

Problemset: Ice cream

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-13 12:38:22

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

int fib[20]={0};

/*
if k<guess -> fib-2 (C+=2)
   k>=guess -> fib-1 (C+=1)
*/

int guess(int n) {
    if(n==1)return 1;
    fib[0] = fib[1] = 1;
    int cur = 0;
    for(int i=2;i<=20;i++){
        fib[i] = fib[i-1]+fib[i-2];
    }
    int l=1,r=n;
    int ans = 1500;
    while(l<r){
        int b = r-l+1;
        int idx = lower_bound(fib,fib+20,b) - fib;
        int mid = l+fib[idx-2]-1;
        //cout<<l<<' '<<r<<' '<<mid<<'\n';
        if(ask(1,mid)){
            ans = mid;
            r = mid;
        }
        else{
            l = mid+1;
        }
    }
    return ans;
}