Pembahasan OSP 2010 no.2 dan 25

Melanjutkan postingan pembahasan soal saya yang terdahulu, kali ini saya akan membahas soal-soal olim lagi. Kali ini yang pengen saya bahas adalah soal OSP 2010 nomor 2 dan 25. Kenapa saya milih kedua nomor itu ? Karena kedua nomor itu menarik,dan sudah saya temukan jawaban dari kedua soal itu. Kalo ga nemu,ngapain dibahas *loh

Oke, langsung aja ke soalnyaa

2. Panitia penyelenggara OSN bagian akomodasi mengatur penempatan para delegasi wakil-wakil
provinsi di sebuah hotel. Delegasi-delegasi itu masing-masing dengan anggota yang jumlahnya
bervariasi, dan rencana kedatangannya pun tidak bersamaan. Para anggota delegasi yang sama
diasumsikan datang bersamaan. Karena jumlah kamar di hotel itu agak terbatas, panitia
menetapkan suatu pengaturan. Selama kamar-kamar kosong masih tersedia, setiap kamar kosong
ditempati oleh dua orang dari delegasi yang sama. Jika jumlahnya ganjil, yang satu orang itu akan
ditentukan belakangan setelah yang berdua-berdua selesai ditempatkan. Selama masih ada kamar
kosong, yang satu orang itu pun ditempatkan di kamar yang kosong. Saat tidak ada kamar kosong
tesisa, setiap orang yang baru datang akan ditempatkan di kamar yang baru ditempati sendirian.
Jika ada beberapa pilihan kamar kosong, selalu dipilih kamar dengan nomor yang paling kecil.
Jika tidak ada lagi kamar kosong, tapi ada beberapa kamar yang masih satu orang, juga dipilih
mulai dari kamar dengan nomor terkecil. Sekarang anda ketahui ada 8 kamar di hotel itu dan ada
8 delegasi yang akan datang yang jumlahnya berturut-turut sesuai dengan urutan waktu
kedatangan adalah 3, 1, 3, 2, 1, 3, 2, 1. Jika kamar dinomori dari 1 sampai dengan 8, dan delegasi
dinomori sesuai dengan urutan kedatangan dari 1 sampai 8, dengan siapakah anggota delegasi
provinsi ke 8 akan sekamar?

Pembahasan

Untuk soal ini, untuk delegasi yang jumlahnya 3 atau 2 orang itu diprioritaskan kamarnya. Untuk yang jumlahnya orangnya 3, disisakan 1 orang yang akan ditunda dulu pembagian kamarnya, lalu yang jumlahnya 2, tidak perlu karena jumlah satu kamar adalah 2 orang. Untuk delegasi yang 1 orang, ditunda juga.

Bagannya adalah sebagai berikut (diurutkan dari kedatangan setiap delegasi)

3 == (dikurangi 2 orang di kamar 1) ==> sisa 1 orang (delegasi 1)
1 == (ditunda pembagian kamarnya) ==> sisa 1 orang (delegasi 2)
3 == (dikurangi 2 orang di kamar 2) ==> sisa 1 orang (delegasi 3)
2 == (dikurangi 2 orang di kamar 3) ==> sisa 0 orang (delegasi 4)
1 == (ditunda pembagian kamarnya) ==> sisa 1 orang (delegasi 5)
3 == (dikurangi 2 orang di kamar 4) ==> sisa 1 orang (delegasi 6)
2 == (dikurangi 2 orang di kamar 5) ==> sisa 0 orang (delegasi 7)
1 == (ditunda pembagian kamarnya) ==> sisa 1 orang (delegasi 8)

Lalu, sisa-sisa 1 orang itu,digabungin lagi.

delegasi 1 dengan delegasi 2 di kamar 6
delegasi 3 dengan delegasi 5 di kamar 7
delegasi 6 dengan delegasi 8 di kamar 8

Jadi, yang sekamar dengan delegasi 8 adalah delegasi ke 6.

~~~

25. Perhatikan potongan algoritma berikut

funtion Z(l: integer; r: integer);
begin
if l < r then z := z(l, ((l+r) div 2) – 1) + z(((l+r) div 2) + 1, r) + 1
else z := 1;
end;

Berapakah yang akan dicetak pada pemanggilan fungsi Z(1, 10)?

Pembahasan

post sebelumnya sangat sesat jawabannya, akan saya edit. Maaf kalo sebelumnya anda disesati -_-

Ini rekursif+divide and conquer simpel. Berikut alur rekursifnya.

z(1,10)
= z(z(1,4)+z(6,10)+1)
= z((z(1,1)+z(3,4)+1)+(z(6,7)+z(9,10)+1)+1)
= z(1+(z(3,2)+z(4,4)+1)+1+((z(6,5)+z(7,7)+1)+(z(9,8)+z(10,10)+1)+1)+1)
= 1+1+1+1+1+1+1+1+1+1+1+1+1
= 13