Olimpiade Sains Provinsi (OSP) 2022 - Komputer, Nomor 15–18

Jika Pak Dengklek akan mengangkut bebek-bebek dengan bobot B₁ = 2, B₂ = 2, dan B₃ = 3 pada kandang dengan biaya angkut C₁ = 5 rupiah per kg dan kapasitas P₁ = 4, berapakah biaya pengangkutan yang harus dikeluarkan Pak Dengklek untuk satu kandang tersebut?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

Jika ada tiga kandang (K = 3) dengan kapasitas yang sama (P₁ = P₂ = P₃ = 3) sedangkan biaya angkut dari masing-masing kandang adalah C₁ = 5, C₂ = 2 dan C₃ = 3, sedangkan bebek Pak Dengklek ada 7 ekor (N = 7) dengan bobot yang kebetulan sama semua (B₁ = … = B₇ = 5), maka berapakah biaya terkecil yang perlu dibayarkan oleh Pak Dengklek untuk mengangkut semua bebek-bebeknya?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

Diketahui ada 3 buah kandang (K = 3) dengan kapasitas P₁ = 6, P₂ = 3, dan P₃ = 4, dengan biaya angkut per kg berat bebek dari masing-masing kandang adalah C₁ = 2, C₂ = 1 dan C₃ = 3 rupiah per kg. Jika diketahui bahwa Pak Dengklek memiliki 9 ekor bebek (N = 9) dengan berat masing masing (B₁, …, B₉) adalah 3, 2, 2, 4, 5, 3, 6, 8, dan 7, maka berapakah biaya angkut terkecil yang diperlukan oleh Pak Dengklek?

Jawaban: ............... {tuliskan jawaban dalam bentuk ANGKA saja}

MENGANGKUT BEBEK

Buatlah program menggunakan bahasa C/C++ untuk membantu menjawab pertanyaan Pak Dengklek di atas.

Format Masukan:
Baris pertama berisi sebuah bilangan K, menyatakan banyaknya bilangan. 2 baris berikutnya berisi masing-masing K buah bilangan bulat positif, menyatakan nilai kapasitas setiap kandang (P₁, …, P_K) serta biaya angkut untuk setiap kandang dalam satuan rupiah per kg berat bebek (C₁, …, C_K).

Kemudian baris ketiga berisi sebuah bilangan bulat N, menyatakan banyaknya bebek Pak Dengklek. Baris keempat berisi N buah bilangan bulat positif, menyatakan berat bebek-bebek Pak Dengklek dalam satuan kilogram.

Format Keluaran:
Keluaran terdiri atas satu baris berisi sebuah bilangan bulat positif, menyatakan total biaya terkecil yang diperlukan oleh Pak Dengklek untuk mengangkut semua bebek-bebeknya menggunakan satu atau lebih kandang-kandang yang ada.

Contoh Masukan dan Keluaran:

2
3 4
5 2
6
4 1 5 2 3 2

43

Penjelasan Contoh:
Pak Dengklek dapat memasukkan bebek ke-2 dan 4 (dengan bobot 1 kg dan 2 kg) ke dalam kandang pertama (dengan kapasitas 3 dan biaya per kg = 5) sehingga biaya yang dibutuhkan untuk kandang pertama adalah (1 + 2) x 5 = 15. Kemudian Pak Dengklek memasukkan bebek sisanya (yaitu bebek ke-1, 3, 5, dan 6 (dengan bobot 4, 5, 3 dan 2 kg) ke kandang kedua (dengan kapasitas 4 dan biaya angkut 2 per kg) sehingga kandang kedua memerlukan biaya (4 + 5 + 3 + 2) x 2 = 28. Biaya total kedua kandang berarti adalah 15 + 28 = 43. Tidak ada cara pengangkutan bebek yang lain ke dalam kandang-kandang tersebut yang menyebabkan biaya angkut menjadi lebih kecil dari 43. Oleh karena itu, jawaban yang diinginkan adalah 43.

Batasan:

Untuk semua kasus uji berlaku:

• 1 ≤ K ≤ 1000
• 1 ≤ N ≤ 100 000
• Untuk setiap B_i berlaku 0 < B_i ≤ 10⁶
• Untuk setiap P_i berlaku 0 < P_i ≤ 100 000
• Untuk setiap C_i berlaku 0 ≤ C_i ≤ 10⁶

Untuk 50% kasus uji berlaku:

• B₁ = B₂ = … = B_N (semua bebek memiliki berat yang sama).