Olimpiade Sains Provinsi (OSP) 2023 - Komputer, Nomor 11–13

Untuk menjawab pertanyaan 1 dan 2 di bawah ini, asumsikan bahwa N = 5 dan M = 6, dan bobot-bobot kentang pada truk A dan truk B masing-masing adalah:

A = {7, 2, 3, 8, 5}

B = {6, 8, 5, 8, 12, 10}

Seandainya Pak Dengklek ingin memindahkan kentang dengan bobot 6 dari truk B ke truk A, berapakah total bobot kentang yang harus dipindahkan Pak Dengklek dari truk B ke truk A, sesuai dengan aturan di atas?

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

Untuk menjawab pertanyaan 1 dan 2 di bawah ini, asumsikan bahwa N = 5 dan M = 6, dan bobot-bobot kentang pada truk A dan truk B masing-masing adalah:

A = {7, 2, 3, 8, 5}

B = {6, 8, 5, 8, 12, 10}

Berapakah total bobot minimum dari kentang-kentang yang dipindahkan dari truk B ke truk A agar tujuan Pak Dengklek tercapai?

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

MENJUAL KENTANG

Buatlah program menggunakan bahasa C/C++ sesuai deskripsi cerita di atas untuk menentukan total bobot kentang terkecil yang perlu dipindahkan oleh Pak Dengklek agar tujuan tercapai sesuai dengan peraturan di atas.

Format Masukan:
Baris pertama berisi dua buah bilangan: N (banyaknya kentang di truk A) dan M (banyaknya kentang di truk B). Baris kedua berisi N buah bilangan, menyatakan bobot-bobot kentang di truk A, sedangkan baris ketiga berisi M buah bilangan, menyatakan bobot-bobot kentang di truk B.

Format Keluaran:
Keluaran terdiri dari satu baris, yaitu sebuah bilangan yang menyatakan berapa total bobot kentang yang harus dipindahkan dari truk B ke truk A sehingga tujuan Pak Dengklek tercapai. Apabila tujuan tersebut tidak mungkin tercapai berdasarkan kondisi yang ada, keluarkan nilai -1.

Peringatan: Untuk dapat menjawab pertanyaan ini dengan benar, program Anda mungkin perlu menggunakan tipe data long long untuk dapat menyimpan data dengan nilai yang besar. Tipe data int saja mungkin tidak cukup!

Contoh Masukan dan Keluaran:

3 4
5 1 3
8 5 4 9

17

1 4
2
1 5 5 5

15

Penjelasan Contoh:
Truk A berisi 3 kentang dengan bobot-bobot = {5, 1, 3}, sehingga rata-ratanya = (5 + 1 + 3)/3 = 3. Truk B berisi 4 kentang dengan bobot-bobot = {8, 5, 4, 9} sehingga rata-ratanya = (4 + 5 + 8 + 9)/4 = 6.5. Pak Dengklek dapat memindahkan kentang dengan bobot 8 dan 9 (total = 8 + 9 = 17) dari truk A ke truk B, sehingga rata-rata bobot kentang di truk A menjadi (5 + 1 + 3 + 8 + 9)/5 = 5.2, sedangkan rata-rata bobot kentang di truk B menjadi (4 + 5)/2 = 4.5. Dalam hal ini, tercapai tujuan Pak Dengklek, yaitu rata-rata bobot kentang di truk A menjadi lebih besar dari rata-rata bobot kentang di truk B, dan semua peraturan terpenuhi. Tidak ada cara lain yang dapat digunakan untuk mencapai tujuan ini dengan total bobot lebih kecil dari 17. Oleh karena itu, jawaban pada kasus ini adalah 17.

Batasan:

Untuk semua kasus uji berlaku:

• 1 ≤ N, M ≤ 100 000
• 1 ≤ A_i, B_i ≤ 100 000

Subtask 1 (20%)
Subtask ini hanya berisi satu kasus uji, yaitu sebagai berikut:

8 10
5 6 3 4 2 7 4 5
7 5 5 7 3 4 3 6 5 3

Subtask 2 (30%)
Pada subtask ini berlaku:

• 1 ≤ N, M ≤ 1000
• 1 ≤ A_i, B_i ≤ 1000
• Tidak ada dua kentang dengan bobot yang sama

Subtask 3 (50%)
Tidak ada batasan tambahan.