OSNP Komputer 2024 Soal D Pemrograman

Details

Description

Studi Kasus D: Kalkulator Pengubah Basis

Deskripsi Cerita

Pak Dengklek memiliki sebuah kalkulator pengubah basis. Untuk menggunakan kalkulator ini, Pak Dengklek pada awalnya menuliskan sebuah bilangan bulat non-negatif X dalam basis 10. Pak Dengklek kemudian memerintahkan kalkulator tersebut untuk mengubah nilai X ke dalam basis B. Secara cepat, kalkulator tersebut akan menampilkan sebuah string Y tanpa leading zeroes* yang seharusnya
merupakan nilai X dalam basis B.

Namun, sangat disayangkan bahwa kalkulator tersebut tidak dapat menampilkan digit selain ‘0’ hingga ‘9’. Untuk digit di atas ‘9’, kalkulator tersebut akan menuliskan nilai digit tersebut dalam basis 10 tanpa leading zeroes. Misalnya, digit ‘A’ akan dituliskan sebagai “10”, digit ‘B’ akan dituliskan sebagai “11”, dan seterusnya.

Sebagai contoh, Pak Dengklek pada awalnya menuliskan bilangan X = 123 456. Pak Dengklek kemudian memerintahkan kalkulator tersebut untuk mengubahnya ke dalam basis B = 16. Bilangan 123 456 dalam basis 16 seharusnya adalah “1E240”, namun kalkulator tersebut malah akan menampilkan Y = “114240”.

Pak Dengklek kemudian secara cermat mengamati bahwa bisa jadi akan ada banyak bilangan berbeda, yang jika diubah ke dalam suatu basis yang sama, akan menampilkan hasil yang sama pula. Misalnya, 737 856 dalam basis 16 juga akan ditampilkan sebagai “114240”. Pun demikian 1 131 072 dalam basis 16 juga akan ditampilkan sebagai “114240”.

Diberikan nilai B dan Y, tugas Anda adalah menghitung banyaknya X berbeda, sehingga apabila X diubah ke dalam basis B, maka kalkulator akan menampilkan hasil berupa string Y. Karena jawabannya bisa sangat besar, keluarkan jawabannya modulo 1 000 000 007.

*) Sebagai catatan, sebuah string tidak memiliki leading zeroes apabila digit pertama bukan ‘0’ kecuali jika bilangan tersebut memang 0. Sebagai contoh, “42”, “0”, dan “1000” merupakan bilangan-bilangan tanpa leading zeroes.

Soal Pemrograman
Tulislah sebuah program dengan bahasa C/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:
B
Y

Format Keluaran
Keluarkan sebuah baris berisi sebuah bilangan bulat yang menyatakan banyaknya X berbeda, sehinggaapabila X diubah ke dalam basis B, maka kalkulator akan menampilkan hasil berupa string Y, modulo 1 000 000 007.

Contoh Masukan dan Keluaran
Contoh Masukan Contoh Keluaran
16 | 3
114240 |
4 | 0
114240 |
10 | 1
0
10 | 1
1001 |
1000000 | 649774399
123456789123456789123456789123456789 |

Penjelasan Contoh
Pada contoh pertama, terdapat 3 kemungkinan X berbeda, yakni 123 456, 737 856, dan 1 131 072; seperti yang telah dijelaskan pada deskripsi cerita.
Pada contoh kedua, tidak ada nilai X yang mungkin karena setiap bilangan yang diubah ke basis 4 pasti hanya memiliki digit 0, 1, 2, atau 3.
Pada contoh ketiga, hanya ada 1 kemungkinan X, yakni 0.
Pada contoh keempat, hanya ada 1 kemungkinan X, yakni 1001.
Pada contoh kelima, sebenarnya terdapat 26 649 774 581 kemungkinan X berbeda, namun perhatikan bahwa jawaban harus dalam modulo 1 000 000 007.

Batasan
Untuk seluruh kasus uji berlaku:
• 2 ≤ B ≤ 1 000 000
• 1 ≤ |Y| ≤ 100 000, dengan |Y| menyatakan panjang dari string Y
• Y hanya terdiri dari digit-digit ‘0’ hingga ‘9’ dan tidak memiliki leading zeroes

Batasan Tambahan untuk Subsoal 1 (Mudah)
Pada subsoal ini, untuk seluruh kasus uji berlaku:
• B ≤ 16
• |Y| ≤ 6
Batasan Tambahan untuk Subsoal 2 (Sulit)
Tidak ada batasan tambahan pada subsoal ini.

Pembahasan oleh cahInfor