Olimpiade Sains Provinsi (OSP) 2017 - Komputer, Nomor 19
Pak Dengklek ingin memasak telur dadar menggunakan mesin-mesin pemecah, pengocok dan penggoreng yang bekerjanya tidak tergantung satu sama lain. Ada 3 tahapan untuk membuat telur dadar yaitu mulai memecah, kemudian mengocok, dan terakhlr menggoreng. Pak Dengklek memiliki 3 mesin pemecah telur, 2 mesin pengocok telur, dan 4 mesin penggoreng telur. Untuk bekerja, satu mesin pemecah butuh 3 menit/telur, satu mesin pengocok butuh 2 menit/telur, dan satu mesin penggoreng butuh 5 menit/telur. Waktu memindahkan telur dari satu mesin ke mesin lainnya dianggap tidak ada.
Contoh: Untuk memasak 3 telur waktu yang dibutuhkan adalah 12 men it dengan ilustrasi sebagai berikut:
Berapa menitkah waktu minimum yang diperlukan untuk memasak 15 telur?
5 jawaban
Thomas Dwi Awaka8 tahun lalu
Pernah Jago OSK
2
Dengan sedikit Niat dan Nguli... Jawabannya 27 Menit
Kadek Surya Mahardika8 tahun lalu
0
soal diatas bisa kita selesaikan dengan mudah (karena hanya sampai 15 telur kita kuli aja :v)
1 1 1 4 4 4 7 7 7 10 10 10 13 13 13
2 2 2 5 5 5 8 8 8 11 11 11 14 14 14
3 3 3 6 6 6 9 9 9 12 12 12 15 15 15
1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15
2 2 4 4 6 6 8 8 10 10 12 12 14 14
1 1 1 1 1 5 5 5 5 5 9 9 9 9 9 13 13 13 13 13
2 2 2 2 2 6 6 6 6 6 10 10 10 10 10 14 14 14 14 14
3 3 3 3 3 7 7 7 7 7 11 11 11 11 11 15 15 15 15 15
4 4 4 4 4 8 8 8 8 8 12 12 12 12 12
jika kita hitung dari akhir telur ke-3 yakni 12 menit maka untuk memasak 15 telur diperlukan waktu 27 menit CMIIW....
galangkangin gotera7 tahun lalu
0
Alternatif kuli, bisa menggunakan dynamic programming (DP) yang kemungkinan ketidaktelitiannya lebih sedikit
Anggaplah ada 4 fase:
- belum siap (fase 0)
- sudah dipecah (fase 1)
- sudah dikocok (fase 2)
- sudah digoreng (fase 3)
Anggap juga telurnya dinomori dari 1 sampai 15. Kita ingin agar waktu jadi telur 1 <= waktu jadi telur 2 <= waktu jadi telur 3 <= ... <= waktu jadi telur 15.
Anggap juga Ci adalah banyaknya alat ke-i yang kita miliki. Pada kasus ini, C1 = 3, C2 = 2, C3 = 4. Anggap Wi sebagai waktu yang diperlukan alat ke-i untuk memproses sebuah telur. Pada kasus ini, W1 = 3, W2 = 2, W3 = 5.
Misalkan F(N, i) : waktu tercepat telur ke-N menyelesaikan fase ke-i. Jawaban yang kita cari adalah F(15, 4)
Base case: F(N, 1) = 0. Karena semua telur sudah siap di awal
Untuk mencari F(N, i), kita cari waktu tercepat dimana telur ke-N dapat mulai di proses fase ke-i. Ada 2 faktor yang mempengaruhi:
- Waktu telur ke-N selesai di proses pada fase ke-(i-1). Waktu tersebut adalah F(N, i-1)
- Waktu ada alat ke-i yang kosong. Karena F(1, i) <= F(2, i) <= F(3, i) <= ... <= F(N, i), kita bisa mulai menggunakan alat ke-i lagi di waktu ke F(N - Ci, i). Karena pada waktu tersebut, telur ke N - Ci selesai di proses dan kita bisa meletakkan telur ke-i.
Jadi, telur ke-N paling cepat dapat dimasukkan ke fase ke-i pada menit ke max(F(N, i-1), F(N - Ci, i). Jadi, F(N, i) = max(F(N, i-1), F(N - Ci, i)) + Wi
Selanjutnya, tinggal mengisi tabel. Mengisi tabel ini cukup ringan karena angkanya kecil-kecil
| i\N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 3 | 3 | 3 | 6 | 6 | 6 | 9 | 9 | 9 | 12 | 12 | 12 | 15 | 15 | 15 |
| 3 | 5 | 5 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 4 | 10 | 10 | 12 | 13 | 15 | 15 | 17 | 18 | 20 | 20 | 22 | 23 | 25 | 25 | 27 |
Jadi, jawabannya adalah 27 menit.
Masuk untuk menulis jawaban