e-olymp
Змагання

Azerbaijan Republican Programming Olympiad - Students FINALS

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

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

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

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

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

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

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

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #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