Submission

(PPPPP)

Score: 100

User: MisterO

Problemset: Ice cream

Language: cpp

Time: 0.002 second

Submitted On: 2025-04-23 13:48:26

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

//int N, K, coin_used=0, question_asked=0;
//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
    int f[30+5];
    int i=1; //Fibonacci Search
    f[0] = f[1] = 1;
    do{
    	i++;
    	f[i] = f[i-1]+f[i-2];
	}while(f[i]<=n);
    int offset = 0;
    int l = 1, r = n;
    while(l+1<r){
    	int idx = min(offset+f[i-2],n);
//    	cout<<l<<' '<<idx<<' '<<r<<'\n';
    	if(ask(l,idx)){
			r = idx;
			i -= 2;
		}else{
    		l = idx+1;
    		i -= 1;
    		offset = idx;
		}
	}
	if(l == r) return l;
	else if(ask(l,l)) return l;
	else 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;
//}