/** * Implement binary search, with some smart boundary management. This should * be enough to stay in the boundaries. Based on Arrays#binarysearch(). * Reminds me of the article of programming pearls, Column 4 writing correct programs. * Implementing binary search remains error-prone. */ fun main() { val input = System.`in`.bufferedReader() val output = System.out.bufferedWriter() val (maxX, maxY) = input.readLine().split(" ", limit = 2).map { it.toLong() } var bestX = 0 var bestY = 0L var currentX = 1 var low = 1L var high = maxY while (currentX <= maxX) { // can't attach debuger, but can print to system.err for debugging output. // System.err.println("x=$currentX range=[$low,$high] best: [$bestX, $bestY]") val mid = ((low + high) / 2).coerceAtMost(maxX) output.write("? $currentX $mid\n") output.flush() when (input.readLine()) { "sky" -> { high = mid - 1 if (high < low && mid - 1 > bestY) { bestY = mid - 1 bestX = currentX } } "building" -> { low = mid + 1 if (high < low && mid > bestY) { bestY = mid bestX = currentX } } } if (high < low) { low = bestY + 1 high = maxY currentX++ } } output.write("! $bestX $bestY\n") output.flush() }