1. Главная
  2. Библиотека
  3. Информационные технологии
  4. На космическом корабле есть n предателей и m членов экипажа. В каждом раунде каждый из присутствующих на корабле предателе...

На космическом корабле есть n предателей и m членов экипажа. В каждом раунде каждый из присутствующих на корабле предателей убивает одного члена экипажа. Если в начале раунда членов экипажа меньше, чем предателей, то некоторые предатели могут никого и не

«На космическом корабле есть n предателей и m членов экипажа. В каждом раунде каждый из присутствующих на корабле предателей убивает одного члена экипажа. Если в начале раунда членов экипажа меньше, чем предателей, то некоторые предатели могут никого и не»
  • Информационные технологии

Условие:

Бейбарыс играет в популярную компьютерную игру.

Действие в ней происходит на космическом корабле. На нем есть 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` больше ...

Не нашел нужную задачу?

Воспользуйся поиском

Выбери предмет