Кабинки: выбор последнего
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Математика
- Словари и множества
В ряду стоят n свободных кабинок; слева и справа от ряда стены. Посетители заходят по одному, и каждый занимает кабинку так, чтобы быть как можно дальше от занятых. Для свободной кабинки L и R — число свободных кабинок между ней и ближайшей занятой (или стеной) слева и справа. Посетитель выбирает кабинку, у которой min(L, R) наибольший; при равенстве — ту, у которой наибольший max(L, R); при равенстве и здесь — самую левую. Никто не уходит.
Всего приходит k посетителей (1 ≤ k ≤ n ≤ 10^15). Верните список из двух чисел [max(L, R), min(L, R)] для кабинки, которую выбрал последний, k-й посетитель.
Пример: 4, 2 → [1, 0] (первый занимает левую из двух средних кабинок, второй — соседнюю справа от неё).
Источник: Coding Competitions Archive, codejam/2017/qualification_round/bathroom_stalls · © Google LLC · Apache-2.0 · условие переведено и дополнено