Задача
Два сумасшедших (и злых) ученых, профессор Зум и доктор Ужасный, только что получили [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 18 19 20 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main(String args[]) { int z; int n= 0; Scanner input = new Scanner(System.in); z = input.nextInt(); for(int i=0;i<z;i++){ n = input.nextInt(); if (n % 2 == 0 ) System.out.println("A"); else System.out.println("B"); } } } |
Решение
Решение задачи сводиться к проверке начального количества атомов ([latex]n[/latex]), которое они хотят поделить между собой, на чётность и нечётность. По условию мы знаем, что профессор первый делит атомы на две непустые группы, следовательно, он может воспользоваться преимуществом первого хода и задавать тон игре. Для победы профессора нужно сделать так, чтоб доктор разделил последний атом, что приведёт к его проигрышу. Значит, для победы нужно чётное количество атомов, так как только при этом случае он может придерживаться стратегии и делить на две непустые группы с нечётным количеством атомов (это может быть [latex]1[/latex] и [latex]n — 1[/latex]) до тех пор, пока его противнику не достанется [latex]1[/latex], что приведёт к взрыву (при нечётном количестве атомов, невозможно с первого хода поделить на две нечётные непустые группы).
Для проверки на чётность и нечётность, необходимо проверить равен ли нулю остаток от деления начального количества атомов ([latex]n[/latex]) на [latex]2[/latex], используя условный оператор.
Ссылки