Olimpiade Sains Provinsi (OSP) 2013 - Komputer

1

Gnegus berhasil menangkap 100 ekor tikus yang selalu mencuri makanannya. Karena dia kesal, dia bergumam "I want to play a game". Tikus-tikus tersebut diletakkan di dalam satu kotak, tanpa diberikan makanan. Karena tikus-tikus tersebut sangat lapar, mereka mulai memakan sesamanya. Seekor tikus akan memakan seekor tikus setiap minggu untuk bertahan hidup. Bila seekor tikus tidak bisa makan seekor tikus yang lain, maka tikus tersebut akan mati. Tikus yang masih hidup setelah 5 minggu berlalu sejak Gnegus meletakkan tikus-tikus tersebut di dalam kotak berjumlah...

2

Terdapat 8 buah jeruk dan 3 buah apel. Buah-buah tersebut akan diletakkan pada suatu garis lurus. Tetapi 2 apel tidak boleh bersebelahan satu sama lain. Banyak kemungkinan meletakkan buah-buah tersebut adalah...

Deskripsi untuk soal nomor 3 - 5

PT. TOKI, sebuah perusahaan manufaktur prosesor komputer, membuat 2 macam prosesor untuk dijual. Masing-masing prosesor dibuat melalui 2 tahap dengan menggunakan mesin tahap 1 dan mesin tahap 2. Detil kebutuhannya adalah seperti berikut:

  • Memproduksi 1 prosesor A membutuhkan 50gr Silikon, 70gr Besi, dan 7 jam.

  • Prosesor yang bisa mendapatkan profit hanyalah yang sudah jadi secara keseluruhan.
3

Jika tidak ada batas waktu untuk memproduksi barang tapi hanya memiliki 4670gr Silikon dan 5950gr Besi, maka profit (keuntungan) maksimum yang bisa didapat dengan membuat hanya produk A adalah sebesar Rp ...

4

Jika Mesin 1 memiliki batas waktu 49 jam sebelum akhirnya rusak, maka profit maksimum yang bisa didapat adalah sebesar Rp...

5

Pak Dengklek, Sang Bos, menginginkan keuntungan setidaknya Rp 3.393.000 dan meminimalkan penggunaan silikon. Banyak silikon minimum yang dibutuhkan untuk memenuhi keinginan Pak Dengklek tersebut adalah ... gram

6

Terdapat sebuah segitiga sama sisi seperti gambar di samping. N buah titik hendak diletakkan di dalam segitiga. Maka N maksimum yang mungkin jika tidak ada 2 titik yang berjarak kurang dari sama dengan x adalah …...

7

Terdapat denah perumahan sebagai berikut:

Garis merupakan jalan, sedangkan angka merupakan nomor rumah. Penduduk di perumahan tersebut suka memberi hadiah kepada tetangga spesialnya. Tetangga spesial adalah nomor rumah yang terdapat di seberang jalan yang memisahkan keduanya dan lebih dekat ke rumah pak RT dibanding dengan dirinya. Rumah Pak RT adalah rumah bernomor 1. Contoh: tetangga spesial dari 28 adalah 11, tetangga spesial dari 16 adalah 5, tetangga spesial dari 18 adalah 5. Tentu saja tidak semua rumah memiliki tetangga spesial, contohnya rumah nomor 1, 3, 17, dll. Siapakah tetangga spesial dari 99?

8

Terdapat kurs mata uang di planet Bebek sebagai berikut:

  • 1 dolar A = 2 dolar B

  • 1 dolar A = 1.8 dolar C

  • 1 dolar A = 2.5 dolar D

  • 1 dolar B = 0.5 dolar C

  • 1 dolar B = 1.3 dolar D

  • 1 dolar C = 1.5 dolar D

Bemi ingin menukarkan 1000 dolar A ke dolar D. Berapa uang maksimal hasil penukaran uang yang dapat diperoleh Bemi?

9

Empat pasang suami istri sedang mengadakan pesta. Diantaranya adalah Adam, Budi, Chandra, Dani, Enni, Fitri, Gina, dan Hanny. Mereka kemudian dipasangkan menjadi 4 pasang untuk mengadakan permainan catur.

  • Budi vs Enni

  • Adam vs istrinya Chandra

  • Fitri vs suaminya Gina

  • Dani vs istrinya Adam

  • Gina vs suaminya Enni

Catatan: Adam, Budi, Chandra, Dani adalah laki-laki dan Enni, Fitri, Gina, Hanny adalah wanita. Dalam setiap pasang suami istri, sang suami pasti laki-laki dan sang istri pasti wanita.

Dengan demikian, istri Budi adalah ...

10

Besok, Raja Dengklek akan mengadakan pesta yang sangat besar. Raja Dengklek telah memesan 2013 botol anggur untuk pestanya tersebut. Namun berdasarkan laporan, salah satu dari botol anggur tersebut telah diberi racun. Racun ini diketahui tidak akan menunjukkan tanda-tanda keracunan sampai orang yang meminumnya mati. Kematian terjadi antara 13-20 jam setelah racun terminum, walaupun hanya terminum setetes. Raja Dengklek memiliki 2013 orang tahanan yang rencananya akan dieksekusi. Raja Dengklek harus berhasil menemukan botol anggur yang mengandung racun tersebut dalam waktu 24 jam. Berapa minimal banyaknya tahanan yang harus minum dari botol-botol anggur yang ada untuk memastikan botol mana yang mengandung racun?

Deskripsi untuk soal nomor 11 - 13

Pada grid 4 x 4 di atas, akan diletakkan N buah koin, di mana tiap kotak dapat menampung maksimal satu koin. Untuk tiap baris, atau kolom, atau diagonal dengan dua buah kotak atau lebih (yang diberi garis panah di atas), jika terdapat sejumlah genap koin pada garis tersebut, maka Anda akan mendapatkan satu poin (Ingat bahwa nol adalah genap). Total poin adalah jumlah dari semua poin pada semua garis. Sebagai contoh, jika N = 4, konfigurasi berikut mendapatkan total poin 14 (garis tebal menunjukkan garis tersebut mendapatkan satu poin)

11

Jika N = 8, maka maksimal total poin yang dapat diperoleh adalah...

12

Jika N = 9, maka maksimal total poin yang dapat diperoleh adalah...

13

Jika N = 10, maka maksimal total poin yang dapat diperoleh adalah...

Deskripsi untuk soal nomor 14 - 15

Enam musisi bernama Ali, Berty, Cakra, Denis, Eric, dan Felik, akan memainkan tiga buah lagu dalam sebuah konser. Tiap lagu membutuhkan dua biola, sebuah cello, dan sebuah piano. Tentu saja tiap orang harus bermain dalam minimal satu lagu, dan tiap orang hanya bisa memainkan satu instrumen dalam tiap lagu (jika dia bermain di lagu itu). Karena takut performanya berkurang, jika seseorang memainkan dua lagu berurutan, maka instrumen yang dimainkan dalam kedua lagu tersebut tidak boleh sama.

  • Ali hanya bisa bermain biola, dan harus memainkan lagu pertama;

  • Berty dan Eric keduanya dapat bermain biola dan piano;

  • Cakra dapat bermain biola dan cello;

  • Denis hanya dapat bermain cello;

  • sedangkan Felik hanya dapat bermain piano.
14

Dari keenam musisi tersebut, siapa sajakah yang tidak dapat bermain di lagu kedua?

15

X ternyata tidak bisa bermain di konser karena tangannya terjepit pintu. Ternyata kelima musisi sisanya tetap dapat menjalankan konser sesuai syarat-syarat di atas. Siapakah X?

16

Bayu memiliki koin uang 200, 300, 500, dan 700 yang sangat banyak. Ia berniat untuk membeli buku pemrograman seharga 2000. Karena koin uang tersebut cukup berat apabila ditaruh dalam kantung celana, ia hanya ingin membawa uang seminimal mungkin. Untuk itu, koin yang seharusnya ia bawa sebanyak ... keping.

17

Perhatikan aturan-aturan berikut ini:

  • 1<x,y,z<9

  • x3 bilangan ganjil

  • x(x+1) > 20

  • y3 bilangan genap

  • x*y < 50

  • z bilangan genap

  • x+y+z<17

Berapakah nilai x*(y+z) maksimal yang bisa dibentuk?

18

Pak Dengklek sedang mengajari bebek-bebeknya menulis huruf. Ia meminta bebek-bebeknya bergantian memilih 26 huruf (a sampai dengan z) dan menuliskannya di papan tulis yang disediakan. Pak Dengklek akan mengakhiri sesi belajar menulis ini apabila 26 huruf tersebut minimal masingmasing sudah dituliskan sebanyak 10 kali. Selain itu, ia membuat aturan bahwa, apabila sebuah huruf sudah dituliskan sebanyak 26 kali, maka bebek selanjutnya yang hendak menuliskan huruf tersebut harus memilih huruf yang lain yang belum dituliskan sebanyak 26 kali. Berapakah paling banyak huruf yang bisa dituliskan bebek-bebek Pak Dengklek sebelum sesi belajar menulis berakhir?

19

Andi setiap hari pergi ke sekolah menggunakan sepeda dengan kecepatan a km/jam. Namun, di daerah tersebut terdapat angin yang berhembus terus menerus dari arah rumah ke sekolah dengan kecepatan b km/jam. Angin ini mempengaruhi kecepatan sepeda yang dikayuh oleh Andi dengan aturan

  • Bila berjalan searah angin maka kecepatan menjadi a + b km/jam

  • Bila berjalan berlawanan dengan angin maka kecepatan menjadi a-b km/jam.

Ia membutuhkan waktu 3 jam untuk berangkat dari rumah ke sekolah, sedangkan dalam perjalanan pulang ia membutuhkan waktu 4 jam. Apabila tidak ada angin yang berhembus, maka berapa jam yang dibutuhkan untuk menempuh perjalanan dari rumah ke sekolah?

20

Sebuah kotak berisi 6 bola merah dan 5 bola kuning. Budi, lalu Andi, dan kemudian Didi mengambil masing-masing satu bola secara berurutan. Berapa kemungkinan bola yang diambil Andi berwarna sama dengan salah satu atau kedua bola yang diambil oleh dua orang lainnya?

21

Shintia memiliki 5 botol air berukuran 61 ml, 25 ml, 13 ml, 7 ml dan 3 ml. Awalnya ia memiliki X ml air di baskom dan hendak mendapatkan Y ml air dengan cara menakar air (penakaran harus bulat) tersebut ke botol-botol dan tidak boleh ada air tersisa di baskom. Contoh: pada baskom terdapat 10 ml air dan ia hendak mendapatkan 3 ml air. Pertama 10 ml tersebut akan dituangkan ke dalam botol berkapasitas 13 ml, lalu akan dituangkan 3 ml air ke botol yang berkapasitas 3 ml sampai full dan akhirnya ia mendapatkan 3 ml air (2 penuangan) dan tersisa 7 ml air pada botol berkapasitas 13 ml. Sekarang ia memiliki 31 ml air di baskom dan hendak mendapatkan 6 ml air. Jika total penuangan yang dilakukan tidak lebih dari 5 kali dan harus ada air dalam tiap botol, berapakah ml jumlah air pada dua botol dengan air tersedikit pada akhir penuangan? (catatan : penuangan dilakukan sampai botol yang dituangkan air penuh atau isi botol/baskom yang menuangkan air sudah habis)

Deskripsi untuk soal nomor 22 - 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?

24

Dalam sebuah turnamen, setiap orang akan berlomba dengan semua peserta lain tepat satu kali. Dalam turnamen tersebut 3 orang mengundurkan diri setelah menjalani 2, 4, dan 6 perlombaan. Diketahui sepanjang turnamen telah diadakan 103 perlombaan, berapa orang yang berpartisipasi pada awal turnamen tersebut?

25

Ada berapa himpunan bagian dari {1,2,...,9} sedemikian sehingga tidak ada 2 anggota yang berurutan? (misal himpunan {1,4,5} dilarang karena memiliki dua anggota 4 dan 5, sementara 4 dan 5 adalah 2 bilangan yang berurutan, sedangkan himpunan {2,4,8} boleh)

26

Perhatikan potongan program berikut!

var N,hasil: integer;
procedure solve(X:integer);
begin
if (X>1) then
begin
hasil:=hasil+1;
solve(X div 2 + X mod 2);
end;
end;
begin
readln(N);
hasil:=0;
solve(N);
writeln(hasil);
end.

Bila diberi masukan bilangan 77, maka program akan memberikan keluaran

27

Perhatikan potongan program di bawah ini!

base := ‘QWERTYUIOPLKJHGFDSAZXCVBNM’;
kata := ‘’;
readln(kalimat);
for i:= length(kalimat) downto 1 do
begin
if pos(kalimat[i], base) > 0 then
kata:= kata & kalimat[i];
end;
writeln(kata);

Fungsi pos (CC:char, str:string) adalah fungsi yang akan menghasilkan posisi CC di suatu string str, jika suatu CC tidak terdapat di string, fungsi pos akan menghasilkan 0. Operator & adalah sebuah operator untuk menambahkan sebuah karakter di akhir sebuah string. Jika program di atas diberi masukan ‘s4yA-BuK4N+oRanG aLaY!?’, maka keluarannya adalah

28

Perhatikan potongan program berikut!

function kibo(n: integer):integer;
begin
 if (n = 2) or (n = 1) or (n = 0) then kibo := n
 else kibo := kibo(n-1) + kibo(n-3);
end;

Berapa kalikah kibo(3) dipanggil saat pemanggilan kibo(7) ?

29

Perhatikan potongan program berikut!

var
 we: longint;
 Z: array[1..15] of longint = (64, 19, 56, 67, 66, 82,
31, 20, 67, 10, 94, 100, 57, 14, 86);
function f(x: longint; y: longint): longint;
var
 a, b: longint;
begin
 if (x = y) then
 f := Z[y]
 else begin
 a := f(x, (x+y) div 2);
 b := f((x+y) div 2+1, y);
 if (a < b) then f := a
 else f := b
 end
end;
begin
 we := f(3,11);
 writeln(we);
end.

Apakah keluaran dari program tersebut?

Deskripsi untuk soal nomor 30 - 31

Perhatikan potongan program berikut!

var
 s:string;
 cl,cr:integer;

procedure right(l, r : integer);
forward;

procedure swap(l, r : integer);
var
 c : char;
begin
 if (l>=1) and (r<=length(s)) then
 begin
 c:=s[l];
 s[l]:=s[r];
 s[r]:=c;
 end;
end;

procedure left(l, r : integer);
begin
 inc(cl);
 swap(l,r);
 if (r<length(s)) then
 right(l,r+1);
end;

procedure right(l, r : integer);
begin
 inc(cr);
 swap(l,r);
 if (l>1) then
 left(l-1,r);
end;

begin
 s:='gogetgold';
 left(9,1);
 writeln(s);
 writeln(cl,',',cr);
end.
30

Apakah yang akan tercetak dari hasil pemanggilan perintah writeln(cl,',',cr)?

31

Jika perintah left(9,1) diganti dengan left(5,5), apakah yang akan tercetak dari hasil pemanggilan perintah writeln(s)?

Deskripsi untuk soal nomor 32 - 33

Perhatikan potongan program berikut!

procedure tulis(n,m:integer);
var
i,j,k:integer;
begin
for i:=1 to n do
begin
for j:=1 to (n div m) do
for k:=1 to m do
writeln('*');
for j:=1 to (n mod m) do
writeln('-');
end;
end;
32

Bila kita memanggil prosedur tulis(30,30), berapakah jumlah ‘*’ yang tertulis?

33

Bila kita memanggil prosedur tulis(n,m), berapakah jumlah simbol ('*' maupun '-') yang tertulis? {tuliskan/nyatakan dalam m atau n}

34

Perhatikan potongan program di bawah ini!

var
 T:array[1..13] of integer = (32, 6, 12, 64, 68, 100,
214, 120, 30, 80, 24, 22, 88);
function q(c,d:integer):integer;
var
 e:integer;
begin
 if (d=0) then q:=c else
 begin
 e:=c mod d;
 q:=q(d,e);
 end;
end;
function p(a,b:integer):integer;
var
 i:integer;
begin
 p:=T[a];
 for i:=a to b do
 begin
 p:=q(p,T[i]);
 end
end;
begin
 writeln(p(1,13));
end.

Berapakah output dari program di atas?

35

Jika a[] adalah array berindex 0..9 dengan isi {1,-1,-2,-1,-1,1,-1,2,-1,3}, maka berapakah nilai tot di akhir program?

Deskripsi untuk soal nomor 36 - 37

Perhatikan potongan program berikut!

function hap(x,t: integer): integer;
begin
 if t = 1 then
hap := x mod 5
 else
hap := 5*x;
end;
function hip(x,y: integer): integer;
begin
 if x < y then
hip := hip(y,x)
 else
hip := hap(x,1) + hap(y,2);
end;
function hop(x,y,z: integer): integer;
begin
 if y > z then
hop := hop(x,z,y)
 else if x > y then
hop := hop(y,x,z)
 else
hop := hip(x,y) + z;
end;
36

Apakah output dari pemanggilan writeln(hop(18, 3, 1993)) ?

37

Apakah output dari pemanggilan writeln(hip(hop(201,320,12), hop(20,1120,10)) + hap(21,30)) ?

38

Diberikan potongan program berikut ini:

program hahaha;
var
 n, i, j, hehe : integer;
 a, hoho : array [0..1000] of integer;
begin
 read(n);
 for i := 1 to n do read(a[i]);
 for i := 1 to n do hoho[i] := 1;
 for i := 1 to n do
 for j := 1 to i-1 do
 if (a[j] < a[i]) and (hoho[j] + 1 > hoho[i]) then
 hoho[i] := hoho[j] + 1;
 hehe := 0;
 for i := 1 to n do
 if (hoho[i] > hehe) then hehe := hoho[i];
 write(hehe);
end.

Berapakah nilai keluaran dari program tersebut, jika diberi masukan sebagai berikut?

10

4 1 6 2 8 3 0 7 9 5

39

Perhatikan potongan program di bawah ini!

for i:=1 to n do
begin
for k:=i to n-1 do write(' ');
for j:=1 to (2*i-1) do
if (i=n) or (i mod 2=1) then write('*')
else if j mod 2=1 then write('*')
else write('0');
writeln;
end;
for l:=n downto 2 do
begin
for m:=l to n do write(' ');
for o:=(2*l-1) downto 3 do
if o mod 2=1 then write('*')
else write('0');
writeln;
end;

Apabila diberi masukan n=7, maka berapakah banyaknya ‘*’ yang dicetak pada layar?

Deskripsi untuk soal nomor 40 - 41

Perhatikan potongan program berikut!

function mencari(N:integer):integer;
var i,j,z:integer;
begin
 mencari:=0;
 for i:=1 to N do
 begin
 j:=1;
 z:=0;
 while (j <= i) do
 begin
 if (i mod j = 0) then inc(z);
 inc(j);
 end;
if (z mod 2 <> 0) then
mencari:=mencari+1;
 end;
end;
40

Berapakah nilai yang dihasilkan dari pemanggilan mencari(50)?

41

Berapakah nilai yang dihasilkan dari pemanggilan mencari(9000)?

42

Perhatikan potongan program di bawah ini!

var
data1 : array[1..10] of integer =
(3,9,2,2,1,5,7,5,5,8);
data2,data3 : array[1..10] of integer;
i : integer;
begin
for i:= 1 to 10 do
data2[i] := 0;
for i:= 1 to 10 do
inc(data2[data1[i]]);
for i:= 2 to 10 do
data2[i] := data2[i] + data2[i-1];
for i:= 10 downto 1 do
begin
data3[data2[data1[i]]] := data1[i];
dec(data2[data1[i]]);
end;
for i:= 1 to 10 do
write(data3[i]);
end.

Keluaran dari program di atas adalah ....

43

Perhatikan potongan program di bawah ini!

var i,j,x: integer;
begin
 x := 0;
 for i:=1 to 5 do begin
 for j:= 5 downto 1 do begin
x := x + i + j;
 end;
 end;
 writeln(x);
end.

Apakah keluaran dari program di atas?

Deskripsi untuk soal nomor 44 - 45

Perhatikan potongan program berikut!

var x,y:integer;
procedure abc(a:integer;var b:integer);
var c:integer;
begin
 if not((a=0)or(b=0)) then
 if (a>b) then
 begin
 a:=a mod b;
 abc(b,a);
 end
 else
 begin
 b:=b mod a;
 abc(a,b);
 end;
 write(a,' ');
end;
begin
 x:=219; y:=168;
abc(x,y);
end.
44

Apa keluaran yang dihasilkan dari program tersebut?

45

Jika perintah write(a,' '); diubah menjadi write(b,' '); maka keluaran yang dihasilkan menjadi?

46

Perhatikan program di bawah ini

var sum, i, j, n, c : integer;
begin
 readln(n);
 sum := 0;
 for i := 2 to n do
 begin
 c := 0;
 j := i;
 while (j > 0) do
 begin
 if (j mod 2 = 1) then c := c + 1;
 j := j div 2;
 end;
 if (c = 1) then sum := sum + 1;
 end;
 writeln(sum);
end.

Jika potongan program dijalankan dengan masukan n = 2013, maka program akan menuliskan keluaran...

47

Perhatikan potongan program di bawah ini!

procedure f(x: longint; y: longint; z: longint);
 begin
 if (y = 0) then
 writeln(z)
 else
 begin
 if (y mod 2 = 1) then
 z := z + x;
 f(2*x, y div 2, z)
 end;
 end;

Berapakah bilangan yang tercetak dilayar jika dilakukan pemanggilan f(15,97,0)?

Deskripsi untuk soal nomor 48 - 49

Perhatikan potongan program berikut!

function flop(a,b:longint):longint;
forward;

function flip(a,b:longint):longint;
begin
 if (a = 0) then
 flip:=0
 else
 flip:=a+flop(a-1,b);
end;

function flop(a,b:longint):longint;
begin
 if (b = 0) then
 flop:=0
 else
 flop:=b+flip(a,b-1);
end;
48

Berapakah nilai yang dihasilkan dari pemanggilan fungsi flip(4,7)?

49

Berapakah nilai yang dihasilkan dari pemanggilan fungsi flop(100,200)?

50

Misalkan terdapat sebuah array bernama a berisi N elemen, yang diisi di indeks 0 s.d. N-1.

for i := 0 to N-1 do
begin
 for j := i+1 to N-1 do
 begin
 buffer := a[i];
 a[i] := a[j];
 a[j] := buffer;
 end;
end;

Apa yang dilakukan oleh prosedur itu terhadap array a?