Olimpiade Sains Provinsi (OSP) 2018 - Komputer, Nomor 30–31
Deskripsi Untuk Soal Nomor 30 dan 31
Untuk menghilangkan penat, Pak Blangkon sering sekali jalan-jalan ke pekarangan di belakang rumahnya. Pekarangannya berukuran 7x8 petak yang di dalamnya terdapat N buah pohon. Saat berada di posisi tertentu Pak Blangkon menyadari bahwa hanya beberapa pohon saja yang bisa terlihat pada delapan arah mata angin, karena pohon tertentu berada tepat di belakang pohon lainnya saat pandangan tertuju pada arah tertentu. Jika dilihat dari atas dalam koordinat dua dimensi, Pak Blangkon ada di posisi B sedangkan pohon-pohonnya ada di posisi P. Seperti contoh pada gambar di bawah ini.
Pada gambar di atas, dari 10 pohon hanya 4 pohon yang bisa dilihat secara langsung oleh Pak Blangkon pada delapan arah mata angin, sedangkan pohon-pohon lainnya terhalang oleh pohon di depannya.
30.
Jika susunan pohon dalam pekarangan Pak Blangkon adalah sebagai berikut:
Ada berapa kemungkinan posisi Pak Blangkon harus berdiri supaya jumlah pohon yang bisa dilihatnya semaksimal mungkin?
Jawaban: ……………. {tuliskan jawaban dalam bentuk angka saja}
31.
Diketahui susunan pohon dalam pekarangan Pak Blangkon adalah sebagai berikut:
Pak Dengklek bertamu ke rumah Pak Blangkon dan diajak berkeliling di pekarangannya. Karena Pak Dengklek benci pohon, ada berapa kemungkinan posisi Pak Blangkon harus berdiri bersama Pak Dengklek supaya jumlah pohon yang bisa dilihat seminimal mungkin?
Jawaban: ……………. {tuliskan jawaban dalam bentuk angka saja}
4 jawaban
Noya Aldiputera7 tahun lalu
Jika ingin mendownvote, jangan lupa juga untuk komen tentang kesalahannya. That'll be helpful for everyone, don't let that be a habit.
1
Untuk mempermudah, kita acukan sebuah koordinat dalam gridnya seperti gambar berikut.
Pertama-tama, carilah banyaknya pohon yang maksimum yang bisa dilihat pada suatu petak (Cari, bukan menghitung banyaknya petak). Kenapa? Karena hal ini bisa dilakukan secara langsung dengan insting yang sehingga pendekatan ini relatif cepat. Jika sudah mencari secara heuristik, ternyata petak ini memiliki jumlah pohon yang maksimum, yaitu 6 pohon. Dengan intuisi, terdapat beberapa observasi yang bisa anda buat:
- Observasi 1. Petak-petak yang berada di ujung pekarangan tidak mungkin bisa melihat 6 pohon secara langsung. (Seperti
.)
- Observasi 2. "Suatu petak memiliki jumlah pohon (yang bisa dilihat) adalah 6", ekspresi yang ekuivalennya yaitu "suatu petak memiliki pemandangan kosong sebanyak 2".
Observasi 2 jika dilakukan setelah Observasi 1 bisa menjadikan waktu pencarian lebih pendek. Jika anda naif, maka bisa saja anda melakukan pencarian (
banyaknya pohon di pekarangan,
ukuran pekarangan). Namun dengan observasi ini, kita bisa melakukan
pencarian, lebih efektif. Lakukan pencarian, anda dapatkan hasil berikut (3 petak)
Untuk yang selanjutnya, saya masih belum ada ide selain melakukannya secara naif. Namun hal yang terpenting adalah banyaknya pohon minimum yang bisa dilihat adalah 3. Setiap petak minimal bisa melihat 3 pohon.
Masuk untuk menulis jawaban
