PohonJagung.cpp

#include <stdio.h>

// Cara 1 (Slow) (TLE)
void hitung1(int hari, int berat, int maks_hari, unsigned int *total){
	//printf("%d %d %d\n", hari, maks_hari, *total);
	if(hari>maks_hari)
		return;

	if(berat==1)
		*total = *total + 1;

	if(berat>=0 && berat<=2)
		hitung1(hari+1, berat+1, maks_hari, total);
	else if(berat>=3 && berat<=4){
		hitung1(hari+1, berat+1, maks_hari, total);
		hitung1(hari+1, 1, maks_hari, total);
	}
	else{
		hitung1(hari+1, berat+1, maks_hari, total);
		hitung1(hari+1, 1, maks_hari, total);
		hitung1(hari+1, 1, maks_hari, total);
		hitung1(hari+1, 1, maks_hari, total);
	}
}

// Cara 2 (Fast)
unsigned int hitung2(int hari, int berat, int maks_hari){
	//printf("%d %d\n", hari, berat);
	if(hari>=maks_hari)
		return 1;
	if(berat>=5)
		return 3*hitung2(hari+1, 1, maks_hari)+hitung2(hari+1, berat+1, maks_hari);
	else if(berat>=3)
		return hitung2(hari+1, 1, maks_hari)+hitung2(hari+1, berat+1, maks_hari);
	else
		return hitung2(hari+1, berat+1, maks_hari);
}

int main(){
	int n;
	unsigned int total=1;
	scanf("%d", &n);
	hitung1(1, 2, n, &total);
	printf("Hitung 1 : %u\n", total);
	printf("Hitung 2 : %u\n", hitung2(0, 1, n));
	return 0;
}

/*
Deskripsi

Professor Pepe Domogan (lebih sering dikenal dengan Prof. PeDo) berhasil membuat penemuan yang akan mengguncang dunia perjagungan. Dengan mempertimbangkan bahwa komoditas utama tempat ia hidup adalah tanaman jagung, ia bertekad untuk meningkatkan komoditas tersebut dengan segala cara yang memungkinkan. Akhirnya ia memutuskan untuk membuat suatu ramuan.

Ramuan hasil penemuannya ini membuat semua tumbuhan jagung tumbuh dan berkembang dengan sangat pesat. Tumbuhan jagung tersebut juga memperbanyak diri dengan cara yang tidak biasa: bertunas. Dan proses pertunasan jagung berlangsung sangat singkat. Tidak hanya tumbuhan yang diberi ramuan saja, bahkan tunas-tunas baru dari tumbuhan yang diberi ramuan pun tumbuh dengan cepat.

Profesor PeDo selalu mencatat proses penelitiannya dalam sebuah jurnal. Berikut cuplikan beberapa jurnalnya

21 Agustus 20XX
Eksperimen dimulai. Tunas tumbuhan dalam kondisi prima. Tunas tersebut diberi ramuan. Tidak ada perbedaan yang mencolok hingga akhir sesi eksperimen. -Prof Pedo

22 Agustus 20XX
Tumbuhan jagung yang diberi ramuan tampak lebih tinggi 20 cm dibandingkan yang biasa. Pertumbuhan akan terus dipantau. Untuk berjaga-jaga, tumbuhan diinkubasi dalam lingkungan optimal. -Prof Pedo

23 Agustus 20XX
Tumbuhan jagung yang diberi ramuan tumbuh jauh lebih tinggi, kira-kira 1,6 meter. Dilihat dari bentuknya, tumbuhan tersebut mencapai fase dewasa. Pertumbuhan akan terus dipantau. -Prof Pedo

24 Agustus 20XX
Tinggi tumbuhan yang diberi ramuan tidak terlihat berubah. Ditemukan satu tunas di dekat tumbuhan yang diberi ramuan. Hipotesa bahwa tumbuhan jagung telah mencapai fase dewasa terbukti. -Prof Pedo

25 Agustus 20XX
Ditemukan satu tunas lagi di dekat tumbuhan yang mendapat ramuan. Tunas pertama tumbuh setinggi 20 cm, seperti tumbuhan yang diberi ramuan pertama kali pada hari kedua. Kedua tunas diinkubasi. -Prof Pedo

26 Agustus 20XX
Ditemukan tiga tunas sekaligus di dekat tumbuhan yang mendapat ramuan. Tumbuhan jagung yang sebelumnya memiliki tinggi 20 cm kini tumbuh menjadi 1,5 meter. Tunas pada tanggal 25 Agustus tumbuh menjadi 19 cm. Tunas baru akan diinkubasi. -Prof Pedo

9 Oktober 20XX
Tumbuhan jagung yang diberi ramuan beserta anakannya memiliki pola pertumbuhan yang sama:

1. Fase awal (fase tunas)
Dari tunas membutuhkan satu hari untuk bisa mencapai tinggi rata-rata 24 cm. Saat mencapai tinggi tersebut tumbuhan mencapai fase pertengahan.

2. Fase pertengahan
Dari fase pertengahan membutuhkan waktu sehari untuk mencapai tinggi rata-rata 1,64 meter. Saat tumbuhan mencapai tinggi ini, tumbuhan telah mampu bertunas. Tumbuhan telah mencapai fase dewasa.

3. Fase dewasa dan fase kematangan
Satu tumbuhan dewasa mampu menghasilkan satu tunas setiap harinya. Namun, dua hari semenjak tumbuhan mencapai fase dewasa, kemampuan reproduksi tumbuhan meningkat. Tumbuhan mencapai fase kematangan, dimana tiga tunas dapat dihasilkan sekaligus oleh satu tumbuhan. -Prof Pedo


Jurnal tersebut kehilangan beberapa tanggal karena rusak disebabkan oleh kelalaian pegawai eksperimen yang berjaga, sehingga Profesor Pedo tidak dapat mengetahui berapa jumlah tumbuhan jagung beberapa hari sebelumnya. Padahal Profesor Pedo selalu mencatat segala kejadian di jurnal tersebut. Untungnya halaman tanggal 9 Oktober tidak hilang. Berbekal informasi pada halaman tersebut, ia mencoba untuk mengetahui kembali jumlah jagung pada hari kesekian. Sayangnya jumlah jagung terlalu banyak sehingga Profesor Pedo tidak sanggup menghitung. Bantulah Profesor Pedo menghitung tumbuhan jagung beberapa hari sebelumnya!
Format Inputan

Input berupa sebuah integer N, dimana N adalah jumlah hari yang berlalu semenjak hari pertama eksperimen (Tanggal 21 Agustus). Jika inputan adalah 0, maka tidak ada hari yang berlalu. Artinya akan dicari jumlah jagung pada tanggal 21 Agustus.
Batasan

Dari hari pertama eksperimen hingga 9 Oktober 20XX
0 <= N <= 50
Format Keluaran

Keluaran berupa sebuah integer I, dimana I adalah jumlah tumbuhan jagung setelah N hari eksperimen
Contoh Input

1
Contoh Output

1
Contoh Input

3
Contoh Output

2
Contoh Input

5
Contoh Output

6
Penjelasan

Pada contoh kedua, setelah 3 hari berlalu, tumbuhan menghasilkan tunas karena tumbuhan mencapai fase dewasa setelah 2 hari berlalu.

Pada contoh ketiga, setelah 5 hari berlalu, tumbuhan menghasilkan tunas sebanyak 5 tunas. Pada hari ketiga menghasilkan satu tunas. Hari keempat menghasilkan satu tunas. Pada hari ini tumbuhan mencapai fase kematangan, sehingga hari kelima menghasilkan 3 tunas sekaligus. Total menjadi 6 tumbuhan.
*/