Efek Domino

Soal#

Informasi#

• Sumber: CompFest 8 - Penyisihan CPC Senior
• Tanggal: 2016-08-20

Arsip#

• TLX

Ringkasan#

Diberikan domino yang memiliki tinggi dari $1$ sampai dengan $N$. Domino-domino tersebut akan disusun berjajar dari belakang ke depan. Saat suatu domino dijatuhkan, domino tersebut dapat menjatuhkan domino di depannya dengan tinggi maksimal dua kalinya. Jika domino paling belakang dijatuhkan dan menyebabkan semua domino jatuh, maka terjadi Efek Domino. Ada berapa banyak penyusunan domino yang dapat menghasilkan Efek Domino? Contoh susunan yang menghasilkan Efek Domino (kiri ke kanan = belakang ke depan):

• $1$-$2$-$3$-$4$-$5$
• $5$-$1$-$2$-$3$-$4$
• $2$-$4$-$3$-$5$-$1$

Solusi#

Petunjuk#

Pembahasan#

Untuk suatu susunan domino dengan tinggi $1$ sampai $k - 1$, kita akan menyisipkan domino dengan tinggi $k$ ke susunan tersebut. Misal susunan domino sebelum disisipkan dilambangkan dengan $S$ dan sesudahnya dilambangkan dengan $S'$. Perhatikan bahwa apabila kita menyisipkan domino dengan tinggi $k$ di belakang, tengah, maupun di depan $S$, domino tersebut pasti bisa menjatuhkan domino di depannya. Tetapi, domino di belakangnya belum tentu dapat menjatuhkan domino tersebut. Tinggi domino minimum dan maksimum pada $S$ yang dapat menjatuhkan domino dengan tinggi $k$ berturut-turut adalah $\left\lceil\frac{k}{2}\right\rceil$ dan $k - 1$. Jadi untuk setiap susunan domino dengan tinggi $1$ sampai $k - 1$, banyaknya domino yang dapat menjatuhkan domino dengan tinggi $k$ adalah $(k - 1) - \left\lceil\frac{k}{2}\right\rceil + 1 = k - \left\lceil\frac{k}{2}\right\rceil = \left\lfloor\frac{k}{2}\right\rfloor$.

Misal $f(n)$ menyatakan banyaknya susunan domino dengan tinggi $1$ sampai $n$ yang dapat menghasilkan Efek Domino. Perhatikan bahwa apabila domino dengan tinggi $k$ ditempatkan di belakang $S$, domino tersebut pasti dapat menjatuhkan semua domino pada setiap susunan $S$ yang mungkin. Oleh karena itu, banyaknya susunan $S'$ di mana domino dengan tinggi $k$ berada di belakang adalah $f(k - 1)$. Sedangkan apabila domino dengan tinggi $k$ disisipkan di tengah atau di depan $S$, maka banyaknya susunan $S'$ yang mungkin adalah $\left\lfloor\frac{k}{2}\right\rfloor \cdot f(k - 1)$. Dengan menggabungkan kedua kasus di atas, didapatkan rekurensi $$f(k) = f(k - 1) + \left\lfloor\frac{k}{2}\right\rfloor \cdot f(k - 1) = \left(\left\lfloor\frac{k}{2}\right\rfloor + 1 \right) \cdot f(k - 1)$$ dengan kasus dasar $f(1) = 1$ atau $f(0) = 1$.

Kita bisa melakukan prekomputasi atau menggunakan teknik seperti dynamic programming untuk mengimplementasi solusi. Namun, perhatikan bahwa soal tidak menyatakan jawaban harus dimodulo. Karena jawaban bisa sangat besar nilainya, kita bisa menggunakan big integer. Untuk memudahkan implementasi dalam bahasa C++, kita bisa menggunakan kode big integer dari orang lain. Kode bigint.cpp dan dependensinya, yaitu fft.h, juga dapat diakses pada situs ini. Pada kebanyakan online judge kita hanya bisa melakukan submisi sebanyak satu berkas. Pada artikel ini, kode tidak mengekspansi pustaka big integer agar tidak menggunakan banyak baris kode. Anda bisa melihat submisi saya di TLX yang mengekspansi pustaka big integer.

Kode#

#include <iostream>
#include <bigint.h>
using namespace std;

const int MAXN = 1000;

int T;
bigint F[MAXN + 1];

int main(){
    cin.tie(0)->sync_with_stdio(0);

    F[0] = 1;
    for(int i = 1; i <= MAXN; i++){
        F[i] = F[i - 1] * (i/2 + 1);
    }

    cin >> T;
    for(int i = 0; i < T; i++){
        int x;
        cin >> x;
        cout << F[x] << '\n';
    }
    return 0;
}