Skip to Content
CTRL K

Guess the K-th Zero (Easy Version)

Editorial oficial (C++) 

Explicación

Usamos búsqueda binaria para hallar la ubicación del kk-ésimo cero.

Para ello, fijamos un punto medio y luego comprobamos si el número de ceros en la mitad izquierda es mayor o igual que kk, o estrictamente menor que kk. Esto nos permite acotar la ubicación del kk-ésimo cero a la mitad izquierda o a la derecha.

Implementación

Complejidad temporal: O(log⁡N)\mathcal{O}(\log N)

#include <bits/stdc++.h>
using namespace std;
 
int query(int r, int k) {
	int res;
	cout << "? " << 1 << " " << r << '\n';
	cin >> res;
	return r - res <= k;
}
 
int main() {
	int n, t, k;
	cin >> n >> t >> k;
	k--;
 
	int lo = 0;
	int hi = n;
	while (hi - lo > 1) {
		int mid = (lo + hi) >> 1;
		if (query(mid, k)) {
			lo = mid;
		} else {
			hi = mid;
		}
	}
 
	cout << "! " << hi << '\n';
}
import java.io.*;
import java.util.*;
 
public class GuessTheKthZero {
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
		int t = io.nextInt();
		int k = io.nextInt() - 1;
 
		int lo = 0;
		int hi = n;
 
		while (hi - lo > 1) {
			int mid = (lo + hi) >> 1;
			if (query(mid, k)) {
				lo = mid;
			} else {
				hi = mid;
			}
		}
 
		io.println("! " + hi);
		io.flush();
		io.close();
	}
 
	private static boolean query(int r, int k) {
		Kattio io = new Kattio();
		io.println("? " + 1 + " " + r);
		io.flush();
		int res = io.nextInt();
		return (r - res <= k);
	}
 
	// CodeSnip{Kattio}
}
def query(r: int, k: int) -> bool:
	print(f"? 1 {r}")
	res = int(input())
	return r - res <= k
 
 
n, t = map(int, input().split())
k = int(input()) - 1
 
lo = 0
hi = n
while hi - lo > 1:
	mid = (lo + hi) // 2
	if query(mid, k):
		lo = mid
	else:
		hi = mid
 
print(f"! {hi}")
Fundamentos