Olimpiade Sains Provinsi (OSP) 2018 - Komputer, Nomor 24–25

24. 9 cara,, bisa dihitung atau ditentukan dulu polanya,, polanya spt pada no 25 berikut :

 

25.

ke kolom 2 ad 1 cara,, dari 2 ke 3 ad 3 cara,, dr 3 ke 4 ada 1 cara,, dr 4 ke 5 ad 3 cara, dr 5 ke 6 ada 1 cara,, begitu strusnyaa

sehingga didapat pola

2 = 1

3 = 3

4 = 3

5 = 9

6 = 9

7 = 27

8 = 27

.

dst.

nah utk mencapai kolom 1357,, berarti dibagi 2 dulu utk menentukan 3 pangkat berapa. karena dp[1] dimulai dr angka 2, jadi 1357 dikurang dulu dg 1. karena selalu ad 2 kolom yg dikali 1, kemudian dikali 3,1,3,1,3 dst,, jadi pembulatan 1357 dibagi 2 harus kebawah. didapat {3^((1357-1) div 2)} mod 7.

jadinya (3^((1357-1) div 2))) mod 7

= 3^678 mod 7

= 1

Permasalahan ini dapat diselesaikan dengan pendekatan dynamic programming. State yang saya gunakan adalah kolom dan posisi Pak Dengklek dan Pak Ganesh saat berada pada kolom tersebut. Apabila posisi Pak Dengklek/Ganesh tidak memungkinkan pada kolom tersebut, yakni ketika di luar indeks 0-3 (hanya terdapat 4 baris) ataupun ketika posisi Pak Ganesh berada di atas Pak Dengklek (keduanya tidak boleh bersilangan), maka banyak kemungkinan untuk state tersebut adalah 0.

Implementasi: https://ideone.com/Q75CQB

#include <cstring>
#include <iostream>
using namespace std;

#define ll long long

ll memo[2000][4][4];

ll dp(int col, int drow, int grow) {
	// row out of bound
	if (drow < 0 || 4 <= drow || grow < 0 || 4 <= grow)
		return 0;
	// d crossed with g
	if (grow <= drow)
		return 0;
	// first column
	if (col == 1) {
		if (drow == 0 && grow == 3)
			return 1;
		else
			return 0;
	}
	if (memo[col][drow][grow] != -1)
		return memo[col][drow][grow];
		
	memo[col][drow][grow] = 0;
	memo[col][drow][grow] += dp(col-1, drow-1, grow-1);
	memo[col][drow][grow] += dp(col-1, drow-1, grow+1);
	memo[col][drow][grow] += dp(col-1, drow+1, grow-1);
	memo[col][drow][grow] += dp(col-1, drow+1, grow+1);
	memo[col][drow][grow] = memo[col][drow][grow] % 7;
	
	return memo[col][drow][grow];
}

int main() {
	int N;
	cin >> N;
	memset(memo, -1, sizeof(memo));
	ll ans = 0;
	for (int i = 0; i < 4; i++)
		for (int j = i+1; j < 4; j++)
			ans += dp(N, i, j);
	cout << ans % 7 << endl;
}

kalo saya ketemunya banyak pola pada kolom ke n = (bil.fibonacci ke-n)^2.  untuk fibo(1)=1 dan fibo(2)=1.

saya nyari cara manual.. ngecek tiap kasus per kolom..

untuk no 24 saya jawab 25.

CMIIW