№ 14292

В Цветочном городе живёт $99^2$ коротышек. Некоторые из коротышек рыцари (всегда говорят правду), а остальные — лжецы (всегда лгут). Дома в городе расположены в клетках квадрата $99\times99$ (всего $99^2$ домов, расположенных в 99 вертикальных и в 99 горизонтальных улицах). В каждом доме живет ровно один коротышка. Номер дома обозначается парой чисел $(x;y)$, где $1\leqslant x\leqslant99$ — номер вертикальной улицы (номера возрастают слева направо), а $1\leqslant y\leqslant99$ — номер горизонтальной улицы (номера возрастают снизу вверх). Цветочным расстоянием между двумя домами с номерами $(x_1;y_1)$ и $(x_2;y_2)$ называется число $\rho=|x_1-x_2|+|y_1-y_2|$. Известно, что на каждой улице — вертикальной или горизонтальной — проживает не менее $k$ рыцарей. Кроме того, все коротышки знают, в каком доме живет рыцарь Знайка. Вы хотите найти его дом, но не знаете, как выглядит Знайка. Вы можете подходить к любому дому и спрашивать живущего в нем коротышку: «Каково цветочное расстояние от вашего дома до дома Знайки?». При каком наименьшем $k$ вы можете гарантированно найти дом Знайки?