Olimpiade Sains Provinsi (OSP) 2013 - Komputer, Nomor 22–23
Deskripsi Untuk Soal Nomor 22 dan 23
Terdapat N kota dengan N nama berbeda. Setiap kota memiliki populasi penduduk masing-masing. Pemerintah negara tersebut pusing karena terdapat terlalu banyak kota. Pemerintah tersebut berencana menggabungkan kota-kota tersebut hingga hanya tersisa satu kota. Caranya begini. Selama masih ada 2 kota atau lebih, pemerintah memilih 2 kota sesuka dia, kemudian menggabungkan kedua kota tersebut. Nama kota yang baru tersebut ialah nama salah satu kota dari kedua kota asalnya yang memiliki jumlah penduduk lebih banyak. Apabila jumlah penduduknya sama, namanya boleh yang mana saja. Tugas Anda pada soal ini ialah menghitung ada berapa nama kota berbeda dari kota terakhir yang mungkin terjadi dengan asumsi pemerintahnya memilih kedua kota tersebut secara acak?
22.
Misalkan N = 8, dan jumlah penduduk masing-masing kota adalah 2, 50, 24, 21, 1, 9, 15, dan 5 orang. Setelah seluruh kota berhasil digabung menjadi 1 kota, ada berapa nama kota berbeda dari kota yang mungkin?
23.
Misalkan N = 100, dan tiap kota diberi nomor 1 sampai 100. Jumlah penduduk di kota i adalah i*i. Ada berapa nama kota berbeda dari kota yang mungkin?
4 jawaban
Reinhart Hermanus11 tahun lalu
TOKI 2011
1
22.
Untuk mengetahui ada berapa kemungkinan nama kota yang tersisa, kita harus mengetahui bagaimana cara menentukan apakah sebuah kota bisa menjadi 1 kota yang tersisa. Untuk mempermudah, mari kita urutkan populasi setiap kota secara menaik:
| Kota : | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Populasi : | 1 | 2 | 5 | 9 | 15 | 21 | 24 | 50 |
Sekarang kita analisa bagaimana cara agar kota ke i bisa menjadi 1 kota yang tersisa. Cara agar kota i bisa mejadi 1 kota yang tersisa adalah:
-
Bergabung dengan semua kota j dimana j<i supaya populasi kota i semakin banyak
- Bergabung dengan semua kota j dimana j>i yang memiliki populasi lebih kecil atau sama dengan kota i
Mari kita cek semua kota:
Kota 1, tidak bisa bergabung dengan kota 2, maka tidak bisa menjadi 1 kota tersisa.
Kota 2, bergabung dengan kota 1, populasi menjadi 3. Tidak bisa bergabung dengan kota 3 karena populasi masih lebih kecil dari 5.
Kota 3, bergabung dengan kota 1, populasi menjadi 6. Bergabung dengan kota 2, populasi menjadi 8. Tidak bisa bergabung dengan kota 4 karena populasi masih lebih kecil dari 9.
Kota 4, bergabung dengan kota 1, populasi menjadi 10. Bergabung dengan kota 2, populasi menjadi 12. Bergabung dengan kota 3, populasi menjadi 17. Bergabung dengan kota 5, populasi menjadi 31. Bergabung dengan kota 6, populasi menjadi 42. Bergabung dengan kota 7, populasi menjadi 66. Bergabung dengan kota 8, populasi menjadi 116. Maka kota 4 bisa menjadi 1 kota yang tersisa.
Kita bisa melihat, bahwa apabila kota i bisa menjadi 1 kota yang tersisa, maka semua kota yang memiliki populasi lebih besar atau sama dengan populasi kota i pasti juga bisa menjadi 1 kota yang tersisa. Maka setelah kita melihat bahwa kota 4 bisa menjadi 1 kota yang tersisa, berarti kota 5,6,7, dan 8 juga bisa menjadi 1 kota yang tersisa. Berarti jawaban untuk soal ini adalah 5 kota.
23.
Cara yang sama dengan nomor 22, jawabannya 97.
Masuk untuk menulis jawaban