Решение задачи Старая добрая раскраска чисел с Codeforces
Без пояснения   Просмотров: 81
Рассмотрим множество всех неотрицательных целых чисел : 0,1,2,…. Даны два целых числа a и b (1≤a,b≤104). Мы раскрашиваем все числа в порядке возрастания: сначала раскрашиваем 0, затем раскрашиваем 1, затем раскрашиваем 2 и так далее.
Каждое число будет раскрашено в белый или черный цвет. Очередное число i раскрашивается по следующим правилам:
если i=0, то раскрашено в белый цвет;
если i≥a и i−a раскрашен в белый цвет, то и i раскрашен в белый цвет;
если i≥b и i−b раскрашен в белый цвет, то и i раскрашен в белый цвет;
если i не раскрашен в белый цвет, то раскрашен в черный.
Таким образом, каждое неотрицательное целое число будет раскрашено в один из двух цветов.
Например, если a=3, b=5, то цвета чисел (в порядке от 0 и далее) будут равны: белый (0), черный (1), черный (2), белый (3), черный (4), белый (5), белый (6), черный (7), белый (8), белый (9), ...
Обратите внимание, что:
Возможно, что существует бесконечно много неотрицательных целых чисел, раскрашенных в черный. Например, если a=10 и b=10, тогда только 0,10,20,30 и любые другие неотрицательные целые числа, десятичная запись которых заканчивается на 0 — белые. Все остальные — черные.
Также возможно, что существует только конечно много неотрицательных целых чисел, раскрашенных в черный. Например, если a=1 и b=10, тогда ни одно число не покрашено в черный цвет.
Ваша задача — определить, конечно ли количество чисел, которые раскрашены в черный цвет, или бесконечно.
Если существует бесконечно много чисел, раскрашенных в черный, то выведите единственную строку, содержащую «Infinite» (без кавычек). Иначе выведите «Finite» (без кавычек).
Каждое число будет раскрашено в белый или черный цвет. Очередное число i раскрашивается по следующим правилам:
если i=0, то раскрашено в белый цвет;
если i≥a и i−a раскрашен в белый цвет, то и i раскрашен в белый цвет;
если i≥b и i−b раскрашен в белый цвет, то и i раскрашен в белый цвет;
если i не раскрашен в белый цвет, то раскрашен в черный.
Таким образом, каждое неотрицательное целое число будет раскрашено в один из двух цветов.
Например, если a=3, b=5, то цвета чисел (в порядке от 0 и далее) будут равны: белый (0), черный (1), черный (2), белый (3), черный (4), белый (5), белый (6), черный (7), белый (8), белый (9), ...
Обратите внимание, что:
Возможно, что существует бесконечно много неотрицательных целых чисел, раскрашенных в черный. Например, если a=10 и b=10, тогда только 0,10,20,30 и любые другие неотрицательные целые числа, десятичная запись которых заканчивается на 0 — белые. Все остальные — черные.
Также возможно, что существует только конечно много неотрицательных целых чисел, раскрашенных в черный. Например, если a=1 и b=10, тогда ни одно число не покрашено в черный цвет.
Ваша задача — определить, конечно ли количество чисел, которые раскрашены в черный цвет, или бесконечно.
Если существует бесконечно много чисел, раскрашенных в черный, то выведите единственную строку, содержащую «Infinite» (без кавычек). Иначе выведите «Finite» (без кавычек).