alpsahin/tubitak-olimpiyat-dataset-v2 huggingface dataset:
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 17

## [15-17] Sorular için açıklama
Elemanları tamsayılar olan sıralı ikililerden oluşmuş kümeler düşünelim. Bunlara ilinti diyeceğiz. Örnek olarak, R ve S şu şekilde tanımlanmış iki ilinti olsun:
\[R = \{(4, 2), (1, 3), (1, 2)\}, S = \{(1, 1), (3, 2), (3, 1), (4, 5)\}\]
İkili inti arasında tanımlanan ▲ işlemi, birinci ilintinin bütün ikili işle işle ikinci ilintinin bütün ikili işle işle ikinci ilintini bütün ikili işle işle ikinci ilintini bütün işle işle ikinci ilintini bütün ikinci ilintini bütün ikinci ilintini bütün ikinci ilin bütün ikinci ilin bütün ikinci ilin bütün ikinci işle ikinci ilin bütün ikinci ilin bütün ikinci ilin bütu.
\[R \triangle S = \{(2, 2), (2, 5), (2, 4)\}, (-2, 2), (-1, 2)\}.\]
15. \(R = \{(2, 2), (3, 3), (4, 4)\} \text{ ve } S = \{(4, 3), (3, 2), (2, 1)\} \text{ olduğuna göre } R \triangle S \text{ işleminin sonucu hangisidir?}\)
A) \(\{(0, 1), (0, 3), (0, 5)\}\)
B) \(\{(0, 3), (0, 5), (0, 7)\}\)
C) \(\{(4, 3), (4, 5), (4, 7)\}\)
D) \(\{(6, 1), (6, 3), (6, 5)\}\)
E) Hiçbiri
R kümesindeki eleman toplamları sırasıyla 4, 6, ve 8'dir. S kümesindeki eleman toplamı ise sırasıyla 7, 5 ve 3'tür. O zaman R ve S kümelerdeki elemanları 1'den 3'e numaralandıırsak:
- 1. için sadece 3. eleman ile ikili oluşmaktadır. O da (4-4,3) = (0,3)'tür.
- 2. için 2. ve 3. elemanlarla ikili oluşmaktadır. Yani sırasıyla (0,5) ve (0,3) oluşur.
- 3. için 1., 2. ve 3. elemanlarla ikili oluşmaktadıır. Yani sırasıyla (0,7), (0,5) ve (0,3) oluşur.

---

\(R = \{(1, 4), (4, 2), (5, 8)\} \text{ ve } RNS = \{(−3, 8), (2, 5), (−3, 5)\} \text{ olduğuna göre S aşağıdakilerden hangisi olabilir?}\)

Şıklar:
A) \(S = \{(1, 7), (1, 3)\}\) | B) \(S = \{(1, 7), (0, 5), (1, 3)\}\) | C) \(S = \{(1, 7), (2, 5), (2, 3)\}\) | D) \(S = \{(4, 4), (1, 4)\}\) | E) Hepsi

Cevap: D \(S = \{(4, 4), (1, 4)\}\)

Çözüm:
R kümesindeki eleman toplamı sırasıyla 5 6, ve 13'tür. S kümesinde Elemanları toplamı 5 8 olan iki ikili bulunsun ki çözüm kümesi elde edilsin. 6 sadece 5 ile ikili oluşturacağından elemanlarının farkı 2 olmalı çünkü 2 çözüm kümesinde 1 kez geçiyor. 13 ise 5 ve 8 ile ikili oluşturacağından aynı mantıkla elemanları farkı -3 olur. Toplamı 5 ve 8 olan herhangi ikili kümesi cevap olur. Sadece D şıkkı bu şartı sağlamaktadır.
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 18

## [18-20] Sorular için açıklama
Bir bölgede şehirler ve şehirleri birbirine bağlayan yol ağı bulunmaktadır. Bölge yönetimi, yüksek bakım masrafları nedeniyle, gereksiz yolları ortadan kaldırmaya karar verir. Gereksiz yollar ortadan kaldırıldığında, herhangi bir şehirden diğerine gitmek mümkün olabilecek fakat gidilen bir yolu ikinci kez geçmeden bir şehre tekrar dönmek mümkün olmayacaktır. Bunun bir sonucu olarak, yol sayısı şehir sayısından tam olarak bir az olacaktır. Bölge yönetimi girdi olarak yol ağını kullanarak içinde gereksiz yolların olmadığı haritayı aşağıdaki yöntemi kullanarak oluşturmaktadır. A ve B şehirleri arasındaki yol YAB ve bu yolun uzunluğu DAB ile gösterilmektedir.
1. Herhangi bir şehir seçip başlangıçta boş bir haritaya ekle
2. Bütün şehirler haritaya eklenene kadar aşağıdaki adımları tekrarla
- Öyle haritaya eklenmiş bir şehir U ve haritaya eklenmemiş bir şehir V çifti seç ki DUV minimum olsun
- V şehrini ve YUV yolunu haritaya ekle
Sorular aşağıda verilen yol ağı dikkate alınarak cevaplandırılacaktır. Ağdaki şehirler büyük noktalar, yollar ise düz çizgiler ile gösterilmiştir. Her bir yolun uzunluğu yanında verilen sayıdır.
[GÖRSEL]

---

Haritaya ilk eklenen şehir D olarak seçilirse, hangi yol içinde gereksiz yolların olmadığı haritada yer al-maz?

Şıklar:
A) YDF | B) YEF | C) YBE | D) YCE | E) YEG

Cevap: B YEF

Çözüm:
Eğer ilk eklenen şehir D olursa yöntemimiz sırasıyla şu adımları izler:
- DAD = 5 en küçük olur ve A şehriyle YAD yolu haritaya eklenir.
- DDF = 6 en küçük olur ve F şehriyle YDF yolu haritaya eklenir. A şıkkı elenir.
- DAB = 7 en küçük olur ve B şehriyle YAB yolu haritaya eklenir.
- DBE = 7 en küçük olur ve E şehriyle YBE yolu haritaya eklenir. C şıkkı elenir
- DCE = 5 en küçük olur ve C şehriyle YCE yolu haritaya eklenir. D şıkkı elenir.
- DEG = 9 en küçük olur ve G şehriyle YEG yolu haritaya eklenir. E şıkkı elenir.
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 19

## [18-20] Sorular için açıklama
Bir bölgede şehirler ve şehirleri birbirine bağlayan yol ağı bulunmaktadır. Bölge yönetimi, yüksek bakım masrafları nedeniyle, gereksiz yolları ortadan kaldırmaya karar verir. Gereksiz yollar ortadan kaldırıldığında, herhangi bir şehirden diğerine gitmek mümkün olabilecek fakat gidilen bir yolu ikinci kez geçmeden bir şehre tekrar dönmek mümkün olmayacaktır. Bunun bir sonucu olarak, yol sayısı şehir sayısından tam olarak bir az olacaktır. Bölge yönetimi girdi olarak yol ağını kullanarak içinde gereksiz yolların olmadığı haritayı aşağıdaki yöntemi kullanarak oluşturmaktadır. A ve B şehirleri arasındaki yol YAB ve bu yolun uzunluğu DAB ile gösterilmektedir.
1. Herhangi bir şehir seçip başlangıçta boş bir haritaya ekle
2. Bütün şehirler haritaya eklenene kadar aşağıdaki adımları tekrarla
- Öyle haritaya eklenmiş bir şehir U ve haritaya eklenmemiş bir şehir V çifti seç ki DUV minimum olsun
- V şehrini ve YUV yolunu haritaya ekle
Sorular aşağıda verilen yol ağı dikkate alınarak cevaplandırılacaktır. Ağdaki şehirler büyük noktalar, yollar ise düz çizgiler ile gösterilmiştir. Her bir yolun uzunluğu yanında verilen sayıdır.
[GÖRSEL]

---

Haritaya ilk eklenen şehir E olarak seçilirse, haritaya eklenen dördüncü şehir hangisidir?

Şıklar:
A) A | B) B | C) C | D) F | E) G

Cevap: A A

Çözüm:
Eğer ilk eklenen şehir E olursa yöntemimiz sırasıyla şu adımları izler:
- \(D_{EC} = 5\) en küçük olur ve \(C\) şehriyle \(Y_{EC}\) yolu haritaya eklenir.
- \(D_{EB} = 7\) en küçük olur ve \(B\) şehriyle \(Y_{EB}\) yolu haritaya eklenir.
- \(D_{BA} = 7\) en küçük olur ve \(A\) şehriyle \(Y_{BA}\) yolu haritaya eklenir.
Yani haritaya sırasıyla \(E, C, B\) ve \(A\) şehirleri eklenmiş olur.
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 20

## [18-20] Sorular için açıklama
Bir bölgede şehirler ve şehirleri birbirine bağlayan yol ağı bulunmaktadır. Bölge yönetimi, yüksek bakım masrafları nedeniyle, gereksiz yolları ortadan kaldırmaya karar verir. Gereksiz yollar ortadan kaldırıldığında, herhangi bir şehirden diğerine gitmek mümkün olabilecek fakat gidilen bir yolu ikinci kez geçmeden bir şehre tekrar dönmek mümkün olmayacaktır. Bunun bir sonucu olarak, yol sayısı şehir sayısından tam olarak bir az olacaktır. Bölge yönetimi girdi olarak yol ağını kullanarak içinde gereksiz yolların olmadığı haritayı aşağıdaki yöntemi kullanarak oluşturmaktadır. A ve B şehirleri arasındaki yol YAB ve bu yolun uzunluğu DAB ile gösterilmektedir.
1. Herhangi bir şehir seçip başlangıçta boş bir haritaya ekle
2. Bütün şehirler haritaya eklenene kadar aşağıdaki adımları tekrarla
- Öyle haritaya eklenmiş bir şehir U ve haritaya eklenmemiş bir şehir V çifti seç ki DUV minimum olsun
- V şehrini ve YUV yolunu haritaya ekle
Sorular aşağıda verilen yol ağı dikkate alınarak cevaplandırılacaktır. Ağdaki şehirler büyük noktalar, yollar ise düz çizgiler ile gösterilmiştir. Her bir yolun uzunluğu yanında verilen sayıdır.
[GÖRSEL]

---

Haritaya ilk eklenen şehir A olarak seçilirse, haritaya en son eklenen yol hangisidir?

Şıklar:
A) \(Y_{DE}\) | B) \(Y_{DF}\) | C) \(Y_{EF}\) | D) \(Y_{EG}\) | E) \(Y_{FG}\)

Cevap: D \(Y_{EG}\)

Çözüm:
Eğer ilk eklenen şehir A olursa yöntemimiz sırasıyla şu adımları İzler:
- \(D_{AD} = 5\) en küçük olur ve \(D\) şehriyle \(Y_{EC}\) yolu haritaya eklenir.
## AÇIKLAMA
Öncelikle şu gözlemi yapalım: eğer M(i, j) tanımında 3.madde olmasaydı. M(i, j) = max(i, j) olurdu. Şimdi ise her ortak i, j elemanı için M(i, j) = M(i-1, j-1) olur, yani 1 azalır. O zaman biz soruyu şöyle bir soruya çevirebiliriz: Verilen iki kelimeyle başlıyoruz. 1 maliyetle ikisinden birinin veya ikisinin birden son elemanını silebiliriz ya da iki kelimenin son harfleri aynıysa maliyetsiz ikisini birden silebiliriz. Amacımız en az maliyetle iki kelimeyi de tamamen silmek. En son maliyet bize iki kelime arasındaki mesafeyi verir.
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 21

Birinci kelime testere ile ikinci kelime keser arasındaki mesafe nedir?

Şıklar:
A) 1 | B) 2 | C) 3 | D) 4 | E) 5

Cevap: C 3

Çözüm:
Testere ve keser ile başlayalım ve şu adımları sırasıyla izleyelim:
- tester — keser ... 1 maliyet
- teste — kese ... r harfi ortak, O maliyet
- test — kes ... e harfi ortak, O maliyet
- tes — kes ... 1 maliyet
- te — ke ... s harfi ortak, O maliyet
- t — k ... e harfi ortak, O maliyet

text<|/ref|>
[[77, the text of the image is not legible. The image appears to be a blurry image of text. The text is not legible. The image appears to be a blurry image of text. The text in the image is not legible. The image appears to be a blurry image of text.
En sonunda son iki harf de silinir ve 3 maliyetle kelimeler tamamen silinir. En iyi ihtimal budur.
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 22

Birinci kelime yahoo ile ikinci kelime google arasındaki mesafe nedir?

Şıklar:
A) 4 | B) 5 | C) 6 | D) 7 | E) 8

Cevap: C 6

Çözüm:
yahoo ve google ile başlayalım ve şöyle çevirmeler yapalım:
- yahoo — google → yahoo — goo, 3 maliyet
- yahoo — goo → yah — g, O maliyet
- yah — g → " — ", 3 maliyet
Toplam en az 6 maliyetle kelimeler tamamen silinebilir.
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 23

5 harfli bir birinci kelime ile 7 harfli bir ikinci kelime arasındaki mesafe en fazla kaç olabilir?

Şıklar:
A) 5 | B) 7 | C) 9 | D) 10 | E) 12

Cevap: B 7

Çözüm:
Bütün harflerin farklı olduğu durumda mesafe max(5, 7) = 7 olur.
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 24

5 harfli bir birinci kelime ile 7 harfli bir ikinci kelime arasındaki mesafe en az kaç olabilir?

Şıklar:
A) 7 | B) 5 | C) 0 | D) 1 | E) 2

Cevap: E 2

Çözüm:
İlk 5 harf aynıysa mesafe max(5, 7) - 5 = 2 olur.
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 25

## [25-27] Sorular için açıklama
Görünüşleri aynı fakat ağırlıkları birbirinden farklı 50 tane top ve üç gözlü bir terazi verilmiştir. Üç gözlü terazi ile herhangi üç top **tek bir tartı** ile ağırlık olarak küçükten büyüğe sıralanabilmektedir. Teraziye üçten az veya üçten fazla top konulamamaktadır.

---

En hafif top en az kaç tartı ile kesinlikle bulunabilir?

Şıklar:
A) 49 | B) 18 | C) 17 | D) 25 | E) 50

Cevap: D 25

Çözüm:
Başlangıçta en hafif olma ihtimali olan 50 top vardır. Her bir tartımdan sonra tam olarak 2 tane top bu potansiyeli kaybeder ve 25 tartımın sonunda en hafif olan top kesinlikle bulunur.
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 26

## [25-27] Sorular için açıklama
Görünüşleri aynı fakat ağırlıkları birbirinden farklı 50 tane top ve üç gözlü bir terazi verilmiştir. Üç gözlü terazi ile herhangi üç top **tek bir tartı** ile ağırlık olarak küçükten büyüğe sıralanabilmektedir. Teraziye üçten az veya üçten fazla top konulamamaktadır.

---

En hafif ve en ağır toplar (ikisi beraber) en az kaç tartı ile kesinlikle bulunabilir?

Şıklar:
A) 33 | B) 49 | C) 50 | D) 34 | E) 36

Cevap: A 33

Çözüm:
Başlangıçta en hafif veya en ağır olma ihtimali olan ellişer top vardır. Her tartımda ortadaki top en ağır ve en hafif olma potansiyelini kaybeder. 17 tartıma ile topları en hafif olma potansiyelli en ağır olma potansiyelli ve potansiyelsiz olarak 3 gruba ayıralım. En kötü ihtimalle en ağır veya hafif grubunda 17 tane top olabilir. Grupları kendi içerisinde tartarsak, en ağır 8, en hafifi de 8 tartma ile bulabiliriz. Toplam en iyi 33 tartmada bulabiliriz.
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 27

## [25-27] Sorular için açıklama
Görünüşleri aynı fakat ağırlıkları birbirinden farklı 50 tane top ve üç gözlü bir terazi verilmiştir. Üç gözlü terazi ile herhangi üç top **tek bir tartı** ile ağırlık olarak küçükten büyüğe sıralanabilmektedir. Teraziye üçten az veya üçten fazla top konulamamaktadır.

---

İkinci en hafif top en az kaç tartı ile kesinlikle bulunabilir?

Şıklar:
A) 26 | B) 49 | C) 25 | D) 34 | E) 27

Cevap: E 27

Çözüm:
Herhangi bir üçlüyü tarttığımızda ilkini alalım ve bu topun arkasına ortacayı koyalım. Bir topun arkasında olan ve aralarındaki sıralamayı bilmediğimiz topların sayısına o topun derecesi diyelim. 17 tartma ile derecesi 1 olan 17 top elde ederiz. Herhangi 3 topu tarttığımızda arkasındakileriyle birlikte sonun topu ve orantıca topun arkasındakileri sileriz çünkü onların 2. En hafif olma potansiyeli kalmamıştır. Sonrada orantıca topu ilk topun arkasına ekleyerek derecesini 1 artırırız. Yani derecesi x, y, z olan 3 topu tartarsak en kötü ihtimalle derecesi max(x, y, z)+1 olan 1 top elde ederiz. Yani topların derecelerini inceleyecek olursak:
- en başta 17 tane 1.derece top, 17 işlem
- sonra 5 tane 2., 2 tane 1.dereceden top, 5 işlem
- 2,2,2,2,2,1,1 → 3,3,1 - 2 işlem
- 3,3,1 → 4 - 1 işlem
- 4 → 2 → 1 - 2 işlem (arkasındaki topları kendi arasında tartarız.)
Toplamda en az 17+5+2+1+2=27 işlemde bulabiliriz.
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 28

## [28-31] Sorular için açıklama
X, Y ve Z aşağıda verildiği gibi tanımlanmış karşılıklı özyineli nesnelerdir. Tanımlarda toplam dört farklı (atomik) sembol (a, b, c ve ·) vardır. X, Y ya da Z ile tanımlanamayan tüm nesneler geçersizdir.
\[
\begin{array}{c|c}
\text{X =} & \begin{array}{c|c}
a \cdot a & \text{ya da;} \\
a \cdot X' \cdot a & \text{ya da;} \\
b \cdot Y' \cdot b & \text{ya da;} \\
c \cdot Z' \cdot c & \text{ya da;}
\end{array} \\
\hline
\text{Y =} & \begin{array}{c|c}
b \cdot b & \text{ya da;} \\
X' \cdot a & \text{ya da;} \\
Y' \cdot b & \text{ya da;} \\
Z' \cdot c & \text{ya da;}
\end{array} \\
\hline
\end{array}
\]
İfadelerdeki X' nesnesi X, Y' nesnesi Y, ve Z' nesnesi Z cinsinden başka nesnelerdir. Sırasıyla X, Y ve Z tipinden nesneleri girdi olarak alan f, g ve h fonksiyonları aşağıda tanımlanmıştır. Bu fonksiyonlar karşılık özyineli fonksiyonlar olup yalnız a, b ve c harflerini içeren kelimeler oluştururlar.
\[
\begin{array}{c|c}
f(X) = & \begin{array}{c|c}
aa & \text{eğer X = a} \cdot a \\
aaf(X') & \text{eğer X = a} \cdot X' \cdot a \\
g(Y')bb & \text{eğer X = b} \cdot Y' \cdot b \\
h(Z')c & \text{eğer X = c} \cdot Z' \cdot c
\end{array} \\
\hline
h(Z) = & \begin{array}{c|c}
c & \text{eğer Z = c} \cdot c \\
af(X') & \text{eğer Z = a} \cdot X' \\
bg(Y') & \text{eğer Z = b} \cdot Y' \\
cch(Z') & \text{eğer Z = c} \cdot Z'
\end{array}
\end{array}
\]
## AÇIKLAMA
Her nesnenin yukarıda belirtilen durumlarını yukarıdan aşağı numaralandıralım (X nesnesinin 1.durumu a, 2.durumu b · X' · a ...) ve soruları ona göre çözelim.

---

Hangisi doğrudur?

Şıklar:
A) Tüm X nesnelerinde • sembolü sayısı tek sayıdır | B) Tüm Y nesneleri tek sayıda sembol içerir | C) Sonlu sayıda geçersiz Z nesnesi vardır | D) Tüm X nesneleri bazı Z nesnelerinden daha fazla sembol içerir | E) c • c • c • c • c geçersiz bir Z nesnesidir

Cevap: B Tüm Y nesneleri tek sayıda sembol içerir

Çözüm:
### Şıklara bakalım:
A) Yanlış, X nesnesi Y nesnesini çağırabilir ve Y nesnesinde istenildiği kadar • bulunabilir.
B) Doğru, her nesnenin başlangıç durumunda tek sayıda sembol vardır ve geçişlerde çift sayıda sembol eklendiğinden her nesne tek sayıda sembol içeririr.
C) Yanlış, Z nesnesi 4.durumu ile sınırsız sayıda kendi nesnesinden üretebilir.
D) Yanlış, sonsuz uzunlukta Z nesnesi olduğundan her X nesnesi için kendisinden daha uzun bir Z nesnesi vardır.
E) Yanlış, Z nesnesi 3 kez 4.durumu ve 1 kez 1.durumu kullanarak bu nesneyi üretebilir.
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 29

## [28-31] Sorular için açıklama
X, Y ve Z aşağıda verildiği gibi tanımlanmış karşılıklı özyineli nesnelerdir. Tanımlarda toplam dört farklı (atomik) sembol (a, b, c ve ·) vardır. X, Y ya da Z ile tanımlanamayan tüm nesneler geçersizdir.
\[
\begin{array}{c|c}
\text{X =} & \begin{array}{c|c}
a \cdot a & \text{ya da;} \\
a \cdot X' \cdot a & \text{ya da;} \\
b \cdot Y' \cdot b & \text{ya da;} \\
c \cdot Z' \cdot c & \text{ya da;}
\end{array} \\
\hline
\text{Y =} & \begin{array}{c|c}
b \cdot b & \text{ya da;} \\
X' \cdot a & \text{ya da;} \\
Y' \cdot b & \text{ya da;} \\
Z' \cdot c & \text{ya da;}
\end{array} \\
\hline
\end{array}
\]
İfadelerdeki X' nesnesi X, Y' nesnesi Y, ve Z' nesnesi Z cinsinden başka nesnelerdir. Sırasıyla X, Y ve Z tipinden nesneleri girdi olarak alan f, g ve h fonksiyonları aşağıda tanımlanmıştır. Bu fonksiyonlar karşılık özyineli fonksiyonlar olup yalnız a, b ve c harflerini içeren kelimeler oluştururlar.
\[
\begin{array}{c|c}
f(X) = & \begin{array}{c|c}
aa & \text{eğer X = a} \cdot a \\
aaf(X') & \text{eğer X = a} \cdot X' \cdot a \\
g(Y')bb & \text{eğer X = b} \cdot Y' \cdot b \\
h(Z')c & \text{eğer X = c} \cdot Z' \cdot c
\end{array} \\
\hline
h(Z) = & \begin{array}{c|c}
c & \text{eğer Z = c} \cdot c \\
af(X') & \text{eğer Z = a} \cdot X' \\
bg(Y') & \text{eğer Z = b} \cdot Y' \\
cch(Z') & \text{eğer Z = c} \cdot Z'
\end{array}
\end{array}
\]
## AÇIKLAMA
Her nesnenin yukarıda belirtilen durumlarını yukarıdan aşağı numaralandıralım (X nesnesinin 1.durumu a, 2.durumu b · X' · a ...) ve soruları ona göre çözelim.

---

Hangisi hem X hem de Y nesnesidir?

Şıklar:
A) b • b • b | B) a • a • a • a • a • a | C) c • b • a • a | D) c • b • b • b • c | E) a • b • b • b • b • b • a

Cevap: D c • b • b • b • c

Çözüm:
Şıklara bakalım:
A) 3 tane harf içeren X nesnesi olamaz.
B) Y nesnesi olabilmesi için 5 tane a içeren X nesnesi olmalıdır (2.durum) ki sadece a içeren X nesneleri çift  
sayısı a içerir.
C) X nesnelerinin ilk ve son harfi aynıdır.
D) c  •  b  •  b  •  b  •  c bir X nesnesi olması için b  •  b  •  b’nin Y nesnesi (X-4.durum), yani b  •  b ‘nin Y nesnesi  
(Y-3.durum) olması gerekir. Yani bu bir X nesnesidir. Y nesnesi olması içinse sırasıyla  
Y = c  •  b  •  b  •  b  •  c, Z = c  •  b  •  b  •  b, Z = b  •  b  •  b, Y = b  • b olması gerekir.
E) X için X = a  •  b  •  b  •  b  •  b  •  b  • a, X = b  •  b  •  b  •  b  •  b, Y = b  •  b  •  b, Y = b  •  b gerekir.       
Y için Y = a  •  b  •  b  •  b  •  b  • b  • a, X = a  •  b  •  b  •  b  •  b  •  b olamaz ( bkz. C şıkkı ).
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 30

## [28-31] Sorular için açıklama
X, Y ve Z aşağıda verildiği gibi tanımlanmış karşılıklı özyineli nesnelerdir. Tanımlarda toplam dört farklı (atomik) sembol (a, b, c ve ·) vardır. X, Y ya da Z ile tanımlanamayan tüm nesneler geçersizdir.
\[
\begin{array}{c|c}
\text{X =} & \begin{array}{c|c}
a \cdot a & \text{ya da;} \\
a \cdot X' \cdot a & \text{ya da;} \\
b \cdot Y' \cdot b & \text{ya da;} \\
c \cdot Z' \cdot c & \text{ya da;}
\end{array} \\
\hline
\text{Y =} & \begin{array}{c|c}
b \cdot b & \text{ya da;} \\
X' \cdot a & \text{ya da;} \\
Y' \cdot b & \text{ya da;} \\
Z' \cdot c & \text{ya da;}
\end{array} \\
\hline
\end{array}
\]
İfadelerdeki X' nesnesi X, Y' nesnesi Y, ve Z' nesnesi Z cinsinden başka nesnelerdir. Sırasıyla X, Y ve Z tipinden nesneleri girdi olarak alan f, g ve h fonksiyonları aşağıda tanımlanmıştır. Bu fonksiyonlar karşılık özyineli fonksiyonlar olup yalnız a, b ve c harflerini içeren kelimeler oluştururlar.
\[
\begin{array}{c|c}
f(X) = & \begin{array}{c|c}
aa & \text{eğer X = a} \cdot a \\
aaf(X') & \text{eğer X = a} \cdot X' \cdot a \\
g(Y')bb & \text{eğer X = b} \cdot Y' \cdot b \\
h(Z')c & \text{eğer X = c} \cdot Z' \cdot c
\end{array} \\
\hline
h(Z) = & \begin{array}{c|c}
c & \text{eğer Z = c} \cdot c \\
af(X') & \text{eğer Z = a} \cdot X' \\
bg(Y') & \text{eğer Z = b} \cdot Y' \\
cch(Z') & \text{eğer Z = c} \cdot Z'
\end{array}
\end{array}
\]
## AÇIKLAMA
Her nesnenin yukarıda belirtilen durumlarını yukarıdan aşağı numaralandıralım (X nesnesinin 1.durumu a, 2.durumu b · X' · a ...) ve soruları ona göre çözelim.

---

Hangisi yanlıştır?

Şıklar:
A) f(X) daima çift uzunlukta kelime üretir | B) h (Z) hem çift hem tek uzunlukta kelimeler üretebilir | C) f(X) kullanılarak a ile başlayıp c ile biten kelime üretilebilir | D) g (Y) kullanılarak c ile biten fakat c ile başlamayan kelime üretilebilir | E) g (Y) kullanılarak üretilebilecek kelime sayısı sonsuzdur

Cevap: B h (Z) hem çift hem tek uzunlukta kelimeler üretebilir

Çözüm:
## Şıklara bakalım:
A) Doğru. Başlangıç durumunda f(X) ve g(Y) çift, h(Z) tek uzunlukta kelime üretir. Sonraki adımlarda da bu 3 fonksiyon çiftlik-teklığini korur.
B) Yanlış. h(Z) her zaman sadece tek uzunlukta üretebilir.
C) Doğru. X-2. ve X-4. durumlar kullanıldığında oluşur.
D) Doğru. Y-4. ve Z-2. durumlar kullanıldığında oluşur.
E) Doğru. Sonsuz Y nesnesine karşın g(Y) ile sonsuz kelime üretilebilir.
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 31

## [28-31] Sorular için açıklama
X, Y ve Z aşağıda verildiği gibi tanımlanmış karşılıklı özyineli nesnelerdir. Tanımlarda toplam dört farklı (atomik) sembol (a, b, c ve ·) vardır. X, Y ya da Z ile tanımlanamayan tüm nesneler geçersizdir.
\[
\begin{array}{c|c}
\text{X =} & \begin{array}{c|c}
a \cdot a & \text{ya da;} \\
a \cdot X' \cdot a & \text{ya da;} \\
b \cdot Y' \cdot b & \text{ya da;} \\
c \cdot Z' \cdot c & \text{ya da;}
\end{array} \\
\hline
\text{Y =} & \begin{array}{c|c}
b \cdot b & \text{ya da;} \\
X' \cdot a & \text{ya da;} \\
Y' \cdot b & \text{ya da;} \\
Z' \cdot c & \text{ya da;}
\end{array} \\
\hline
\end{array}
\]
İfadelerdeki X' nesnesi X, Y' nesnesi Y, ve Z' nesnesi Z cinsinden başka nesnelerdir. Sırasıyla X, Y ve Z tipinden nesneleri girdi olarak alan f, g ve h fonksiyonları aşağıda tanımlanmıştır. Bu fonksiyonlar karşılık özyineli fonksiyonlar olup yalnız a, b ve c harflerini içeren kelimeler oluştururlar.
\[
\begin{array}{c|c}
f(X) = & \begin{array}{c|c}
aa & \text{eğer X = a} \cdot a \\
aaf(X') & \text{eğer X = a} \cdot X' \cdot a \\
g(Y')bb & \text{eğer X = b} \cdot Y' \cdot b \\
h(Z')c & \text{eğer X = c} \cdot Z' \cdot c
\end{array} \\
\hline
h(Z) = & \begin{array}{c|c}
c & \text{eğer Z = c} \cdot c \\
af(X') & \text{eğer Z = a} \cdot X' \\
bg(Y') & \text{eğer Z = b} \cdot Y' \\
cch(Z') & \text{eğer Z = c} \cdot Z'
\end{array}
\end{array}
\]
## AÇIKLAMA
Her nesnenin yukarıda belirtilen durumlarını yukarıdan aşağı numaralandıralım (X nesnesinin 1.durumu a, 2.durumu b · X' · a ...) ve soruları ona göre çözelim.

---

h(c·a·b·b·b·b·b) işleminin sonucu hangisidir?

Şıklar:
A) ccabbbbb | B) ccabbbbbb | C) ccabbbbbbb | D) ccaabbbbb | E) ccababbbb

Cevap: B ccabbbbbb

Çözüm:
Sadeleştirelim:
• h(c • a • b • b • b • b • b), 4.durum
• cc h(a • b • b • b • b • b), 2.durum
• cca f(b • b • b • b • b), 3.durum
• cca g(b • b • b), 3.durum
• ccab g(b • b) bbb, 1.durum
• ccab bb bbb
Bilgisayar Olimpiyatı 2012, 1. Aşama, Soru 32

## [32-35] Sorular için açıklama
Önce sürekli artan bir seri onu takiben sürekli azalan başka bir serinin birleşiminden oluşan dizilere **bitonik diziler** denir. Yani, n eleman içeren A[0..n-1] dizisi, eğer öyle bir k indisi (0 < k < n-1) için \(\forall i 0 \le i < k.A[i] < A[i+1]\) ve \(\forall i k < i < n-1.A[i] > A[i+1]\) sağlanıyorsa bitonik dizidir.
Örnek bitonik ve bitonik olmayan diziler aşağıdaki tabloda verilmiştir.
<table><tr><td>dizi</td><td>bitonik?</td><td>açıklama</td></tr><tr><td>1 2 7 8 6 3 2</td><td>evet</td><td>1 2 7 8 artan bir seri, 6 3 2 azalan bir seri</td></tr><tr><td>1 2 7 8 8 3 2</td><td>evet</td><td>1 2 7 8 artan seri, 8 3 2 azalan bir seri</td></tr><tr><td>1 2 7 7 8 8 3 2</td><td>hayır</td><td>1 2 7 8 artan bir seri ancak azalan seri yok</td></tr><tr><td>1 2 7 8</td><td>hayır</td><td>1 7 7 8 sürekli artmıyor</td></tr><tr><td>6 3 2</td><td>hayır</td><td>1 2 7 8 artan seri ancak azalan seri yok</td></tr><tr><td>6 3 2 1 2 7 8</td><td>hayır</td><td>6 3 2 azalan bir seri ancak artan bir seri yok</td></tr><tr><td>2 6 3 2 1 7 8</td><td>hayır</td><td>artan ve azalan seri var ancak sıra doğru değil, önce artan olmalı çok sayıda artan ve azalan seri var</td></tr></table>

---

Bitonik olduğu bilinen 50 elemanı bir dizide en küçük elemanı bulmak için kaç karşılaştırma gerek ve yeterlidir?

Şıklar:
A) O | B) 1 | C) 2 | D) 24 | E) 49

Cevap: B 1

Çözüm:
Bir dizi bitonik ise en küçük eleman ya başladır ya da sondadır. Tek bir karşılaştırma ile bulunabilir.