Контест Senior Бинарный поиск обновлено
k-е число в таблице умножения
Условие
Таблица умножения n × m содержит числа i · j для 1 ≤ i ≤ n, 1 ≤ j ≤ m. Выпишем все n · m чисел по неубыванию. Какое число окажется на k-м месте?
Ввод: три числа n, m, k (1 ≤ n, m ≤ 10⁵, 1 ≤ k ≤ n · m).
Вывод: k-е по порядку число.
Пример 1
Ввод:
3 3 5
Вывод:
3
Пример 2
Ввод:
2 3 6
Вывод:
6
Как подойти
Подсказки: 2
- Ищите не позицию, а значение: бинарный поиск по x.
- Сколько чисел не больше x в строке i? min(m, x // i).
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.