Условие:
Бейбарыс играет в популярную компьютерную игру.
Действие в ней происходит на космическом корабле. На нем есть n
предателей и m
членов экипажа (всего n+m
игроков). В каждом раунде каждый из присутствующих на корабле предателей убивает одного члена экипажа (конечно же, никакие два предателя не могут убить одного члена экипажа). Если в начале раунда членов экипажа меньше, чем предателей, то некоторые предатели могут никого и не убить. После этого, если на корабле останется хотя бы один член экипажа, происходит общее собрание членов экипажа, и они выбрасывают одного из предателей в открытый космос, в результате чего предатель умирает и не может в дальнейшем убивать. Если все предатели или все члены экипажа оказываются мертвы, игра заканчивается, иначе начинается новый раунд.
Бейбарысу стало интересно, кто же останется в конце игры: предатели или члены экипажа? Также он задался вопросом: через сколько раундов закончится игра? Помогите ему узнать это!
Входные данные
В первой строке записано целое число t
(1≤t≤105
) — количество тестовых случаев. Далее следуют t
строк, в каждой из которых содержится описание каждого тестового случая.
Описание тестового случая состоит из двух записанных через пробел целых чисел n
и m
(1≤n≤2×109,1≤m≤1018
) — количество предателей и членов экипажа, соответственно.
Выходные данные
Для каждого из тестовых случаев выведите ответ в описанном ниже формате.
В первой строке выведите "Impostors" (без кавычек), если в конце игры останутся предатели, и "Crewmates" (без кавычек), если останутся члены экипажа.
Во второй строке выведите одно число — количество раундов, произошедших до конца игры.
Система оценки
Подзадача Дополнительные ограничения Баллы Необходимые подзадачи
0
Тесты из условия 0
—
1
1≤n,m≤103
20
—
2
m≤2×109
30
1
3
— 50
1
, 2
Пример
Входные данныеСкопировать
2
2 10
2 3
Выходные данныеСкопировать
Crewmates
2
Impostors
2
Примечание
Рассмотрим первый пример. После первого раунда будут убиты двое членов экипажа, после чего один из двух предателей будет отправлен в открытый космос. Далее начнется второй раунд, в котором будет убит еще один член экипажа, а последний предатель отправится за борт. В итоге после двух раундов семеро членов экипажа останутся в живых.
Рассмотрим второй пример. После первого раунда на борту космического корабля останется один член экипажа и один предатель. Во втором раунде член экипажа будет убит, в результате чего общее собрание не состоится, а значит, предатель останется жив.
Решение:
Чтобы решить задачу, давайте разберем, как происходит игра и как можно вычислить, кто останется в конце и сколько раундов пройдет.
Шаг 1: Понимание механики игры
1. Убийства: Каждый предатель убивает одного члена экипажа. Если предателей больше, чем членов экипажа, то некоторые предатели могут не убить никого.
2. Собрание: Если после убийств остались члены экипажа, они выбрасывают одного предателя.
3. Конец игры: Игра заканчивается, когда либо все предатели, либо все члены экипажа мертвы.
Шаг 2: Определение условий окончания игры
- Если количество предателей
n больше или равно количеству членов экипажа m, то предатели выиграют, так как они смогут убивать членов экипажа до тех пор, пока не останется один или меньше.- Если
n m, то члены экипажа могут победить, но нужно учитывать, сколько раундов пройдет.Шаг 3: Подсчет раундов
1. В каждом раунде:
- Члены экипажа уменьшаются на
min(n, m).- После этого, если
m все еще больше 0, один предатель будет выброшен.2. Количество раундов можно вычислить следующим образом:
- Если
n m, то в каждом раунде m уменьшается на n и n уменьшается на 1 (если m больше 0).- Это продолжается до тех пор, пока
m не станет меньше или равно n.Шаг 4: Алгоритм
1. Если
n = m, выводим Impostors и количество раундов, равное m.2. Если
n m, считаем количество раундов:-
rounds = m // n (полные раунды, когда предатели убивают всех членов экипажа)-
remaining_crew = m % n (оставшиеся члены экипажа после полных раундов)- Если
remaining_crew 0, то еще один раунд, чтобы выбросить предателя.- В итоге, если
remaining_crew 0, то члены экипажа победят, иначе предатели.Шаг 5: Реализация
Теперь реализуем это в коде:
Теперь проверим на примерах: 1. Вход: → , 2. Вход: → , Таким образом, мы можем решить задачу, используя описанный алгоритм.