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

[20-22] Sorular İçin Açıklama
K, YveMkarakterlerini kullanarak (bu harfler sırasıyla Kırmızı, Yeşil ve Mavi renklerini
gösterir) renkli bir üçgeni temsil eden bir program yazıyoruz. Üçgen oluşturma kuralları
şöyledir:
● İlksatırdaki karakterler girdi olarak verilir.
● İkinci satırdan itibaren her satır bir önceki satırdan bir tane daha az karakter içerir.
● Birsatırdaki ardışık iki karakter incelenerek sonraki satırdaki karakter bulunur.
● Birsatırda aynı rengi temsil eden iki karakter yan yana ise sonraki satıra bu
karakter konur.
● Birsatırda farklı iki rengi temsil eden iki karakter varsa sonraki satıra olmayan
rengin karakteri konur.
● Ensonsatırda tek bir karakter kalana kadar bu kurallar uygulanır.
Örnek olarak, aşağıdaki üçgenler bu kurallara göre oluşturulmuştur:

K K
 K

Y K M
 M Y
  K

M K
 Y

---

Bir satırda yalnızca tek bir karenin renginin bildiğimizi varsayalım. Bu satırdaki bilinmeyen karakterler kurallar dahilinde kaç farklı şekilde renklendirilebilir?

Şıklar:
A) 1 | B) 2 | C) 3 | D) 4 | E) İlgili olması gereken karakter sayısına göre değişir.

Cevap: A 1

Çözüm:
Bir satırdaki karakterler biliniyorsa ve sonraki satırda bir karakter biliniyorsa, o satırın tamamlanmasının tek bir yolu vardır. Bunu tüme varım ile ispatlayabiliriz: Bunun için en alt satırdan (yani tek renk içeren satırdan) başlayarak üste doğru gidelim. En küçük satır tamamen biliniyor. Üstündeki satırdaki tek bir karakter bilinirse o zaman o satır tek bir yol ile tamamlanabilir. Bu şekilde istenen ifade elde edilir.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 22

[20-22] Sorular İçin Açıklama
K, YveMkarakterlerini kullanarak (bu harfler sırasıyla Kırmızı, Yeşil ve Mavi renklerini
gösterir) renkli bir üçgeni temsil eden bir program yazıyoruz. Üçgen oluşturma kuralları
şöyledir:
● İlksatırdaki karakterler girdi olarak verilir.
● İkinci satırdan itibaren her satır bir önceki satırdan bir tane daha az karakter içerir.
● Birsatırdaki ardışık iki karakter incelenerek sonraki satırdaki karakter bulunur.
● Birsatırda aynı rengi temsil eden iki karakter yan yana ise sonraki satıra bu
karakter konur.
● Birsatırda farklı iki rengi temsil eden iki karakter varsa sonraki satıra olmayan
rengin karakteri konur.
● Ensonsatırda tek bir karakter kalana kadar bu kurallar uygulanır.
Örnek olarak, aşağıdaki üçgenler bu kurallara göre oluşturulmuştur:

K K
 K

Y K M
 M Y
  K

M K
 Y

---

Bazı satırlarda sadece en soldaki ve en sağdaki karakterler en son satırdaki karakterin ne olduğunu belirler. Örnek olarak bir satırın en solunda K, en sağında M olsun. Son satır, diğer karakterlerden bağımsız olarak G karakterini içerir. Aşağıdakilerden hangisi bu tür bir satırdaki karakter sayısını verir?

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

Cevap: B 4

Çözüm:
Bu özellik 4 tane karakterli satırlar için geçerlidir. (Daha uzun bazı satırlar için de bu özellik vardır). Bu özelliğin 4 karakterli satırlar için geçerli olduğu denenerek görülebilir. Genel olarak karakter sayısı 3^{n}+1 olan satırlar için (yani, 10, 28, 82, vs.) bu özellik bulunur.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 23

[23-25 Sorular için Açıklama]
\begin{itemize}
    \item \(A\) ve \(B\) kümesinde \(A\)’dan \(B\)’ye ikili ilişki (\(A\)’dan \(B\)’ye bir bağıntı), \(A\) kartezyen \(B\)’nin (\(A \times B\)’nin) bir altkümesidir.
    \item \(A\) kümesinde bir ilişki \(A\)’dan \(A\)’ya ilişkiye karşılık gelir.
    \item \textbf{Örnek:} \(A = \{1, 2, 3, 4\}\) kümesi için \(R = \{(a, b) \mid a, b\text{'yi böler}\}\) ilişkisinin içinde yer alan sıralı çiftler \((1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3)\) ve \((4,4)\)'dür.
    \item \(A\) kümesinde bir \(R\) bağıntısı eğer her \(a \in A\) için \((a, a) \in R\) şartını sağlıyorsa \(R\) bağıntısı yansıyan olarak adlandırılır.
    \item \(A\) kümesinden alınan her \(a, b\) için, \((a, b) \in R\) olduğunda \((b, a)\) da \(R\)’nin elemanı ise \(R\) bağıntısı simetrik olarak adlandırılır.
\end{itemize}

---

A elemanları birbirinden farklı 8 elemanlı bir küme olsun. A kümesinde kaç farklı simetrik ve yansıyan bağıntı tanımlanabilir?

Şıklar:
A) \(2^8\) | B) \(2^{16}\) | C) \(2^{28}\) | D) \(2^{36}\) | E) \(2^{63}\)

Cevap: C \(2^{28}\)

Çözüm:
A kümesinin eleman sayısını \(n\) ile gösterelim. A kümesinde \(n^2\) tane sıralı ikili tanımlanabilir. Bunlardan \(n\) tanesi her yansıyan bağıntıda bulunmak zorundadır. Geri kalan \(n(n-1)\) tane ikili ikişerli \(\frac{n(n-1)}{2}\) tane grup olarak düşünülebilir. Şartları sağlayan bir bağıntıda bir grup ya bulunacaktır ya bulunmayacaktır. Bu seçme işlemi \(2^{\frac{n(n-1)}{2}} = 2^{28}\) şekilde yapılabilir.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 24

[23-25 Sorular için Açıklama]
\begin{itemize}
    \item \(A\) ve \(B\) kümesinde \(A\)’dan \(B\)’ye ikili ilişki (\(A\)’dan \(B\)’ye bir bağıntı), \(A\) kartezyen \(B\)’nin (\(A \times B\)’nin) bir altkümesidir.
    \item \(A\) kümesinde bir ilişki \(A\)’dan \(A\)’ya ilişkiye karşılık gelir.
    \item \textbf{Örnek:} \(A = \{1, 2, 3, 4\}\) kümesi için \(R = \{(a, b) \mid a, b\text{'yi böler}\}\) ilişkisinin içinde yer alan sıralı çiftler \((1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3)\) ve \((4,4)\)'dür.
    \item \(A\) kümesinde bir \(R\) bağıntısı eğer her \(a \in A\) için \((a, a) \in R\) şartını sağlıyorsa \(R\) bağıntısı yansıyan olarak adlandırılır.
    \item \(A\) kümesinden alınan her \(a, b\) için, \((a, b) \in R\) olduğunda \((b, a)\) da \(R\)’nin elemanı ise \(R\) bağıntısı simetrik olarak adlandırılır.
\end{itemize}

---

A elemanları birbirinden farklı 8 elemanlı bir küme olsun. A kümesinde kaç farklı simetrik bağıntı tanımlanabilir?

Şıklar:
A) \(2^8\) | B) \(2^{16}\) | C) \(2^{28}\) | D) \(2^{36}\) | E) \(2^{63}\)

Cevap: D \(2^{36}\)

Çözüm:
A kümesinin eleman sayısını \(n\) ile gösterelim. A kümesinde \(n^2\) tane sıralı ikili tanımlanabilir. Bunlardan \(n\) tanesinde bir eleman kendisiyle ilişkilidir. Bu \(n\) ikilinin her biri bir grup olarak düşünülebilir. Geri kalan \(n(n-1)\) tane ikili ikişerli \(\frac{n(n-1)}{2}\) tane grup olarak düşünülebilir. Toplamda \(\frac{n(n+1)}{2}\) grup vardır. Simetrik bir bağıntıda her bir grup ya bulunacaktır ya da bulunmayacaktır. Bu seçme işlemi \(2^{\frac{n(n+1)}{2}} = 2^{36}\) şekilde yapılabilir. Dolayısıyla
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 25

[23-25 Sorular için Açıklama]
\begin{itemize}
    \item \(A\) ve \(B\) kümesinde \(A\)’dan \(B\)’ye ikili ilişki (\(A\)’dan \(B\)’ye bir bağıntı), \(A\) kartezyen \(B\)’nin (\(A \times B\)’nin) bir altkümesidir.
    \item \(A\) kümesinde bir ilişki \(A\)’dan \(A\)’ya ilişkiye karşılık gelir.
    \item \textbf{Örnek:} \(A = \{1, 2, 3, 4\}\) kümesi için \(R = \{(a, b) \mid a, b\text{'yi böler}\}\) ilişkisinin içinde yer alan sıralı çiftler \((1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3)\) ve \((4,4)\)'dür.
    \item \(A\) kümesinde bir \(R\) bağıntısı eğer her \(a \in A\) için \((a, a) \in R\) şartını sağlıyorsa \(R\) bağıntısı yansıyan olarak adlandırılır.
    \item \(A\) kümesinden alınan her \(a, b\) için, \((a, b) \in R\) olduğunda \((b, a)\) da \(R\)’nin elemanı ise \(R\) bağıntısı simetrik olarak adlandırılır.
\end{itemize}

---

A elemanları birbirinden farklı 8 elemanlı bir küme olun. R ise A'dan A'ya tanımlı ve rastgele seçilmiş bir bağıntı olsun. R bağıntısının yansıyan olma olasılığı nedir?

Şıklar:
A) 1/32 | B) 1/36 | C) 1/64 | D) 1/128 | E) 1/256

Cevap: E 1/256

Çözüm:
A kümesinin eleman sayısını n ile gösterelim. A kümesinde \(n^2\) tane sırali ikili tanımlanabilir. Bunlardan \(n\) tanesinde biri eleman kendisiyle ilişkilidir. Bir bağıntının yansıyan olması için bu \(n\) ikilinin tamamını içermesi gerekir. Rastgele seçilmiş bir R
bağıntısı bu ikililerin her birini 1/2 olasılıkla içerir. Hepsini birden içerme olasılığı 1/2"dir. Bize n = 8 olarak verildiği için sonuç 1/2^8 yani 1/256 olur.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 26

[26-27SorulariçinAçıklama]
1’den n’ye kadar olan sayıların bütün sıralamalarını göz önünde bulunduralım. Ardışık iki sayıdan küçük olanın büyük olandan hemen önce gelmediği sıralamaları iyi sıralamalar olarak adlandıralım. Yani iyi bir sıralamada, herhangi bir i sayısı p konumunda bulunuyorsa, i + 1 sayısı p + 1 konumunda bulunmamaktadır. Örnek verecek olursak, n = 3 için, iyi sıralamalar aşağıdaki üç sıralamadır:
(1,3,2), (2,1,3) (3,2,1).

---

n = 4 için kaç tane iyi sıralama vardır?

Şıklar:
A) 8 | B) 9 | C) 11 | D) 13 | E) 10

Cevap: C 11

Çözüm:
P(n), n sayının iyi sıralama sayısını göstersin. P(n)'deki sıralamaların nasıl oluştuğunu inceleyelim. Burada iki durum mevcuttur: n'nin iyi bir sıralamaya ya da kötü bir sıralamaya eklenmesidir.
İlk durum: n'nin iyi bir sıralamayı bozmayacak şekilde eklenmesi. Bu durumda n ancak n - 1'den sonraki pozisyona eklenirse elde edilen sıralama artık iyi bir sıralama olmayacaktır. Dolayısıyla iyi bir sıralama için n'nin yerleştirilebileceği n - 1 farklı konum bulunmaktadır. Dolayısıyla bu şekilde elde edilebilecek iyi sıralamaların sayısı (n - 1)×P(n - 1) olacaktır.
İkinci durum: n'nin iyi olmayan bir sıralamaya eklenmesiyle iyi bir sıralama elde edilmesidir. Bu durum sadece bir çiftten kaynaklı iyi olmayan bir sıralamaya eklenmesiyle elde edilebilmektedir. Ardışık olan sayıları m ve m + 1 olarak adlandıralım. İyiliği bozan çift tek bir sayı gibi ele alınırsa, n - 1 sayıdan oluşan sadece bir çiftten kaynaklı iyi olmayan sıralamaların sayısı (n - 2)×P(n - 2) olacaktır. Burada n - 2 ardışık çiftlerin sayısını P(n - 2) ise bu çift tek sayıymış gibi ele alındığında iyi sıralamaları sayısını göstermektedir.
Dolayısıyla P(n) = (n - 1)×P(n - 1) + (n - 2)×P(n - 2)'dir. P(1) ve P(2) değerleri 1 olacaktır. Sorunun cevabı içinse n yerine 4 koyduğumuzda cevap 11 olacaktır.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 27

[26-27SorulariçinAçıklama]
1’den n’ye kadar olan sayıların bütün sıralamalarını göz önünde bulunduralım. Ardışık iki sayıdan küçük olanın büyük olandan hemen önce gelmediği sıralamaları iyi sıralamalar olarak adlandıralım. Yani iyi bir sıralamada, herhangi bir i sayısı p konumunda bulunuyorsa, i + 1 sayısı p + 1 konumunda bulunmamaktadır. Örnek verecek olursak, n = 3 için, iyi sıralamalar aşağıdaki üç sıralamadır:
(1,3,2), (2,1,3) (3,2,1).

---

n = 6 için kaç tane iyi sıralama vardır?

Şıklar:
A) 298 | B) 309 | C) 256 | D) 301 | E) 362

Cevap: B 309

Çözüm:
Üstteki soruda elde edilen formülde değerleri yerine koyduğumuzda P(4) = 11,
P(5) = 53 ve P(6) = 309 olacaktır.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 28

[28-30 Sorular için Açıklama]
Ali çiçek süsleyerek geçimini sağlamaktadır ve **n** gün çalıştıktan sonra emekliye ayrılacaktır. Ali'nin süslediği çiçekleri satabilmesi piyasadaki süslenmiş çiçek talebine de bağlıdır. **x1, x2, ..., xn** dizisi Ali'nin çiçeklerine önümüzdeki **n** gündeki talebi göstermektedir. Yani **xi** Ali'nin **i**. gün sonra satabileceği (dolayısıyla süsleyebileceği) azami çiçek sayısını göstermektedir. Çiçekler süslendiği gün satılmak zorundadır.

Ali artık yaşlandığı için dinlenmeden çalıştığı her gün bir önceki güne göre daha az çiçek süsleyebilmektedir. Ali dinlendiği gün hiç çiçek süslememektedir. **si** Ali'nin üst üste çalıştığı **i**. günde süsleyebileceği azami çiçek sayısı olsun. **s1 >= s2 >= ... >= sn >= 1** değerleri bize verilmiş olsun.

Amacımız Ali’nin **n** günde süsleyip satabileceği toplam çiçek sayısının alabileceği en büyük değeri bulmaktır. Ali’nin dinleneceği günleri bu değere ulaşacak şekilde seçen stratejiye optimal strateji diyoruz.

Örnek: **n = 4**, **x = {10, 1, 7, 7}** ve **s = {8, 4, 2, 1}** olsun. Bu durumda Ali'nin uygulayabileceği optimal strateji 2. gün dinlenmek ve diğer günler çalışmaktır. Bu strateji altında Ali **8 + 0 + 7 + 4 = 19** çiçek süsleyecektir.

---

n = 179 için Ali optimal stratejiyi uygularsa en fazla kaç gün dinlenebilir?

Şıklar:
A) 59
B) 60
C) 61
D) 89
E) 90

Cevap: D 89

Çözüm:
Ali optimal stratejide son gün dinlenemez, bu yüzden Ali 179. gün çalışacaktır. Aynı
zamanda, Ali hiçbir zaman ardışık iki gün dinlenemez. Bu yüzden ilk 178 günün en
fazla yarısında dinlenebilir. Bu da 89 güne karşılık gelmektedir. Bu yüzden cevap en
fazla 89 olabilir.
𝑥 = {10,  10, …,10}
ve
𝑠 = {10,1,1,1, …,1}
için optimal
stratejide Ali tek günler çalışacak ve çift günler dinlenecektir. Bu yüzden cevap en
az 89’dur. Dolayısıyla doğru cevap 89’dur.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 29

[28-30 Sorular için Açıklama]
Ali çiçek süsleyerek geçimini sağlamaktadır ve **n** gün çalıştıktan sonra emekliye ayrılacaktır. Ali'nin süslediği çiçekleri satabilmesi piyasadaki süslenmiş çiçek talebine de bağlıdır. **x1, x2, ..., xn** dizisi Ali'nin çiçeklerine önümüzdeki **n** gündeki talebi göstermektedir. Yani **xi** Ali'nin **i**. gün sonra satabileceği (dolayısıyla süsleyebileceği) azami çiçek sayısını göstermektedir. Çiçekler süslendiği gün satılmak zorundadır.

Ali artık yaşlandığı için dinlenmeden çalıştığı her gün bir önceki güne göre daha az çiçek süsleyebilmektedir. Ali dinlendiği gün hiç çiçek süslememektedir. **si** Ali'nin üst üste çalıştığı **i**. günde süsleyebileceği azami çiçek sayısı olsun. **s1 >= s2 >= ... >= sn >= 1** değerleri bize verilmiş olsun.

Amacımız Ali’nin **n** günde süsleyip satabileceği toplam çiçek sayısının alabileceği en büyük değeri bulmaktır. Ali’nin dinleneceği günleri bu değere ulaşacak şekilde seçen stratejiye optimal strateji diyoruz.

Örnek: **n = 4**, **x = {10, 1, 7, 7}** ve **s = {8, 4, 2, 1}** olsun. Bu durumda Ali'nin uygulayabileceği optimal strateji 2. gün dinlenmek ve diğer günler çalışmaktır. Bu strateji altında Ali **8 + 0 + 7 + 4 = 19** çiçek süsleyecektir.

---

n = 4, \(x = \{10, 2, 9, 6\}\), ve \(s = \{8, 8, 6, 3\}\) için Ali optimal stratejiyi uyguladığında toplam kaç çiçek süslemiş olur?

Şıklar:
A) 12 | B) 16 | C) 19 | D) 22 | E) 25

Cevap: D 22

Çözüm:
Optimal stratejide Ali 2. gün dinlenir kalan günler çalışır. Böylelikle \(8 + 0 + 8 + 6 = 22\) çiçek süsler.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 30

[28-30 Sorular için Açıklama]
Ali çiçek süsleyerek geçimini sağlamaktadır ve **n** gün çalıştıktan sonra emekliye ayrılacaktır. Ali'nin süslediği çiçekleri satabilmesi piyasadaki süslenmiş çiçek talebine de bağlıdır. **x1, x2, ..., xn** dizisi Ali'nin çiçeklerine önümüzdeki **n** gündeki talebi göstermektedir. Yani **xi** Ali'nin **i**. gün sonra satabileceği (dolayısıyla süsleyebileceği) azami çiçek sayısını göstermektedir. Çiçekler süslendiği gün satılmak zorundadır.

Ali artık yaşlandığı için dinlenmeden çalıştığı her gün bir önceki güne göre daha az çiçek süsleyebilmektedir. Ali dinlendiği gün hiç çiçek süslememektedir. **si** Ali'nin üst üste çalıştığı **i**. günde süsleyebileceği azami çiçek sayısı olsun. **s1 >= s2 >= ... >= sn >= 1** değerleri bize verilmiş olsun.

Amacımız Ali’nin **n** günde süsleyip satabileceği toplam çiçek sayısının alabileceği en büyük değeri bulmaktır. Ali’nin dinleneceği günleri bu değere ulaşacak şekilde seçen stratejiye optimal strateji diyoruz.

Örnek: **n = 4**, **x = {10, 1, 7, 7}** ve **s = {8, 4, 2, 1}** olsun. Bu durumda Ali'nin uygulayabileceği optimal strateji 2. gün dinlenmek ve diğer günler çalışmaktır. Bu strateji altında Ali **8 + 0 + 7 + 4 = 19** çiçek süsleyecektir.

---

n = 5, \(x = \{4, 6, 19, 2, 7\}\), ve \(s = \{15, 9, 3, 1\}\) için Ali optimal stratejiyi uyguladığında toplam kaç çiçek süslemiş olur?

Şıklar:
A) 18
B) 19
C) 20
D) 21
E) 26

Cevap: E 26

Çözüm:
Optimal stratejide Ali 2. Gün dinlenir kalan günler çalışır. Böylelikle 4 + 0 + 15 + 2 + 5 = 26 çiçek süslemiş olur.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 30

[21-30] Sorular İçin Açıklama
● Soruları C programlama dili çerçevesinde cevaplayınız.
● Derleyici olarak gcc kullanıldığını varsayınız.
● Gerekli tüm başlık (header) dosyalarının verilen programa dahil edildiğini
varsayınız.

---
```c

Şıklar:


Çözüm:
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 31

[31-32 Sorular için Açıklama]
23 Nisan Ulusal Egemenlik ve Çocuk Bayramı için dünyanın bir çok ülkesinden Türkiye’ye çocuklar gelecektir.  \( x_{1}, x_{2}, \ldots, x_{n} \)  dizisi Türkiye’ye gelecek olan n tane yabancı çocuğun yaşlarını göstermektedir. Türkiye’deki m çocuk yurt dışından gelecek misafirleri ağırlamak için gönüllü olmuştur.  \( y_{1}, y_{2}, \ldots, y_{m} \)  dizisi Türk çocukların yaşlarını göstermektedir. Kurallar gereği bir Türk çocuğu en fazla bir yabancı çocuğu ağırlayabilir ve kendi ile misafir çocuğun yaşları farkının en fazla 1 olması gerekmektedir. Yani 13 yaşındaki bir Türk çocuğu 12, 13 veya 14 yaşındaki bir misafiri ağırlayabilir.

---

Yabancı çocukların yaşları  \( x = \{7, 15, 11, 13, 9, 11, 17, 10, 17, 16\} \)  ve Türk çocukların yaşları  \( y = \{7, 7, 13, 17, 12, 16, 15, 16, 6, 15\} \)  ise en fazla kaç yabancı öğrenci misafir edilebilir?

Şıklar:
A) 6 | B) 7 | C) 8 | D) 9 | E) 10

Cevap: B 7

Çözüm:
Sorunun çözümü için diziler küçükten büyüğe sıralanır ve açgözlü olarak eşleştirme sağlanır. Verilen diziler için sonuç 7'dir.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 32

## [31-32 Sorular için Açıklama]
23 Nisan Ulusal Egemenlik ve Çocuk Bayramı için dünyanın bir çok ülkesinden Türkiye’ye çocuklar gelecektir.  \( x_{1}, x_{2}, \ldots, x_{n} \)  dizisi Türkiye’ye gelecek olan n tane yabancı çocuğun yaşlarını göstermektedir. Türkiye’deki m çocuk yurt dışından gelecek misafirleri ağırlamak için gönüllü olmuştur.  \( y_{1}, y_{2}, \ldots, y_{m} \)  dizisi Türk çocukların yaşlarını göstermektedir. Kurallar gereği bir Türk çocuğu en fazla bir yabancı çocuğu ağırlayabilir ve kendi ile misafir çocuğun yaşları farkının en fazla 1 olması gerekmektedir. Yani 13 yaşındaki bir Türk çocuğu 12, 13 veya 14 yaşındaki bir misafiri ağırlayabilir.

---

Yabancı çocukların yaşları
\( x = \{17, 14, 10, 12, 5, 10, 13, 11, 12, 8, 14, 10, 8, 17, 9, 14, 7, 5, 8, 11\} \)  ve
Türk çocukların yaşları  \( y = \{5, 15, 16, 11, 9, 12, 12, 15, 7, 7, 10, 10, 17, 16, 8\} \)  ise en fazla kaç yabancı öğrenci misafiir edilebilir?

Şıklar:
A) 10 | B) 11 | C) 12 | D) 13 | E) 14

Cevap: E 14

Çözüm:
Sorunun çözümü için diziler küçükten büyuğe sıralanır ve açgözlü olarak eşleştirmesi sağlanır. Verilen diziler için sonuç 14'tür.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 33

[33-34 Sorular için Açıklama]
En küçük kapsayan düğüm probleminde girdi olarak bir çizge verilir. Bu problemde
çizgedeki her kenara değen bir düğümü içeren bir düğüm alt kümesi aranmaktadır. Amaç
bu şartı sağlayan ve en az sayıda düğümden oluşan düğüm altkümesini bulmaktır.
Örnek: Aşağıda 5 düğümlü ve 5 kenarlı bir çizge örneği verilmiştir. Bu çizge için en küçük kapsayan düğüm probleminin çözümü 2 ve 5 numaralı düğümlerdir.
[GÖRSEL]

---

1000 düğümden oluşan bir çizgede, en küçük kapsayan düğüm probleminin çözümü en fazla kaç düğümden oluşabilir?

Şıklar:
A) 400 | B) 500 | C) 501 | D) 999 | E) 1000

Cevap: D 999

Çözüm:
Her düğüm ikilisi arasında bir kenarın olduğu n düğümlü bir çizgede, n - 1 düğümden küçük bir çözüm yoktur. Dolayısıyla cevap 999'dur.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 34

[33-34 Sorular için Açıklama]
En küçük kapsayan düğüm probleminde girdi olarak bir çizge verilir. Bu problemde
çizgedeki her kenara değen bir düğümü içeren bir düğüm alt kümesi aranmaktadır. Amaç
bu şartı sağlayan ve en az sayıda düğümden oluşan düğüm altkümesini bulmaktır.
Örnek: Aşağıda 5 düğümlü ve 5 kenarlı bir çizge örneği verilmiştir. Bu çizge için en küçük kapsayan düğüm probleminin çözümü 2 ve 5 numaralı düğümlerdir.
[GÖRSEL]

---

1000 düğümden ve 999 kenardan oluşan bir bağlı çizgede, en küçük örten düğüm
probleminin çözümü en fazla kaç düğümden oluşabilir? Bağlı çizgelerde, her iki düğüm
çifti arasında bir yol vardır. Bu yol bir ya da daha fazla kenardan oluşmaktadır.

Şıklar:
A) 400
B) 500
C) 501
D) 999
E) 1000

Cevap: B 500

Çözüm:
Bu soruda tarif edilen çizge 1000 düğümlü bir ağaca denk gelmektedir. Yol da bir ağaçtır.
n düğümlü bir yolda en küçük örten düğüm probleminin çözümü \( \lfloor \frac{n}{2} \rfloor \) düğüm içerir.
Bu yüzden cevap en az 500’dür. Verilen bir ağaçtaki tek seviyeye karşılık gelen ve çift seviyeye
karşılık gelen düğümlere bakınız. Her iki küme de örten düğüm probleminin çözümü dür.
Güvercin yuvası prensibine göre en az bir tanesi en fazla \( \lfloor \frac{n}{2} \rfloor \) düğümden oluşmaktadır.
Bu yüzden istenen cevap en fazla \( \lfloor \frac{1000}{2} \rfloor = 500 \)’dür.
Dolayısıyla cevap 500’dür. Cevap B şıkkıdır.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 35

Düğümleri  ve  adında iki ayrık ve birbirinden bağımsız kümeye ayrılabilen ve her bir kenarı U kümesindeki bir düğümü V kümesindeki bir düğüme bağlayan çizgelere iki parçalı çizge adı verilir. 

 
Örnek: Aşağıdaki resimde verilen çizge örneği iki parçalı bir çizgedir. Bu çizgenin düğümlerinin U = {2,5} ve V = {1, 3, 4} olacak şekilde iki ayrık ve birbirinden bağımsız kümeye ayrılabildiğine ve her kenarın bir düğümünün U kümesinde ve diğer düğümünün ise kümesinde olduğuna dikkat ediniz.

Her ağacın iki parçalı bir çizge olduğuna ancak aşağıdaki şekilde görüldüğü üzere her iki
parçalı çizgenin bir ağaç olmadığına dikkat ediniz.
[GÖRSEL]
---

1000 düğümlü iki parçalı bir çizgede, en küçük örten düğüm probleminin çözümü
en fazla kaç düğümden oluşabilir?

Şıklar:
A) 400
B) 500
C) 501
D) 999
E) 1000

Cevap: B 500

Çözüm:
\( U \) ve \( V \) kümelerinden herhangi biri örten düğüm probleminin bir çözümüdür. Güvercin
yuvası prensibi gereği küçük olanı en fazla \( \lfloor \frac{n}{2} \rfloor \) düğümden oluşmaktadır. Bu yüzden,
cevap en fazla 500’dür. Her yol iki parçalı bir çizge olduğu için ve \( n \) düğümlü bir yolda en
küçük örten düğüm probleminin çözümü \( \lfloor \frac{n}{2} \rfloor \) olduğu için cevap en az 500’dür.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 36

[36-50 soruları için açıklama]
- Soruları C programlama dili çerçevesinde cevaplayınız.
- Derleyici olarak gcc kullanıldığını varsayınız.
- Gerekli tüm başlık (header) dosyalarının verilen programa dahil edildiğini varsayınız.

---

İki pozitif tam sayı parametre ile çağrıldığında aşağıdaki fonksiyon ne döner?
```c
int f( int n, int m ) {
if ( n == m ) {
return n;
} else if ( m > n ) {
return f(m - n, n);
} else {
return f(n - m, m);
}
}
```

Şıklar:
A) n'ın m'li kombinasyonunu | B) n'ın m. kuvvetini | C) n ve m'nin en büyük ortak bölenini | D) n ve m'nin en küçük ortak katını | E) Hiçbiri

Cevap: B n'ın m. kuvvetini

Çözüm:
Bu fonksiyon n ve m'nin en büyük ortak bölenini hesaplamaktadır.
Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 37

[36-50 soruları için açıklama]
- Soruları C programlama dili çerçevesinde cevaplayınız.
- Derleyici olarak gcc kullanıldığını varsayınız.
- Gerekli tüm başlık (header) dosyalarının verilen programa dahil edildiğini varsayınız.

---

Aşağıdaki program parçası ekrana kaç tane ‘A’ karakteri yazar?
```c
int i, j, n = 256;
for (i=n;i>=1;i/=2)
for (j=0;j<i;j++)
printf("A\n");
```

Şıklar:
A) 256
B) 255
C) 511
D) 624
E) 1024

Cevap: C 511

Çözüm:
i döngü değişkeni sırasıyla 256, 128, 64, 32, 16, 8, 4, 2 ve 1 değerlerini alır. Bu değerler
görüldüğü üzere 20’dan 28’e kadar olan 2’nin kuvvetleridir. İçteki döngü her i değeri için i
defa çalışır ve ekrana i tane A karakteri basar. Bu durumda ekrana basılan toplam A karakteri sayısı 2^0’dan 2^8’e kadar olan 2’nin kuvvetlerinin toplamıdır. Bu da 2^9-1 = 511’e
eşittir.