Кабінки в убиральні#8693

Кабінки в убиральні

1 секунда

128 мегабайтів

Середня

В убиральні в рядок розташовані $n + 2$ n + 2 кабінки. Кабінки на лівому і правому кінцях завжди зайняті охоронцями. Решта $n$ кабінок призначені для користувачів.

Кожного разу, коли хтось заходить в убиральню, він намагається вибрати кабінку, максимально віддалену від інших людей. Щоб уникнути плутанини, вони дотримуються певних правил: для кожної порожньої кабінки $s$ обчислюються два значення $l_{s}$ l_s і $r_{s}$ r_s, які є кількістю порожніх кабінок між $s$ і найближчою зайнятою кабінкою зліва і справа відповідно. Потім розглядається множина кабінок з найдальшим найближчим сусідом, тобто ті $s$ , для яких $min (l_{s}, r_{s})$ \min(l_s, r_s) є максимальним. Якщо така кабінка єдина, то вибирається саме вона; в іншому випадку вибирається та з кабінок, де $max (l_{s}, r_{s})$ \max(l_s, r_s) є максимальним. Якщо і таких кабінок виявиться кілька, то вибирається найліва з них.

$k$ людей збираються увійти в убиральню. Кожен вибирає собі кабінку до приходу наступної людини. Ніхто ніколи не виходить.

Коли остання людина вибирає свою кабінку $s$ , чому дорівнює значення $max (l_{s}, r_{s})$ \max(l_s, r_s) і $min (l_{s}, r_{s})$ \min(l_s, r_s)?

Вхідні дані

Перший рядок містить кількість тестів $t$ ( $1 \leq t \leq 100$ 1 \le t \le 100). Далі слідують $t$ рядків. Кожен рядок містить два цілих числа $n$ ( $1 \leq n \leq 1 0^{18}$ 1 \le n \le 10^{18}) і $k$ ( $1 \leq k \leq n$ 1 \le k \le n).

Вихідні дані

Для кожного тесту виведіть один рядок, що містить Case #x: y z, де $x$ номер тесту (починаючи з $1$ ), $y$ дорівнює $max (l_{s}, r_{s})$ \max(l_s, r_s), $z$ дорівнює $min (l_{s}, r_{s})$ \min(l_s, r_s) - ці значення підраховані для останньої людини, яка увійшла в убиральню і вибрала кабінку $s$ .

Приклади

Приклад 1