Submission

(%%%P%)

Score: 45

User: MisterO

Problemset: Ice cream

Language: cpp

Time: 0.003 second

Submitted On: 2025-04-23 13:04:29

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

//int N, K, coin_used=0, question_asked=0;
int f[30+5];
//
//bool ask(int L, int R) {
//    question_asked++;
//    if(question_asked > 25) {
//        printf("Ask too many times!");
//        exit(0);
//    }
//    if(L > R || L < 1 || R > N) {
//        printf("Invalid question!");
//        exit(0);
//    }
//    if(L <= K && R >= K) {
//        coin_used += 2;
//        return true;
//    } else {
//        coin_used++;
//        return false;
//    }
//}

int guess(int n) {
    // write your solution here
    f[0] = f[1] = 1;
//    printf("%d => %d\n",1,f[1]);
    for(int i=2;;i++){
    	f[i] = f[i-1]+f[i-2];
//    	printf("%d => %d\n",i,f[i]);
    	if(f[i] > 1000) break;
//    	if(f[i] > n) break;
	}
    int l = 1, r = n;
//    printf("L M I V R\n");
    while(l+1<r){
    	int mid = l+(r-l)/2;
    	int idx = upper_bound(f+1+2,f+16+1,r-l)-f-1-2;
    	int val = f[idx]+l;
//    	printf("%d %d %d %d %d\n",l,mid,idx,val,r);
//    	printf("qry(%d,%d)\n",l,val);
    	bool cal = ask(l,val);
    	if(cal){
    		r = val;
		}else{
			l = val+1;
		}
	}
	if(l == r) return l;
	else if(ask(l,l)) return l;
    return r;
}

//int main(int argc, char** argv) {
//    scanf("%d %d", &N, &K);
//    int num = guess(N);
//    if(num != K) {
//        printf("Wrong answer: expected %d but found %d", K, num);
//    } else {
//        printf("Correct answer: %d coin used", coin_used);
//    }
//    return 0;
//}