Olimpiade Sains Kota (OSK) 2016 - Komputer , Nomor 22 - 23
Deskripsi untuk soal nomor 22 - 23
Rina sedang bermain dengan string (deretan) huruf. Aturan permainannya adalah sebagai berikut.
Pada satu kali permainan pemain memilih sebuah string. Selanjutnya setiap huruf akan diganti
dengan string tertentu, misalnya setiap huruf A diganti dengan “AB” dan setiap huruf B diganti
dengan “A”. Jika permainan dilakukan lebih dari satu kali, pergantian dilakukan pada hasil
sebelumnya menggunakan aturan pergantian yang sama. Misalkan Rina memilih string "BAABA"
dan bermain 1 kali, maka string itu akan berubah menjadi "AABABAAB". Jika bermain 2 kali, maka
string itu akan berubah menjadi "ABABAABAABABA".
Dengan peraturan A diganti dengan “AB” dan B diganti dengan “A”, berapa panjang string hasil
setelah dilakukan 10 kali permainan dengan string awal adalah “A”?
a. 90
b. 55
c. 144
d. 89
e. 88
Rina melakukan permainan yang sama dengan soal sebelumnya dan dia menemukan secarik kertas
di meja bertuliskan "ABABBBABABBBBBBBBBABABBBABA". Dia ingat bahwa itu adalah string hasil
permainan yang pernah dilakukannya dengan string awal dan peraturan yang berbeda (seperti soal
sebelumnya). Tapi dia lupa string awalnya apa dan peraturannya apa, yang hanya dia ingat adalah
dia melakukan permainan sebanyak 3 kali. Rina meminta kalian mencari string awal dan peraturan
penggantian untuk menghasilkan string yang ditemukan di meja tersebut!
a. string awal: “B”, peraturan: (A diganti dengan “AAA”, B diganti dengan “BAB”)
b. string awal: “ABA”, peraturan: (A diganti dengan “BAB”, B diganti dengan “ABA”)
c. string awal: “BA”, peraturan: (A diganti dengan “BA”, B diganti dengan “AB”)
d. string awal: “AB”, peraturan: (A diganti dengan “BA”, B diganti dengan “AB”)
e. string awal: “A”, peraturan: (A diganti dengan “ABA”, B diganti dengan “BBB”)
