Bahas Soal Tebak Himpunan, OSN 2013

Hai, gw mau ngasih kalian pembahasan soal tebak himpunan versi gw. Semoga bisa berguna yah :3

Soal bisa dilihat di sini : http://tokilearning.org/problem/1606
atau di sini : (diambil dari tokilearning juga) : Tebak Himpunan

Jadi gw bahasnya per subtask aja yah 😀
Subtask 1 & 2
Nah, OSN tahun lalu khususnya ada games interaktifnya, jadi Subsoal 1 dan 2 itu bisa kita mainin 😀 , gamesnya keren loh :3 . Jadi subsoal 1 dan 2 udah cukup mainin gamenya aja ntar dapet juga source codenya kalo selesai 😛

Subtask 3 & 4
Sebenarnya udah sangat jelas, kita bisa dapetin subtask 3 & 4 dengan bruteforce. Mengapa karena k cuma 1, kita coba aja cetak semua dari 1 sampai N. Tiap ada yang bisa jadi simpen aja di array. Kalau udah selesai ngecek dari 1..N cetak aja isi arraynya tersebut 😀

Subtask 5
Liat S. S selalu berisikan dari 1 .. N. Untuk itu kita menggunakan binary search. Kita cek posisi tengah sekarang dan posisi tengah + 1. Kalau posisi tengahnya ‘bisajadi’ dan posisi tengah + 1 nya ‘tidak’ maka cetak dari 1..posisi tengah tersebut. Kalau posisi tengahnya ‘bisajadi’, ama posisi tengah + 1 nya juga ‘bisajadi’ maka awalnya dimajuin jadi tengah + 1, kalau nggak akhirnya dimundurin jadi tengah – 1

Subtask 6
Kalo cara gw, pertama gw buat array of boolean, yang pertama gw truein
Di for 2 lapis, terus dicek kemungkinan a ama b nya. Jika ternyata tidak, maka a dan b bukan bagian dari himpunan tersebut. Langsung aja arraynya kita false-in. Jika ‘bisajadi’, maka cek kalo arraynya udah false, maka bukan himpunannya. Kalo masih true dibiarin aja. Nanti pas udah ngecek semua kemungkinan, cetak semua isi array yang masih true.

Sekian pembahasan saya. Semoga bermanfaat

Advertisements

About Josua Aditya Mustiko

KnightSaber77 ~

Posted on August 28, 2014, in Uncategorized. Bookmark the permalink. 1 Comment.

  1. imba m(_ _)m..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: