Задача
Два сумасшедших (и злых) ученых, профессор Зум и доктор Ужасный, только что получили [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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> using namespace std; int main() { int z, n; cin >> z; for ( int i = 0; i < z; i++ ) { cin >> n; if ( n % 2 == 0 ) { // Проверка на чётность cout << "A" << endl; } else { cout << "B" << endl; } } return 0; } |
Решение
Решение задачи сводиться к проверке начального количества атомов ([latex]n[/latex]), которое они хотят поделить между собой, на чётность и нечётность. По условию мы знаем, что профессор первый делит атомы на две непустые группы, следовательно, он может воспользоваться преимуществом первого хода и задавать тон игре. Для победы профессора нужно сделать так, чтоб доктор разделил последний атом, что приведёт к его проигрышу. Значит, для победы нужно чётное количество атомов, так как только при этом случае он может придерживаться стратегии и делить на две непустые группы с нечётным количеством атомов (это может быть [latex]1[/latex] и [latex]n — 1[/latex]) до тех пор, пока его противнику не достанется [latex]1[/latex], что приведёт к взрыву (при нечётном количестве атомов, невозможно с первого хода поделить на две нечётные непустые группы).
Для проверки на чётность и нечётность, необходимо проверить равен ли нулю остаток от деления начального количества атомов ([latex]n[/latex]) на [latex]2[/latex], используя условный оператор.
Ссылки