Olimpiade Sains Kota (OSK) 2018 - Komputer, Nomor 28

Question

Pak Dengklek membuat suatu permainan bagi para bebeknya, membawa mereka ke dalam satu goa yang petanya sebagai berikut. Lingkaran adalah ruangan, dan arah panah menunjukkan lorong untuk mencapai suatu ruangan dari sebuah ruangan. Angka menunjukkan jumlah permata dalam setiap ruangan.

Hadiah akan diberikan kepada bebek, yang berhasil mengumpulkan sejumlah permata yang paling banyak, Berapa maksimum permata yang dapat dikumpulkan mulai dari pintu masuk (kiri bawah) sampai keluar (Kanan atas)?

a. 26

b. 27

c. 28

d. 29

e. 30

kenneth mamahit · Accepted Answer

10+2=12 12+7=19 19+3=22 23+5=28 7+3=10 10+2=12 15+3=18 21+2=23 3+4=7 7+1=8 9+6=15 15+6=21 3 3+3=6 6+3=9 9+4=13

M.Fikri Sandi Pratama · Answer

3+3+3+6+6+2+5 = 28

Kopi Putih · Answer

Dapat Menggunakan Teknik Dynamic Programming. Dynamic Programming yang dipakai adalah Bottom Up, mengisi dari Base Case Pertama, Hanya Ujung kanan atas ( Posisi 0,3 ) nya saja yang dapat dihitung, yaitu 5. Jumlah Permata yang dapat diambil maksimal dari Tempat (0,3) adalah 5. dp 0 1 2 3 0 5 1 2 3 Kemudian isi kotak posisi (0,2) dan (0,3) dp 0 1 2 3 0 8 5 1 7 2 3 Lanjutkan pengisian untuk semua elemen kolom ke 3 dan baris ke 0 dp 0 1 2 3 0 17 15 8 5 1 7 2 13 3 17 Base Case sudah terisi semua. Sek

MAN 2 Kudus · Answer

https://www.youtube.com/watch?v=rcoaY19NL0w

kariaman lase · Answer

karna setiap bebek harus berjalan lurus melewati pintu masuk (kiri bawah) lalu keatas untuk keluar 27 jawabannya

10+2=12	12+7=19	19+3=22	23+5=28
7+3=10	10+2=12	15+3=18	21+2=23
3+4=7	7+1=8	9+6=15	15+6=21
3	3+3=6	6+3=9	9+4=13

dp	0	1	2	3
0	17	15	8	5
1			8+3	7
2				13
3				17

dp	0	1	2	3
0	17	15	8	5
1		15+2	11	7
2			13+6	13
3				17

dp	0	1	2	3
0	17	15	8	5
1	17+3	17	11	7
2			19	13
3			19+3	17

dp	0	1	2	3
0	17	15	8	5
1	20	17	11	7
2		19+1	19	13
3			22	17

Olimpiade Sains Kota (OSK) 2018 - Komputer, Nomor 28

5 jawaban