## Sample Batch. Menara Pangkat
#### Writer: Daniel Stevanus
### Batch with Subtasks
Pada soal batch yang terdiri dari beberapa subsoal, Anda dapat mengerjakan dan menyelesaikan satu per satu subsoal dengan solusi yang berbeda-beda untuk tiap subsoal.

Misalnya, pada kasus berikut ini:
- Anda memiliki solusi untuk Subsoal 1 (11 poin), namun tidak untuk Subsoal 2
- Anda memiliki solusi untuk Subsoal 2 (7 poin), namun tidak untuk Subsoal 1

Anda dapat meng-*submit* kedua solusi tersebut secara terpisah sehingga mendapat 11 poin pada submisi pertama, dan 7 poin pada submisi kedua. Poin-poin yang anda dapatkan secara terpisah tersebut akan diakumulasikan dan hasil penjumlahan poin-poin tersebut yang akan menjadi nilai Anda pada soal tersebut.

Untuk kasus diatas, maka poin yang akan didapatkan adalah $11+7 = 18$ poin

### Solution

Sebelum menuju solusi untuk tiap-tiap subsoal, perlu dipahami dulu bahwa Pola Bilangan Hasil Modulo oleh sebuah bilangan $M$ akan berulang setiap $\phi(M)$ kali. Dengan $\phi(M)$ adalah banyak bilangan lebih kecil dari $M$ yang saling prima dengan $M$.

Perlu diketahui juga hal-hal berikut:
- Jika $A \space mod \space M = 0$, maka hasilnya akan selalu 0.
- Jika $A \space mod \space M = 1$, maka hasilnya akan selalu 1.
- Jika $B = 1$, maka hasilnya akan selalu $A \space mod \space M$.
- $A^{A^{A^{...}}}mod \space M = (A \space mod \space M)^{A^{A^{...}}} \space mod \space M$

#### Subsoal 1

Pada subsoal 1, telah diberikan detail masukan yaitu `3 3 100` ($A = 3, B = 3, M =100$). Anda dapat menyelesaikan soal ini secara naif dengan atau tanpa bantuan program komputer.
Anda dapat menghitung $3^{3^3}$ mod $100$ dengan kertas pensil sebagai b berikut:
$3^{27}\space mod\space 100 =3*3*3*3*3*{...}*3 \space mod \space 100 = \space243\space mod\space100*3*3*3*{...}*3\space mod \space100 = {...}$
Anda juga dapat menggunakan bantuan program komputer menggunakan perulangan ataupun fungsi rekursi untuk menyelesaikan permasalahan ini.

#### Subsoal 2
Pada subsoal 2, telah diberikan detail masukan yaitu `20202020 202020 2020` $(A = 20202020,$ $B = 202020,$ $M = 2020)$.
Perhatikan kalau nilai $A$ habis dibagi oleh $M$ $(A \space mod \space M = 0)$, maka berapa pun pangkatnya (nilai $B$-nya), hasilnya akan selalu $0$.

#### Subsoal 3 ($M = 2$)
Hal ini sama saja dengan menentukan apakah hasilnya **genap** atau **ganjil**. Menentukan genap atau ganjil suatu bilangan berpangkat dapat dilakukan hanya dengan mengetahui bilangan yang dipangkatkan (dalam hal ini, $A$).
Untuk itu kita hanya perlu mengecek apakah A bernilai genap $(A \space mod \space 2 = 0)$ atau A bernilai ganjil $(A \space mod \space 2 = 1)$

#### Subsoal 4 ($M = 3$)
Hanya ada tiga kemungkinan hasil modulo A oleh 3, yaitu **0, 1, dan 2**.

- Untuk $A \space mod \space 3 = 2$, maka soal kini dapat disederhanakan menjadi $2^{A^{A^{...}}} \space mod \space 3$.
Dalam kasus ini kita dapat menggunakan Teorema Euler dimana
$2^{A^{A^{...}}} \space mod \space 3 = 2^{A^{A^{...}} \space mod \space \phi(3)} \space mod \space 3 =2^{A^{A^{...}} \space mod \space 2} \space mod \space 3$.
Perhatikan kalau $A^{A^{...}} \space mod \space 2$ sama halnya dengan **Subsoal 3**, dimana hasilnya hanya diantara 0 atau 1. Dengan demikian ketika $A \space mod \space 3 = 2$, maka hasilnya ada diantara $2^0$ atau $2^1$ tergantung pada $A^{A^{...}} \space mod \space 2$.

#### Subsoal 5 ($M = 4$)
Ada empat kemungkinan hasil modulo A oleh 4, yaitu **0, 1, 2, dan 3**.

- Untuk $A \space mod \space 4 = 2$, maka kita hanya perlu mengecek apakah pangkatnya > 1. Jika pangkatnya >=1 maka hasilnya adalah 0 karena $2^{p} (untuk \space p>1)$ akan selalu habis di modulo 4. Lagipula, tidak mungkin ada nilai $p$ dimana $p \leq 1$ kecuali jika $A$ bernilai $1$ dan hasilnya sudah pasti $1$.
- Untuk $A \space mod \space 4 = 3$, kita tahu bahwa $3^{A^{A^{...}}} \space mod \space 4$ akan berulang setiap $\phi(2)=2$ kali. Dalam kasus ini kita dapat menggunakan Teorema Euler dimana
$3^{A^{A^{...}}} \space mod \space 4 = 3^{A^{A^{...}} \space mod \space \phi(4)} \space mod \space 4 =3^{A^{A^{...}} \space mod \space 2} \space mod \space 4$.
Perhatikan kalau $A^{A^{...}} \space mod \space 2$ sama halnya dengan **Subsoal 3**, dimana hasilnya hanya diantara 0 atau 1. Dengan demikian ketika $A \space mod \space 3 = 2$, maka hasilnya ada diantara $2^0$ atau $2^1$ tergantung pada $A^{A^{...}} \space mod \space 2$.
#### Subsoal 6 ($M = 5$)
Ada lima kemungkinan hasil modulo A oleh 5, yaitu **0, 1, 2, 3, dan 4**.
- Untuk $A \space mod \space 5$ yang bernilai $2, 3,$ atau $4$, kita dapat menggunakan Teorema Euler untuk membantu menyederhanakan pangkat bertingkatnya.
$A^{A^{A^{...}}} \space mod \space 5 = A^{A^{A^{...}} \space mod \space \phi(5)} \space mod \space 5=A^{A^{A^{...}} \space mod \space 4} \space mod \space 5$.
Perhatikan kalau kita mendapatkan bentuk pangkat yang familiar dengan **Subsoal 5**, yaitu $A^{A^{...}} \space mod \space 4$.
Misalkan X adalah hasil dari $A^{A^{...}} \space mod \space 4$ yang didapat dengan cara yang sama pada Subsoal 5, maka kita dapatkan $A^{A^{A^{...}}} \space mod \space 5 = (A \space mod \space 5)^X \space mod \space 5$, dimana X salah satu dari ${0,1,2,3}$.

#### Subsoal 7 ($M = 6$)
Ada enam kemungkinan hasil modulo A oleh 5, yaitu **0, 1, 2, 3, 4 dan 5**.

- Untuk $A \space mod \space 6$ yang bernilai $2, 3, 4$ atau $5$, kita dapat menggunakan Teorema Euler untuk membantu menyederhanakan pangkat bertingkatnya.
$A^{A^{A^{...}}} \space mod \space 6 = A^{A^{A^{...}} \space mod \space \phi(6)} \space mod \space 6=A^{A^{A^{...}} \space mod \space 2} \space mod \space 6$.
Perhatikan kalau kita mendapatkan bentuk pangkat yang familiar dengan **Subsoal 3**, yaitu $A^{A^{...}} \space mod \space 2$.
Misalkan X adalah hasil dari $A^{A^{...}} \space mod \space 2$ yang didapat dengan cara yang sama pada Subsoal 3, maka kita dapatkan $A^{A^{A^{...}}} \space mod \space 6 = (A \space mod \space 6)^X \space mod \space 6$, dimana X salah satu dari ${0,1}$.
- **Perlu diperhatikan pula** kalau $M = 6$ tidak selalu saling prima dengan $A$ (tidak saling prima = tidak mungkin menghasilkan 1 (atau $A^0$ sebagai hasil modulonya), sehingga kita perlu mengubah nilai $X = 0$ menjadi $X = 2$.

#### Subsoal 8 ($B = 2$)
Ketika $B=2$, maka soal dapat disederhanakan menjadi $A^A \space mod \space M$. Ini adalah soal perpangkatan pada umumnya yang dapat diselesaikan dengan bantuan fungsi pangkat $p^q = p^{q/2} * p^{q/2} \space mod \space M$ untuk $q$ genap, dan $p^q = p^{q/2} * p^{q/2} * p \space mod \space M$ untuk $q$ ganjil (untuk menghindari terjadinya overflow/angka melebihi batas [long]int)

## Sample Interactive. Mengambil Batu

#### Writer: Nathan Keith

### Interactive Problems for Dummies

Dalam problem tipe ini, data masukan yang diberikan ke program Anda mungkin tidak ditentukan sebelumnya tetapi dibuat khusus untuk solusi Anda. Juri menulis program khusus — `interactor`, sehingga keluaran dari program ini ditransfer ke masukan solusi Anda, dan keluaran dari program Anda dikirim ke masukan interactor. Dengan kata lain, solusi Anda dan interactor saling bertukar data dan mungkin memutuskan apa yang akan dicetak berdasarkan "sejarah komunikasi".

Ketika Anda menulis solusi untuk problem interaktif, penting untuk diingat bahwa jika Anda mengeluarkan beberapa data, kemungkinan data tersebut pertama-tama ditempatkan di buffer internal dan mungkin tidak langsung ditransfer ke interactor. Untuk menghindari situasi seperti itu, Anda harus menggunakan operasi `flush` khusus setiap kali Anda mengeluarkan beberapa data. Dalam C++ Anda dapat menggunakan `fflush(stdout)` atau `cout << flush` (tergantung apa yang Anda gunakan untuk keluaran data — `scanf/printf` atau `cout`).

Ada beberapa fitur untuk problem interaktif:

- Masukan/keluaran dalam problem interaktif bekerja jauh lebih lambat dibandingkan dengan problem biasa — coba gunakan `scanf/printf` alih-alih `cin/cout` dalam C++.
- Biasanya, pengujian manual solusi untuk problem interaktif jauh lebih sulit, karena peserta perlu mengambil peran interactor selama pengujian.
- Mengeluarkan `endl` dalam `cout` di C++ melakukan operasi flush secara otomatis.

Kredit: Diterjemahkan dan dimodifikasi dari Blog MikeMirzayanov dari Codeforces
https://codeforces.com/blog/entry/45307

### Solution

#### Subtask 1

Dapat dibuktikan bahwa jika $A_{1}$ $mod$ $(N+1) = 0$, maka Anda akan kalah jika Pak Dengklek bermain dengan optimal.

Bukti: Setiap kali $A_{1}$ $mod$ $(N+1) = 0$ (posisi kalah), maka setiap langkah akan menghasilkan $A_{1}$ $mod$ $(N+1) \neq 0$ (posisi menang). Setiap kali $A_{1}$ $mod$ $(N+1) \neq 0$, ada sebuah langkah untuk membuat $A_{1}$ $mod$ $(N+1)$, yaitu dengan mengambil $A_{1}$ $mod$ $(N+1)$ batu dari tumpukan.

Oleh karena itu, pilihan optimal bagi Anda adalah mengambil $A_{1}$ $mod$ $(N+1)$ batu setiap giliran sampai tidak ada batu yang tersisa.

Kompleksitas: $O(N)$

#### Subtask 2

Kita dapat mendefinisikan hubungan rekursif sebagai berikut:

Didefinisikan $DP(A,B)$ adalah **TRUE** jika pemain pertama menang dengan konfigurasi saat giliran pemain pertama adalah $A,B$ dan sebaliknya.

Dengan hubungan rekursif ini, setiap giliran, kita dapat menemukan giliran berikutnya sehingga kita akan menang apa pun yang dilakukan Pak Dengklek.

Kompleksitas: $O(A_{1}A_{2}N)$

#### Subtask 3

Dapat dibuktikan bahwa jika $A_1 \; mod \; (N+1) = A_2 \; mod \; (N+1)$, maka Anda akan kalah jika Pak Dengklek bermain dengan optimal.

Bukti: Jika nilai $mod$ mereka tidak sama, selalu ada langkah untuk membuatnya sama.

Oleh karena itu, pilihan optimal bagi Anda adalah mengambil $|A_1-A_2| \; mod \; (N+1)$ batu dari tumpukan yang lebih besar di setiap giliran sampai tidak ada batu yang tersisa.

Kompleksitas: $O(N)$

**Catatan Kaki**

Secara umum, dapat dibuktikan bahwa jika $A_1 \; mod \; (N+1) \oplus A_2 \; mod \; (N+1) \dots A_k \; mod \; (N+1)=0$, maka Anda akan kalah jika Pak Dengklek bermain dengan optimal di mana $\oplus$ adalah operasi XOR bitwise.