Olimpiade Sains Provinsi (OSP) 2012 - Komputer

1

Selisih jumlah umur Barnie dan Jecky 6 tahun yang lalu dan jumlah umur Barnie dan Jecky 5 tahun yang akan datang merupakan dua kali dari selisih umur Zeta 6 tahun yang lalu dan 5 tahun yang akan datang. Selisih umur Barnie dan Zeta adalah 31. Jumlah umur Jecky dan Zeta 1 tahun yang lalu adalah 70. Umur Jecky 7 tahun yang lalu merupakan dua kali dari umur Barnie 7 tahun yang lalu. Selain itu, diketahui umur Barinie, Jecky, dan Zeta saat ini adalah bilangan bulat. Berapa jumlah umur Barnie, Jecky, dan Zeta 3 tahun yang lalu?

2

Agar mudah diingat, Pak Dengklek membuat password untuk komputernya dengan mengacak hurufhuruf pada namanya, yaitu 'D', 'E', 'N', 'G', 'K', 'L', 'E', dan 'K'. Suatu ketika ia lupa password komputernya, dan memutuskan untuk mencoba semua kemungkinan pengacakan yang ada tanpa pengulangan. Berapakah waktu yang dibutuhkan untuk mencoba semua kemungkinan pengacakan tersebut, jika sekali mencoba suatu kemungkinan membutuhkan waktu 10 detik?

3

Pak Dengklek memiliki 1000 ekor bebek, yang diberi nomor 1 sampai dengan 1000. Pak Dengklek yang sedang berbaik hati, ingin memberikan Anda sebagian bebek yang dimilikinya. Anda bebas memilih beberapa bebek yang mana saja, asalkan memenuhi satu syarat khusus yang diminta Pak Dengklek: jika Anda memilih bebek bernomor x, Anda tidak boleh memilih bebek bernomor 3x. Misalnya, jika Anda memilih bebek bernomor 5, Anda tidak boleh memilih bebek bernomor 15. Berapa banyak maksimal bebek yang bisa Anda terima dari Pak Dengklek?

4

Pak Dengklek memiliki 1000 buah kartu. Setiap kartu terdiri dari dua sisi yang tampak identik. Pada kedua sisi setiap kartu, Pak Dengklek dapat memilih untuk menuliskan sebuah angka, atau tidak menuliskan apa-apa. Seribu buah kartu tersebut diletakkan oleh Pak Dengklek di atas meja, sehingga Anda dapat melihat bahwa pada sisi yang terbuka, semua kartu telah ditulisi angka yang berbeda, mulai dari 1 hingga 1000. Anda tidak dapat melihat sisi yang tertutup. Pak Dengklek mengatakan bahwa: "Jika pada satu sisi kartu tertulis bilangan ganjil, maka pada sisi lainnya pasti tertulis bilangan yang habis dibagi 3, DAN jika satu sisi sebuah kartu tidak terdapat tulisan apa-apa (kosong), maka pada sisi lainnya pasti tertulis bilangan yang habis dibagi 5". Berapa minimal kartu yang harus Anda balik untuk mengetahui apakah Pak Dengklek berkata benar atau tidak?

5

Didefinisikan n! = n x (n-1) x (n-2)... x 2 x 1. Berapakah banyaknya digit 0 beruntun di akhir 500! ?

6

Sebuah slot machine memiliki tiga roda undi. Di setiap roda ada 4 simbol, yaitu A, B, C, dan D. Setiap kali pengguna menarik tuas, ketiga roda undi akan berputar dan masing-masing roda berhenti di suatu simbol tertentu. Pengguna akan menang jika ketiga simbol yang ditunjukkan roda undi semuanya sama. Berapakah peluang pengguna untuk menang di slot machine ini?

7

Pak Dengklek sangat sayang dengan bebek-bebeknya. Ia mencatat hari ulang tahun setiap bebekbebeknya (hari, tanggal, dan bulan), sebagai contoh (Rabu, 2, Mei). Pak Dengklek tahu bahwa jika ia memiliki minimal 366 ekor bebek, maka pasti ada dua ekor bebek yang berulang tahun pada tanggal dan bulan yang sama, namun belum tentu harinya sama (asumsikan bahwa setahun selalu memiliki 365 hari). Pak Dengklek bertanya, berapakah jumlah minimal bebek yang harus ia miliki, agar ia yakin bahwa pasti ada 5 bebek yang berulang tahun pada hari, tanggal dan bulan yang sama?

8

Bilangan bulat positif terkecil yang memiliki tepat 6 pembagi (termasuk 1 dan dirinya sendiri) adalah 12. Bilangan bulat positif terkecil yang memiliki tepat 30 pembagi adalah...

Deskripsi untuk soal nomor 9 - 10

Tiga orang sahabat, Ari, Budi, dan Cici terdampar di sebuah pantai bersama seekor kucing. Mereka berusaha mengumpulkan makanan, dan yang berhasil mereka temukan hanyalah ikan-ikan kecil, namun dengan jumlah cukup banyak. Karena kelelahan, mereka memutuskan untuk beristirahat dan membangun tenda. Mereka berencana untuk memasak ikan keesokan harinya bersamasama.

Malamnya, ketika semua sedang tertidur, Ari bangun dari tidurnya. Karena ia kuatir pada keesokan harinya teman-temannya akan curang pada saat membagi ikan untuk sarapan, Ari mencoba mengamankan bagiannya. Ia membagi ikan-ikan tersebut ke dalam 3 bagian sama rata. Ternyata tersisa satu ekor ikan. Ari mengambil salah satu dari 3 bagian, dan memberikan sisa satu ekor ikan tadi ke kucingnya, dan kemudian tidur lagi. Tidak disangka, ternyata kedua temannya yang lain mempunyai pikiran untuk melakukan hal yang sama seperti Ari: bangun, membagi ikan (yang tersisa) ke dalam tiga bagian, dan mengambil bagiannya. Pada setiap pembagian, selalu tersisa satu ekor ikan yang kemudian diberikan kepada si kucing.

Keesokan paginya, mereka semua terbangun, dan tanpa saling memberitahu apa yang mereka lakukan pada malam harinya, mereka membagi ikan-ikan tersebut untuk bertiga. Sama seperti sebelumnya, pembagian dengan 3 menyisakan satu ekor ikan, yang diberikan kepada si kucing.

9

Berapakah jumlah minimum ikan yang terkumpul mula-mula?

10

Secara berturut-turut, berapakah jumlah ikan yang dimiliki oleh masing-masing Ari, Budi dan Cici pada akhirnya?

11

Dengan menggunakan hanya simbol 0, 1 dan 2, kita ingin membentuk string sedemikian rupa hingga selisih antara satu simbol dengan simbol di sebelahnya tidak lebih dari satu. Sebagai contoh, kita dapat membentuk string 011221 dan 2211010, tetapi tidak boleh membentuk string 102. Berapakah banyaknya string seperti ini yang panjangnya tepat 10 simbol?

12

. Beberapa anak berbaris dalam satu barisan. Sang Guru memerintahkan mereka untuk mengubah posisi barisan mereka, dengan aturan: setiap anak boleh memilih untuk tetap di posisinya semula, atau bertukar dengan orang yang berdiri tepat di depan atau tepat di belakangnya (apabila ada dan belum pernah bertukar). Jika ada 3 orang anak yang berbaris, dengan urutan awal A, B, C, maka ada 3 kemungkinan hasil setelah perintah Guru dijalankan, yaitu: tetap, berubah menjadi B,A,C, atau berubah menjadi A,C,B. Berapa kemungkinan hasil yang mungkin apabila ada 15 anak yang berbaris?

13

Anda memiliki sebuah neraca yang dapat digunakan untuk membandingkan bobot dua obyek dan mengetahui mana yang lebih berat. Jika Anda memiliki 128 benda, berapa kali minimal Anda harus menggunakan neraca tersebut untuk menentukan mana benda terberat DAN benda terberat kedua dari 128 benda tadi?

14

Dalam papan catur ukuran 3x3, dua kuda putih berada pada posisi pojok atas (kanan dan kiri), sedangkan kedua kuda hitam berada pada posisi pojok bawah (kanan dan kiri). Diketahui tidak boleh ada dua kuda berada di petak yang sama pada saat apapun. Tentukan, dengan minimal berapa gerakan menggunakan langkah kuda catur, posisi kuda hitam dan putih saling bertukar (kuda-kuda hitam di pojok atas, kuda-kuda putih di pojok bawah)? (Sebagai keterangan, pada catur, satu langkah kuda dilakukan dengan menggeser kuda satu petak secara horizontal (baik ke kiri maupun ke kanan) dan dua petak secara vertikal (baik ke atas maupun ke bawah), maupun menggeser kuda dua petak secara horizontal dan satu petak secara vertikal).

15

Pak Dengklek memiliki 2 buah takaran air, A dan B, masing-masing volumenya adalah 35 ml dan 48 ml. Jika Pek Dengklek ingin mengambil tepat 22 ml air, maka Pak Dengklek dapat melakukannya dengan menggunakan tiga langkah penakaran, yaitu: takar 2 kali dengan takaran A (2x35=70 ml) lalu kurangkan dengan 1 kali takaran B (70-48=22). Jika Pak Dengklek ingin mengukur tepat 10 ml air, berapakah minimal penakaran yang diperlukan?

16

Pak Dengklek memiliki 80 buah koin emas, semuanya dengan bentuk dan rupa yang sama. Sayangnya, di antara 80 koin tadi, diketahui ada satu koin yang palsu. Pak Dengklek tidak tahu yang mana yang palsu, akan tetapi ia mengetahui bahwa koin yang palsu pasti lebih ringan dari yang asli. Pak Dengklek memiliki sebuah neraca yang bisa ia gunakan untuk membandingkan berat dua buah benda. Pak Dengklek kemudian memilih sebuah strategi yang memastikan banyak penimbangan pada kasus terburuk adalah sesedikit mungkin. Berapakah banyak penimbangan yang Pak Dengklek perlukan pada kasus terburuk apabila ia menggunakan strategi tersebut?

Deskripsi untuk soal nomor 17 - 18

Dalam sebuah pertandingan renang antar RW terdapat 8 orang peserta, mereka adalah A, B, C, D, E, F, G, dan H. Setelah pertandingan dilakukan secara tertutup, Pak Lurah yang merupakan juri mengumumkan hasilnya. Ia tidak mengumumkan urutan peringkat dari 1 sampai 8, (makin kecil peringkat seseorang tentunya semakin baik peringkatnya), tetapi hanya memberikan beberapa fakta mengenai pertandingan, yaitu sebagai berikut:

  • E berada 3 peringkat di bawah B dan 4 peringkat di atas F

  • Peringkat A lebih baik dari D, dan peringkat D lebih baik dari H

  • Selisih peringkat A dan D sama dengan selisih peringkat D dan H

  • Peringkat G lebih baik dari peringkat C
17

Ada berapa konfigurasi urutan peringkat yang mungkin?

18

Jika diketahui peringkat C lebih baik dari E, tuliskanlah urutan peringkat dari 1 sampai dengan 8.

Deskripsi untuk soal nomor 19 - 22

Terdapat 100 titik, dinomori 1 sampai 100. Seekor kelinci bernama Listi berada di titik 1. Listi dapat berpindah lokasi dengan meloncat. Apabila Listi meloncat sejauh X, maka apabila ia sebelumnya berada di titik Y, ia akan sampai di titik Y+X. Tentu saja Listi tidak dapat melakukan loncatan tersebut apabila Y+X lebih besar dari 100. Sebuah cara bagi Listi untuk berpindah dari titik X ke titik Y didefinisikan sebagai urutan panjang loncatan yang ia lakukan. Dengan kata lain, dua cara dianggap berbeda apabila:

a) Jumlah loncatan di kedua cara berbeda, atau

b) Ada indeks i di mana loncatan ke-i di cara pertama berbeda dengan loncatan ke-i di cara kedua.

19

Apabila Listi hanya dapat melakukan loncatan dengan panjang 7 atau 9, berikan salah satu cara ia dapat mencapai titik 72. Berikan sebagai urutan loncatan yang harus ia lakukan.

20

Apabila Listi hanya dapat melakukan loncatan dengan panjang 7 atau 9, ada berapa cara berbeda yang dapat ia lakukan untuk mencapai titik 72?

21

Apabila Listi dapat melakukan loncatan dengan panjang 1 atau 2 saja, ada berapa cara berbeda yang dapat ia lakukan untuk mencapai titik 12?

22

Apabila Listi hanya dapat melakukan loncatan yang panjangnya adalah angka pangkat 1, 2, 4, 8, 16, 32, dan 64, berikan salah satu cara untuk mencapai titik 100 yang menggunakan jumlah loncatan sesedikit mungkin.

23

Diberikan sebuah barisan bilangan bulat yang mana untuk i > 0, bilangan ke-i pada barisan ini merupakan hasil kali dari (1 x 2 x ... x (i-1) x i) dengan bilangan pertama pada barisan ini. Jika jumlah delapan bilangan pertama pada barisan ini adalah 416097, maka bilangan kesepuluhnya adalah ...

24

Jika 4! berarti 4 x 3 x 2 x 1 = 24. Tuliskanlah kedua digit terakhir dari 1! + 2! + 3! + ... + 9999!

25

Jika a, b, c, d dan e adalah bilangan-bilangan cacah (0,1,2, ...) dan diketahui pula a x b x c x d x e = 864, berapakah banyaknya kemungkinan nilai-nilai kelima bilangan tersebut dapat dibuat jika a x b harus sama dengan 12 dan setiap bilangan boleh digunakan lebih dari satu kali?

26

Diketahui definisi fungsi sebagai berikut. Jika max(a,b) adalah fungsi yang mengembalikan nilai maksimum dari a dan b, berapakah nilai dari F1(4,3)?

function F1(i, j : integer) : integer;
begin
 if (i < 0) or (j < 0) then
 F1 := max(i, j) + 1
 else if i = j then
 F1 := F1(i + 1, j - 1)
 else
 F1 := F1(i - 2, j - 1) + F1(i - 1, j - 2);
end;
27

Dari definisi fungsi sebagai berikut, berapakah nilai dari F2(6,2)?

function F2(n, k : integer) : integer;
var
 i, x : integer;
begin
 x := 1;
 for i := n downto k + 1 do
 x := x * i;
 for i := n - k downto 2 do
 x := x div i;
 F2 := x;
end;
28

Tentukanlah berapa banyak tanda bintang dihasilkan sebagai output jika fungsi F4(n) dijalankan. (notasikan jawaban anda dalam n)

procedure F4(n : integer);
begin
 if n = 1 then
 write('*')
 else
 begin
 write('*');
 F4(n - 1);
 write('*');
 end;
end;

Deskripsi untuk soal nomor 29 - 30

Perhatikan fungsi berikut:

function F5(n : integer) : integer;
begin
 if (n = 1) or (n = 2) then
 F5 := 1
 else
 F5 := F5(n - 1) + F5(n - 2);
end;
29

Berapa kalikah F5(4) dieksekusi pada pengeksekusian F5(8)?

30

Berapa kalikah F5(n-k) dieksekusi pada pengeksekusian F5(n) (dengan n>k>2, notasikan jawaban anda dalam F5, n dan k)?

31

Jika a dan b memiliki nilai kebenaran yang sama maka outputnya adalah ...

if not((not a and b) or (a and not b)) then
 writeln('merah')
else
 writeln('putih');
32

Jika nilai yang mungkin baik untuk a, b, maupun c adalah salah satu bilangan bulat yang berkisar antara {1,2,3,4} berapakah nilai maksimum d yang mungkin?

if a > b then
 if b < c then
 b := a + 2 * c
 else
 c := b + 2 * c
else
 a := b + c;
d := a + b + c;

Deskripsi untuk soal nomor 33 - 34

Perhatikan potongan program berikut

//inisiasi semua T[..] sebagai true
for i := 2 to max do
begin
 if (T[i]) then
 begin
 writeln(i);
 j := i;
 while (j*i <= max) do
 begin
 ... // perintah yang hilang
 j := j + 1;
 end;
 end;
end;
33

Agar algoritma tersebut dapat menampilkan semua bilangan prima 2,3,5,7,… dan seterusnya hingga nilai max, perintah apa yang harus dituliskan di bagian … //perintah yang hilang? (hint : perintah hanya terdiri dari 1 statement).

34

Mengacu pada potongan algoritma di atas. Bila max bernilai 100, berapa kali perintah writeln(i) dieksekusi?

Deskripsi untuk soal nomor 35 - 36

Perhatikan potongan program berikut

function campur(n : integer) : integer;
begin
 campur := n * n;
end;
function aduk(x,y,z : integer) : integer;
begin
 if (y = 0) then
 aduk := 1
 else if (y mod 2 = 0) then
 aduk := campur(aduk(x,y div 2,z)) mod z
 else
 aduk := ( (x mod z) * aduk(x,y-1,z) ) mod z;
end;
var
 a,b,c : integer;
begin
 readln(a,b,c);
 writeln(aduk(a,b,c));
end.
35

Jika program dijalankan dan pengguna memasukkan angka 2, 10, dan 10, berapakah angka yang dikeluarkan program?

36

Jika program dijalankan dan pengguna memasukkan angka 4, 40, dan 5, berapakah angka yang dikeluarkan program?

Deskripsi untuk soal nomor 37 - 39

Perhatikan potongan program berikut

function g(a,b : integer) : integer;
begin
 if (b = 0) then
 g := // kosong
 else
 g := // kosong
end;
function h(a,b : integer) : integer;
begin
 h := // kosong
end;
37

Isilah bagian kosong di baris 4 dengan tepat.

38

Isilah bagian kosong di baris 6 dengan tepat.

39

Isilah bagian kosong di baris 11 dengan tepat.

40

Perhatikan potongan program berikut ini:

var m,i,a,b,c,d:longint;
begin
 readln(m);
 a:=1;b:=1;c:=1;
 for i:=4 to m do
 begin
 d:=a+b+c;
 a:=b;
 b:=c;
 c:=d;
 end;
 writeln(c);
end.

Bila user memasukkan input 8, maka berapakah outputnya?

Deskripsi untuk soal nomor 41 - 42

Perhatikan potongan program berikut

function xxx(x:longint):longint;
begin
 xxx:=x*x;
end;

function xyz(x,y:longint):longint;
begin
 if(y = 1)then
 xyz:=x
 else if ((y mod 2) = 0) then
 xyz:=xxx(xyz(x, y div 2))
 else
 xyz:=x*xyz(x,y-1);
end;
41

Untuk pemanggilan xyz(2,12) akan menghasilkan nilai berapa?

42

Jika fungsi xyz dipanggil dengan nilai argumen y=100, berapa kalikah fungsi xyz ini akan dieksekusi?

Deskripsi untuk soal nomor 43 - 44

Perhatikan potongan program berikut

a:=2;
b:=3;
for i:=p to q do
begin
 b:=i*(a+b);
end;
43

Apabila rumus pada baris ke-5 program di atas diubah menjadi b:=a*(a+b) dan nilai b setelah program dijalankan adalah 108, maka berapa nilai q-p?

44

Apabila diketahui p=3 dan nilai b setelah program dijalankan adalah 350, maka berapa nilai q pada saat inisialisasi?

Deskripsi untuk soal nomor 45 - 48

Perhatikan potongan program berikut

function func(x:integer):integer;
var
 i : integer;
 b : boolean;
begin
 b:= true;
 i := 1;
 while b=true do
 begin
 if (x mod i) <> 0 then
 begin
 func := i;
 b:=false;
 end;
 inc(i);
 end;
end;
45

Tentukan nilai dari func(4620).

46

Tentukan nilai x positif terkecil di mana func(x) = 11.

47

Tentukan bilangan x positif terkecil ke-11 di mana func(x) = 11.

48

Dengan mengasumsikan tipe integer adalah tipe bilangan bulat yang tidak memiliki batasan, berikan sepuluh nilai x positif terkecil di mana tidak ada angka positif y sehingga func(y) = x.

Deskripsi untuk soal nomor 49 - 50

Perhatikan potongan program berikut

var
 i,j:longint;
begin
for j:=1 to 15 do
 for i:=1 to 16-j do
 if (i mod j=0) then writeln(‘*’);
end.
49

Jika program di atas dijalankan, maka banyaknya bintang yang akan ditampilkan ke layar adalah ...

50

Jika ’16-j’ diubah menjadi 16, maka banyaknya bintang yang akan ditampilkan ke layar adalah ...