e-olymp 9107. Не разделяйте атом!

by

10

Задача

Два сумасшедших (и злых) ученых, профессор Зум и доктор Ужасный, только что получили [latex] n [/latex] атомов очень редкого элемента, которым они хотят поделиться между собой. Они решили сыграть в следующую игру:

Сначала профессор делит атомы на две непустые группы. Затем доктор берет одну группу и использует ее для своих злых целей, а другую разделяет на две непустые части. Затем профессор берет одну из частей и снова делит другую на две части, возвращая ее доктору. Игра продолжается — с каждым ходом ученый берет одну из частей и разделяет другую — пока один из игроков не будет вынужден разделить один атом. Это приводит к взрыву, и неудачный сплиттер проигрывает игру (вероятно, с его жизнью).

Зная количество атомов [latex] n [/latex], определите, кто из злодеев выживет в игре.

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

Первая строка содержит количество тестов [latex] z [/latex] [latex]left(1 leqslant zleqslant50right)[/latex] . Далее следуют описания тестов.

Каждый тест содержит одно целое число [latex] n [/latex] [latex]left(1 leqslant n leqslant10^{6}right)[/latex] — начальное количество атомов.

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

Для каждого теста выведите строку, содержащую один символ: ‘A‘, если профессор выиграет игру, и ‘B‘, если победит доктор

Тесты

№ Входные данные Выходные данные
1 2
5
6		 B
A
2 2
2
17		 A
B
3 2
11
15		 B
B
4 2
12
16		 A
A
5 3
101
110
111		 B
A
B

Код программы

Решение

Решение задачи сводиться к проверке начального количества атомов ([latex]n[/latex]), которое они хотят поделить между собой, на чётность и нечётность. По условию мы знаем, что  профессор первый делит атомы на две непустые группы, следовательно, он может воспользоваться преимуществом первого хода и задавать тон игре. Для победы профессора нужно сделать так, чтоб доктор разделил последний атом, что приведёт к его проигрышу. Значит, для победы нужно чётное количество атомов, так как только при этом случае он может придерживаться стратегии и делить на две непустые группы с нечётным количеством атомов (это может быть [latex]1[/latex] и [latex]n — 1[/latex]) до тех пор, пока его противнику не достанется [latex]1[/latex], что приведёт к взрыву (при нечётном количестве атомов, невозможно с первого хода поделить на две нечётные непустые группы).
Для проверки на чётность и нечётность, необходимо проверить равен ли нулю остаток от деления начального количества атомов ([latex]n[/latex]) на [latex]2[/latex], используя условный оператор.

Ссылки

 

Related Images:

10 thoughts on “e-olymp 9107. Не разделяйте атом!”

  1. Здравствуйте.
    1. Уберите кириллицу из постоянной ссылки.
    2. Используйте LaTex.
    3. Исправьте отступы.
    4. Поставьте соответствующие метки и рубрики.

    • Спасибо за комментарий, исправил.

  2. Здравствуй.
    1. Заголовки нужны обычные, не «стильные».
    2. Прочитайте ваше описание, у вас там опечатка. Особенно обратите внимание на последнее предложение.

    • Спасибо за комментарий, исправил.

    • Вы пишите «они хотят поделиться между собой». Поделиться можно чем-то своим с кем-то другим. Если «между собой» следует использовать «поделить» или «разделить».
    • Уберите if ( ) из последнего предложения или оформите его как фрагмент кода.
    • Теперь самое главное — пояснение ничего не поясняет. Почему в случае четного числа атомов профессор Зум выигрывает? Каким образом он это делает? По условию профессору нужно разделить атомы на две кучки. И на какие две кучки он делит?

    • Спасибо за комментарий, исправил.

    • А я бы сказал, что не исправили, а запутали. Вот это предложение почему верно: «Значит, для победы профессора нужно чтоб последний атом разделит доктор, а для победы доктора профессор, то есть для победы профессора необходимо чётное количество атомов, именно в этом случае последний атом разделит доктор, а для доктора нечётное.»?
      Если в нем слова «чётное» и «нечётное» поменять местами, то никакая логическая связь не нарушится. Значит, доказательство в нем не содержится.
      Спойлеры:
      1) Скорее всего Вы сыграли в эту игру сами с собой для первых 6-10 чисел или написали какой-то перебор, который это делает и увидели закономерность. Откуда она берется, Вам не ясно, но объяснение писать надо, вот и получилось что получилось.
      2) Доказательство можно написать по индукции. Наше утверждение очевидно верно для игр с 1 и 2 атомами. Пусть оно верно для всех игр до $2k$ атомов. Покажем, как должны действовать доктор и профессор (оба желая победить) при $2k+1$ и $2k+2$ атомах.

    • Спасибо за комментарий, исправил.

    • Спасибо за комментарий, исправил.

Добавить комментарий