eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Кабинки в уборной

Кабинки в уборной

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

В уборной в ряд стоят n + 2 кабинок. Кабинки на левом и правом концах постоянно заняты охранниками. Другие n кабинок предназначены для пользователей.

Всякий раз, когда кто-то входит в ванную, он старается выбрать кабинку, максимально удаленную от других людей. Чтобы избежать путаницы, они следуют определенным правилам: для каждой пустой кабинки s вычисляются два значения l[s] и r[s], каждое из которых является числом пустых кабинок между s и ближайшей занятой кабинкой слева и справа соответственно. Затем рассматривается множество кабинок с самым дальним ближайшим соседом, то есть теми s, для которых min(l[s], r[s]) является максимальным. Если такая кабинка единственна, то выбирается именно она; в противном случае выбирается та из кабинок, где max(l[s], r[s]) является максимальным. Если и таких кабинок окажется несколько, то выбирается самая левая из них.

k людей собираются войти в уборную. Каждый выбирает себе кабинку до прихода следующего человека. Никто никогда не уходит.

Когда последний человек выбирает свою кабинку s, чему равно значение max(l[s], r[s]) и min(l[s], r[s])?

Входные данные

Первая строка содержит количество тестов t (1t100). Далее следуют t строк. Каждая строка содержит два целых числа n (1n10^18) и k (1kn).

Выходные данные

Для каждого теста выведите одну строку содержащую Case #x: y z, где x номер теста (начиная с 1), y равно max(l[s], r[s]), z равно min(l[s], r[s]) - эти значения подсчитаны для последнего человека, вошедшего в уборную и выбравшего кабинку s.

Пример

Входные данные #1
5
4 2
5 2
6 2
1000 1000
1000 1
Выходные данные #1
Case #1: 1 0
Case #2: 1 0
Case #3: 1 1
Case #4: 0 0
Case #5: 500 499
Источник 2017 Google Code Jam, Квалификационный раунд, Задача C