Olimpiade Sains Provinsi (OSP) 2017 - Komputer, Nomor 3
Bilangan unik lainnya yang disukai Pak Dengklek adalah Bilangan Kompeten. Sebuah bilangan X disebut Bilangan Kompeten apabila digit-digit dart X menurun atau menaik dari kiri ke kanan. Contoh Bilangan Kompeten yang menaik adalah 12234 dan contoh Bilangan Kompeten yang menurun adalah 9844200. Tiba-tiba Pak Dengklek penasaran, ada berapa Bilangan Kompeten yang nilainya kurang dari (10^10)?
2 jawaban
Michael Cahyadi Tjondro Kusumo8 tahun lalu
6
Soal ini kita hitung saja sama seperti soal sebelumnya, yaitu dengan menggunakan Kombinasi dengan Repetisi lalu mengurutkan angkanya sendiri.
Tetapi perlu diketahui bahwa untuk menghitung bilangan dibawah 1010 kita memerlukan 0 untuk diletakkan di depan, sedangkan cara yang kita gunakan sebelumnya akan memposisikan 0 untuk selalu berada di paling kanan.
Jadi untuk menghitung ini, saya akan tambahkan 1 angka lagi di luar 0-9 yaitu "0 yang dianggap lebih besar dari 9". Dengan begitu kita hanya perlu menambahkan 1 digit lagi dalam perhitungan. Jadi rumus kombinatoriknya adalah:
Terlihat mudah, tapi sebenarnya ini masih overcounting. Kenapa? Mari kita lihat lagi.
Saya akan memisalkan "0 yang dianggap lebih besar dari 9" dengan "A". Jika melakukan perhitungan ini, kita akan menemukan bilangan yang hanya memiliki digit "A" dan "0" sebanyak 9 kali. Dan kita juga akan menemukan satu bilangan yang hanya terdiri dari digit "A" saja.
Jadi hasil perhitungan tadi kita kurangi dengan 10 menjadi 184746.
Lalu jangan lupa kita jumlahkan dengan hasil perhitungan kita dari nomor selanjutnya yaitu 92378. Tapi jangan lupa bahwa pada kedua perhitungan terdapat sejumlah bilangan yang sama, yaitu bilangan yang hanya terdiri dari 1 macam digit dan atau 0. Karena banyaknya macam digit ada 9 selain 0 dan bilangan bernilai 0 hanya 1 kemungkinan pembentuknya, jawaban kita menjadi:
184746 + 92378 - 9*10 - 1 = 277033
CMIIW
Michael Cahyadi Tjondro Kusumo8 tahun lalu
O iya gan, maaf atas kesalahannya terima kasih sudah diingatkan, sudah saya revisi
bu dengklek8 tahun lalu
jadi begini pak,, anda tau PANTEK
MAN 2 Kudus7 tahun lalu
kan sama aja hasilnya, yg dikoreksi yg mn?
MAN 2 Kudus7 tahun lalu
Masuk untuk menulis jawaban
TOKI 2012, IF ITB 2012. http://olimpiadeinformatika.com
saya ingin mengoreksi,
Pertama, 184756 - 10 seharusnya 184746
Kedua, untuk perhitungan bilangan yang hanya terdiri dari 1 macam digit :
- jika pembentuknya cuma 0 maka cuma 1 kemungkinan {0}
- jika pembentuknya sama bukan 0, maka ada 9 kemungkinan digit dikali kemungkinan jumlah digit yaitu 10 {1,11,...,1111111111,2,22,...,2222222222,...,...,9999999999}
Sehingga seharusnya dikurangi 91
184746 + 92378 - 91 = 277033
https://ideone.com/5VKebu (di ideone TLE, harus jalankan di komputer lokal, butuh waktu 15-30 menit)