17206. Gra w mnożenie [AL_12_03]

Zadanie:
http://spoj.com/ALGOLIGA/problems/AL_12_03
http://pl.spoj.com/problems/AL_12_03

Skrócony opis problemu:

Zaczynamy od $p=1$. Gracze A i B mnożą na przemian $p$ przez $x \in \left\lbrace 2,3,4,5,6,7,8,9\right\rbrace$ aż $p \ge n$. Gracz, który ostatni przemnoży $p$ wygrywa. Zaczyna gracz A. Naszym zadaniem jest określić który gracz wygra, zakładając, że obaj grają optymalnie.

Rozwiązanie:

Dla $p \le 9$ gracz A oczywiście wygra. Dla $p \in \left<10;18\right>$ wygra gracz B. Dla $p \in \left<19;36\right>$ znów wygra gracz A, gdyż najpierw wybierze 2, gracz B również wybierze 2 (aby zminimalizować iloczyn), a gracz A wybierze 9. $2 \cdot 2 \cdot 9 = 36$. Czy oznacza to, że dla $p=37$ gracz A przegra? Nie. Wystarczy, że zwiększy swoją pierwszą liczbę do 3. Gracz B nawet jeśli wybierze 9 to nie osiągnie 37. A więc gracz B nadal będzie chciał minimalizować iloczyn wybierając 2. Dostaniemy więc $3 \cdot 2 \cdot 9 = 54$. Możemy tak ciągnąć aż do maksymalnej wartości jaką gracz A może na początku wybrać - $9 \cdot 2 \cdot 9 = 162$. A więc najnowszy przedział gracza A to $\left<19;162\right>$. Jak możemy się domyślić, maksymalna wartość jaką może uzyskać gracz B odpowiednio wybierając kolejne czynniki to $2 \cdot 9 \cdot 2 \cdot 9 = 324$. Gracz B wygrywa zatem w przedziale $\left<163;324\right>$. Widzimy już chyba zależność. Jeśli nie, oto kolejne przedziały zwycięstw (nieparzyste należą do gracza A, parzyste do gracza B):

$$\left<2;9\right>\\
\left<10;18\right>\\
\left<19;162\right>\\
\left<163;324\right>$$

A zatem, zaczynamy sobie od $p=1$ i mnożymy $p$ przez 9 jeśli kolejka należy do gracza A lub przez 2 jeśli należy ona do gracza B. Gdy osiągniemy $p \ge n$ możemy łatwo określić zwycięzcę, gdyż musimy pamiętać przez co ostatnio pomnożyliśmy $p$.

Złożoność: $O(\log n)$, gdyż mnożymy na przemian $p$ przez 2 i 9 aż osiągniemy $n$. Mnożeń tych będzie maksymalnie $2 \cdot \lceil \log_{18} n \rceil$ (gdy wygra gracz B, bo będzie po równo mnożeń przez 9 i przez 2; gdy wygra gracz A będzie 1 mnożenie mniej).

Algorytm:

int main()
{
    double n;
    while(get(n))
    {
        while(n > 9)
            n /= 18.0;
        print(n <= 1.0 ? "B" : "A");
    }
}

Optymalizacja:

W powyższym algorytmie wykorzystuję dzielenie zamiast mnożenia (idę od końca). Z mnożeniem będzie szybciej i będzie można operować na liczbach całkowitych, co jest szybsze.