Задача

Мурад и Ибрагим играют в следующую игру. Изначально дается число $1$. На своем ходу каждый игрок должен умножить текущее число на одно из целых чисел от $2$ до $9$ включительно. Цель состоит в том, чтобы получить число не меньше заданного целого числа $n$. Игрок, получивший такой номер первым, объявляется победителем. Мурад всегда начинает первым. Выясните, кто победит, если Мурад и Ибрагим будут играть оптимально.

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

Первая строка содержит одно число $t$ $(1 \leqslant t \leqslant 2500)$ — количество тестов. Каждая из следующих $t$ строк содержит одно целое число $n$ $(2 \leqslant n \leqslant 10^9)$.

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

Для каждого теста выведите в отдельной строке $1$, если Мурад выиграет игру, и $2$ иначе.

Тесты

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

Решение с циклом для каждого отдельного теста:

Решение без цикла для каждого отдельного теста:

Решение

Для начала заметим, что победит тот игрок, чей ход выпадет на число из промежутка $[\frac{n}{9},n)$, так как любое число из этого промежутка можно умножить на соответствующее целое число из $[2,9]$ и получить число не меньшее чем $n$. Назовем такой промежуток «зеленой зоной» (в общем виде будет $[\frac{2n}{18^k},\frac{n}{18^{k-1}})$, $k \in \mathbb {N}$). Тогда очевидно, что проиграет тот игрок, чей ход выпадает на число из промежутка $[\frac{n}{18},\frac{n}{9})$, так как при умножении числа из этого промежутка на любое целое число из $[2,9]$, приводит к тому, что получается число из «зеленой зоны». Назовем такой промежуток «красной зоной» (в общем виде будет $[\frac{n}{18^k},\frac{2n}{18^k})$, $k \in \mathbb {N}$). Получаем, что промежуток $(0,n)$ делится на «красные» и «зеленые зоны». Тогда задача сводится к нахождению вида «зоны» в которой находится $1$.

Используя в реализации цикл для каждого отдельного теста, получить результат достаточно несложно. Однако, для заданного $n$ можно получить исход игры используя лишь линейные вычисления.

Рассмотрим цепочку неравенств (учитывая, что $2 \leqslant n$ ):  $$\lfloor \log _{18} n \rfloor \leqslant \log _{18} n \leqslant \lceil  \log _{18} n \rceil$$

$$18^{\lfloor \log _{18} n \rfloor} \leqslant n \leqslant 18^{\lceil  \log _{18} n \rceil}$$

$$\frac{1}{18^{\lceil  \log _{18} n \rceil}} \leqslant \frac{1}{n} \leqslant \frac{1}{18^{\lfloor \log _{18} n \rfloor}}$$

$$\frac{n}{18^{\lceil  \log _{18} n \rceil}} \leqslant 1 \leqslant \frac{n}{18^{\lfloor \log _{18} n \rfloor}}$$

Из общего вида «красной зоны» видно, что левый ее конец это число вида $\frac{n}{18^k}$, значит $\frac{n}{18^{\lceil  \log _{18} n \rceil}}$ является левым концом «красной зоны», обозначим его как $l$. Тогда, $2l$ будет правым концом «красной зоны» исходя из её общего вида. Из полученного неравенства видно, что $1$ лежит между левыми концами соседних «красных зон». Получаем, что если $2l \leqslant 1$, то единица лежит в «зеленой зоне», а иначе — в «красной».

Ссылки

Условие задачи на e-olymp

Решение без цикла для каждого отдельного теста на ideone

Решение с циклом для каждого отдельного теста на ideone