Olimpiade Sains Provinsi (OSP) 2025 - Komputer, Nomor 9–12
Deskripsi Untuk Soal Nomor 9 dan 12
Studi Kasus C. Balada Kemasan Telur
Pak Dengklek ingin berjualan telur dengan modal uang sebesar N rupiah. Di pusat grosir, dijual berbagai tipe telur dalam kemasan persegi. Untuk setiap bilangan prima p, terdapat tipe telur p yang dijual di dalam kemasan berukuran p × p yang berisikan p × p buah telur, dengan harga p rupiah per kemasan. Perhatikan bahwa tidak ada tipe telur k dengan k adalah bilangan non-prima. Diketahui juga bahwa banyaknya stok tiap tipe telur tidak terbatas.
Karena Pak Dengklek tidak mau ribet, Pak Dengklek akan memilih tepat satu tipe telur saja dan membelanjakan seluruh modal uangnya untuk membeli tipe telur tersebut tanpa sisa. Dengan kata lain, Pak Dengklek harus memilih suatu tipe telur p sehingga p habis membagi N.
Setelah pulang dari pusat grosir, Pak Dengklek akan menjual kembali seluruh telur yang ia telah dapatkan. Pak Dengklek akan menyusun seluruh telur di dalam tepat satu kemasan baru berukuran s × t berisikan s × t buah telur.
Sebagai contoh, jika Pak Dengklek sekarang memiliki 36 butir telur, maka terdapat 9 ukuran kemasan yang mungkin: 1 × 36, 2 × 18, 3 × 12, 4 × 9, 6 × 6, 9 × 4, 12 × 3, 18 × 2, dan 36 × 1.
Sayangnya, Pak Dengklek belum tahu ukuran s × t mana yang akan menarik pelanggannya. Untuk itu, dengan modal uangnya, Pak Dengklek akan memilih suatu tipe telur sedemikian sehingga ketika Pak Dengklek menjual kembali seluruh telurnya, banyak kemungkinan kemasan s × t yang mungkin adalah sebanyak-banyaknya. Perhatikan bahwa jika s ≠ t, maka kemasan s × t dianggap berbeda dengan kemasan t × s.
9.
Apabila Pak Dengklek pada awalnya memiliki modal uang sebesar 111 111 rupiah, lalu ia memilih tipe telur 7 untuk dibelanjakan, maka berapakah banyak telur yang akan dijual kembali pada akhirnya?
Tuliskan jawaban dalam bentuk ANGKA.
10.
Dari 5 skenario berikut, manakah banyak telur yang menghasilkan banyak kemungkinan kemasan yang paling banyak?
- Jika Pak Dengklek menjual kembali 21 × 51 = 10 butir telur
- Jika Pak Dengklek menjual kembali 22 × 52 = 100 butir telur
- Jika Pak Dengklek menjual kembali 22 × 51 = 20 butir telur
- Jika Pak Dengklek menjual kembali 23 × 51 = 40 butir telur
- Jika Pak Dengklek menjual kembali 26 × 50 = 64 butir telur
11.
Apabila Pak Dengklek pada awalnya memiliki modal uang sebesar 45 rupiah, maka tipe telur apakah yang perlu Pak Dengklek pilih agar ketika ia menjual kembali seluruh telurnya, banyak kemungkinan kemasan yang mungkin adalah sebanyak-banyaknya? Jika terdapat lebih dari satu kemungkinan jawaban, pilih yang paling kecil.
Tuliskan jawaban dalam bentuk ANGKA.
12.
BALADA KEMASAN TELUR
Tulislah sebuah program dengan bahasa C++ sesuai deskripsi cerita dengan format dan batasan sebagai berikut. Perhatikan bahwa untuk setiap kasus uji berlaku time limit selama 2 detik dan memory limit sebanyak 256 MB.
Format Masukan:
Masukan diberikan dalam format berikut:
NFormat Keluaran:
Keluarkan sebuah baris berisi sebuah bilangan bulat yang menyatakan tipe telur yang perlu Pak Dengklek pilih agar ketika ia menjual kembali seluruh telurnya, banyak kemungkinan kemasan yang mungkin adalah sebanyak-banyaknya. Jika terdapat lebih dari satu kemungkinan jawaban, pilih yang paling kecil.
Contoh Masukan dan Keluaran:
| Contoh Masukan | Contoh Keluaran |
|---|---|
18 | 2 |
60 | 3 |
1000000007 | 1000000007 |
Penjelasan Contoh
Pada contoh pertama, untuk dapat membelanjakan seluruh modal uangnya, Pak Dengklek boleh memilih tipe telur 2 atau 3.
- Apabila Pak Dengklek memilih tipe telur 2, maka Pak Dengklek akan membeli 18 ÷ 2 = 9 kemasan yang masing-masing berisi 2 × 2 = 4 telur, sehingga ia akan memiliki 9 × 4 = 36 telur. Saat Pak Dengklek ingin menjual kembali seluruh telurnya, terdapat 9 kemungkinan kemasan yang mungkin: ukuran 1 × 36, 2 × 18, 3 × 12, 4 × 9, 6 × 6, 9 × 4, 12 × 3, 18 × 2, dan 36 × 1.
- Apabila Pak Dengklek memilih tipe telur 3, maka Pak Dengklek akan membeli 18 ÷ 3 = 6 kemasan yang masing-masing berisi 3 × 3 = 9 telur, sehingga ia akan memiliki 6 × 9 = 54 telur. Saat Pak Dengklek ingin menjual kembali seluruh telurnya, terdapat 8 kemungkinan kemasan yang mungkin: ukuran 1 × 54, 2 × 27, 3 × 18, 6 × 9, 9 × 6, 18 × 3, 27 × 2, dan 54 × 1.
Dengan demikian, untuk mendapatkan kemungkinan kemasan yang paling banyak, Pak Dengklek perlu memilih tipe telur 2.
Pada contoh kedua, untuk dapat membelanjakan seluruh modal uangnya, Pak Dengklek boleh memilih tipe telur 2, 3, atau 5. Dapat dihitung bahwa dengan membeli tipe telur 2, akan ada 16 kemungkinan kemasan yang mungkin; sedangkan dengan membeli tipe telur 3 ataupun 5, akan ada 18 kemungkinan kemasan yang mungkin. Karena terdapat lebih dari satu kemungkinan jawaban yang menghasilkan kemungkinan terbanyak yakni 18, Pak Dengklek akan memilih yang paling kecil yakni 3.
Pada contoh ketiga, perhatikan bahwa N = 1 000 000 007 adalah bilangan prima sehingga Pak Dengklek hanya dapat memilih tipe telur 1 000 000 007.
Batasan
- 2 ≤ N ≤ 1012
Batasan Tambahan untuk Subsoal 1 (Mudah)
- N ≤ 2000
Batasan Tambahan untuk Subsoal 2 (Sulit)
Tidak ada batasan tambahan pada subsoal ini.
Peringatan
Untuk dapat menjawab pertanyaan ini dengan benar, Anda mungkin perlu menggunakan tipe data long long untuk dapat menyimpan data dengan nilai yang besar. Tipe data int saja mungkin tidak cukup!
0 jawaban
Masuk untuk menulis jawaban