Задача
Мурад и Ибрагим играют в следующую игру. Изначально дается число $1$. На своем ходу каждый игрок должен умножить текущее число на одно из целых чисел от $2$ до $9$ включительно. Цель состоит в том, чтобы получить число не меньше заданного целого числа $n$. Игрок, получивший такой номер первым, объявляется победителем. Мурад всегда начинает первым. Выясните, кто победит, если Мурад и Ибрагим будут играть оптимально.
Входные данные
Первая строка содержит одно число $t$ $(1 \leqslant t \leqslant 2500)$ — количество тестов. Каждая из следующих $t$ строк содержит одно целое число $n$ $(2 \leqslant n \leqslant 10^9)$.
Выходные данные
Для каждого теста выведите в отдельной строке $1$, если Мурад выиграет игру, и $2$ иначе.
Тесты
№ |
Входные данные |
Выходные данные |
| 1 | 4 9 10 1149729 999999999 |
1 2 2 1 |
| 2 | 3 6 163 1234567 |
1 2 2 |
| 3 | 3 42 100 1000 |
1 1 1 |
Код программы
Решение с циклом для каждого отдельного теста:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> using namespace std; int main() { int k; double n; cin >> k; for (int i = 0; i < k; i++) { cin >> n; bool p = true; while (n > 1) { n /= (p ? 9 : 2); p = !p; } cout << p + 1 << "\n"; } return 0; } |
Решение без цикла для каждого отдельного теста:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> #include <cmath> using namespace std; int main() { int t, n; cin >> t; int x = 0; for (int i = 0; i < t; i++) { cin >> n; double l = n / pow(18, ceil(log(n) / log(18))); cout << ((2 * l <= 1) ? 1 : 2) << "\n"; } return 0; } |
Решение
Для начала заметим, что победит тот игрок, чей ход выпадет на число из промежутка $[\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
Для отправки комментария необходимо войти на сайт.