Olimpiade Sains Kota (OSK) 2016 - Komputer, Nomor 21

Soal ini akan diselesaikan dengan Dynamic Programming.

Misalkan f(n) adalah banyaknya amuba pada menit ke-n.

Kita tahu, banyaknya amuba pada menit ke-n adalah banyaknya amuba pada menit sebelumnya (n-1) ditambah banyaknya amuba baru. Dimana amuba baru dilahirkan oleh amuba yang telah berumur minimal 4 menit. Amuba yang berumur minimal 4 menit adalah amuba yang pada menit ke(n-4) ia telah ada, banyaknya ada f(n-4). Dari sana didapatkan relasi rekursi f(n) = f(n-1) + f(n-4)

f(1) = 6
f(2) = 6
f(3) = 6
f(4) = 6
f(5) = f(4) + f(1) = 6 + 6 = 12
f(6) = f(5) + f(2) = 12 + 6 = 18
f(7) = f(6) + f(3) = 18 + 6 = 24
f(8) = f(7) + f(4) = 24 + 6 = 30
f(9) = f(8) + f(5) = 30 + 12 = 42
f(10) = f(9) + f(6) = 42 + 18 = 60
f(11) = f(10) + f(7) = 60 + 24 = 84
f(12) = f(11) + f(8) = 84 + 30 = 114
f(13) = f(12) + f(9) = 114 + 42 = 156
f(14) = f(13) + f(10) = 156 + 60 = 216
f(15) = f(14) + f(11) = 216 + 84 = 300
f(16) = f(15) + f(12) = 300 + 114 = 414
f(17) = f(16) + f(13) = 414 + 156 = 570
f(18) = f(17) + f(14) = 570 + 216 = 786
f(19) = f(18) + f(15) = 786 + 300 = 1086
f(20) = f(19) + f(16) = 1086 + 414 = 1500
f(21) = f(20) + f(17) = 1500 + 570 = 2070
f(22) = f(21) + f(18) = 2070 + 786 = 2856
f(23) = f(22) + f(19) = 2856 + 1086 = 3942
f(24) = f(23) + f(20) = 3942 + 1500 = 5442
f(25) = f(24) + f(21) = 5442 + 2070 = 7512
f(26) = f(25) + f(22) = 7512 + 2856 = 10368
f(27) = f(26) + f(23) = 10368 + 3942 = 14310
f(28) = f(27) + f(24) = 14310 + 5442 = 19752
f(29) = f(28) + f(25) = 19752 + 7512 = 27264
f(30) = f(29) + f(26) = 27264 + 10368 = 37632
f(31) = f(30) + f(27) = 37632 + 14310 = 51942
f(32) = f(31) + f(28) = 51942 + 19752 = 71694
f(33) = f(32) + f(29) = 71694 + 27264 = 98958
f(34) = f(33) + f(30) = 98958 + 37632 = 136590
f(35) = f(34) + f(31) = 136590 + 51942 = 188532
f(36) = f(35) + f(32) = 188532 + 71694 = 260226
f(37) = f(36) + f(33) = 260226 + 98958 = 359184
f(38) = f(37) + f(34) = 359184 + 136590 = 495774
f(39) = f(38) + f(35) = 495774 + 188532 = 684306
f(40) = f(39) + f(36) = 684306 + 260226 = 944532
f(41) = f(40) + f(37) = 944532 + 359184 = 1303716
f(42) = f(41) + f(38) = 1303716 + 495774 = 1799490
f(43) = f(42) + f(39) = 1799490 + 684306 = 2483796
f(44) = f(43) + f(40) = 2483796 + 944532 = 3428328
f(45) = f(44) + f(41) = 3428328 + 1303716 = 4732044
f(46) = f(45) + f(42) = 4732044 + 1799490 = 6531534
f(47) = f(46) + f(43) = 6531534 + 2483796 = 9015330
f(48) = f(47) + f(44) = 9015330 + 3428328 = 12443658
f(49) = f(48) + f(45) = 12443658 + 4732044 = 17175702
f(50) = f(49) + f(46) = 17175702 + 6531534 = 23707236
f(51) = f(50) + f(47) = 23707236 + 9015330 = 32722566
f(52) = f(51) + f(48) = 32722566 + 12443658 = 45166224
f(53) = f(52) + f(49) = 45166224 + 17175702 = 62341926
f(54) = f(53) + f(50) = 62341926 + 23707236 = 86049162
f(55) = f(54) + f(51) = 86049162 + 32722566 = 118771728
f(56) = f(55) + f(52) = 118771728 + 45166224 = 163937952
f(57) = f(56) + f(53) = 163937952 + 62341926 = 226279878
f(58) = f(57) + f(54) = 226279878 + 86049162 = 312329040
f(59) = f(58) + f(55) = 312329040 + 118771728 = 431100768
f(60) = f(59) + f(56) = 431100768 + 163937952 = 595038720

Jawaban : A