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

[Soru 6-7 için açıklama]
Bir zamanlar, Gizemli Adalar Ülkesinde birbirine gizli tünellerle bağlı bir dizi ada vardı. Bu tüneller, adalar
arasında seyahat etmeyi sağlıyordu, öyle ki tünelleri kullanarak herhangi bir adadan başka herhangi bir
adaya ulaşılabilmekteydi. Ancak zamanla, bazı tüneller unutulmuş veya zarar görmüştü. Ülkenin
mühendisleri bu tünellerden bir kısmını seçip yenileyerek bir tünel ağı oluşturmak için yeni bir plan
yaptılar. Bu plana göre aşağıdaki adımlar gerçekleştirildi:
1. Tümtünelleri içeren bir liste oluşturuldu ve listedeki tüneller risk derecelerine göre artan sırada
sıralandı. (Tünelin risk derecesi bir tamsayı ile gösterilmekteydi.) Bu listeye L dendi.
2. Yyenilenecek tünelleri ifade eden başlangıçta boş bir tünel kümesi olarak tanımlandı.
3. Başlangıçta, her ada kendi başına bir bölge olarak kabul edildi.
4. Sıralı tüneller listesi L’deki her bir tünel t için (sırayla):
a. Eğer t, farklı bölgelerdeki iki adayı birbirine bağlıyorsa:
i. t yenilenecek tüneller kümesi Y’ye eklendi.
ii. t’nin bağladığı iki adanın (bu adaları a ve b olarak adlandıralım) içinde bulundukları
bölgeler birleştirilip tek bir bölge sayıldı. (Bu, a’nın içinde bulunduğu bölgedeki tüm
adalar ile b’nin içinde bulunduğu bölgedeki tüm adaların artık aynı tek bölge içinde
sayılması anlamına gelmekteydi).
b. Eğer t, zaten aynı bölge içinde olan iki adayı birbirine bağlıyorsa, bu tünel göz ardı edildi.
5. Tüm adalar tek bir bölge oluşturduğunda işlem tamamlandı.

---

Yukarıdaki algoritma, aşağıda verilen 10 ada ve aralarında bulunan 16 tünel için çalıştırılırsa algoritma sonlandığında Y kümesindeki tünellerin risk derecelerinin toplamı ne olur? Tünel gösterimi, (ada1, ada2, r) şeklindedir ve bu tünelin ada1 ile ada2 arasında olduğunu ve r risk derecesine sahip olduğunu belirtir. Adalar-Kümesi = {A, B, C, D, E, F, G, H, I, J}
Tüneller-Kümesi = {(C, G,1), (A,B,2), (E,J,2), (H,I,2), (I,J,3), (B,C,3), (B,G,4), (E,I,4), (A,G,5), (D,I,5), (G,H,6), (D,E,7), (F,G,8), (A,F,8), (C,H,9), (C,D,10)}

Şıklar:
A) 29 | B) 32 | C) 33 | D) 36 | E) 37

Cevap: B 32

Çözüm:
Verilen algoritma Kruskal’ın en küçük kapsayan ağaç algoritmasıdır. Adaların düğümlerle, tünellerin kenarlarla modellendiği bir çizgede bu algoritma çalıştırıldığında en küçük kapsayan ağacın içerdiği kenarların ağırlıkları toplamı 32 olarak bulunur.
Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 7

[Soru 6-7 için açıklama]
Bir zamanlar, Gizemli Adalar Ülkesinde birbirine gizli tünellerle bağlı bir dizi ada vardı. Bu tüneller, adalar
arasında seyahat etmeyi sağlıyordu, öyle ki tünelleri kullanarak herhangi bir adadan başka herhangi bir
adaya ulaşılabilmekteydi. Ancak zamanla, bazı tüneller unutulmuş veya zarar görmüştü. Ülkenin
mühendisleri bu tünellerden bir kısmını seçip yenileyerek bir tünel ağı oluşturmak için yeni bir plan
yaptılar. Bu plana göre aşağıdaki adımlar gerçekleştirildi:
1. Tümtünelleri içeren bir liste oluşturuldu ve listedeki tüneller risk derecelerine göre artan sırada
sıralandı. (Tünelin risk derecesi bir tamsayı ile gösterilmekteydi.) Bu listeye L dendi.
2. Yyenilenecek tünelleri ifade eden başlangıçta boş bir tünel kümesi olarak tanımlandı.
3. Başlangıçta, her ada kendi başına bir bölge olarak kabul edildi.
4. Sıralı tüneller listesi L’deki her bir tünel t için (sırayla):
a. Eğer t, farklı bölgelerdeki iki adayı birbirine bağlıyorsa:
i. t yenilenecek tüneller kümesi Y’ye eklendi.
ii. t’nin bağladığı iki adanın (bu adaları a ve b olarak adlandıralım) içinde bulundukları
bölgeler birleştirilip tek bir bölge sayıldı. (Bu, a’nın içinde bulunduğu bölgedeki tüm
adalar ile b’nin içinde bulunduğu bölgedeki tüm adaların artık aynı tek bölge içinde
sayılması anlamına gelmekteydi).
b. Eğer t, zaten aynı bölge içinde olan iki adayı birbirine bağlıyorsa, bu tünel göz ardı edildi.
5. Tüm adalar tek bir bölge oluşturduğunda işlem tamamlandı.

---
Adalar kümesinin {A2k| 0 ≤ k ≤ 1000} olarak gösterildiği 1001 adadan oluşan bir başka adalar ülkesi düşünelim. Bu ülkede her bir adadan diğer bütün adalara birer tünel olduğunu varsayalım. (Tüneller farklı derinliklerde olsun ve birbiriyle kesişmesin.) A1 ve A2 adaları arasındaki tünelin risk derecesi (i+j)/2 ise yukarıda verilen algoritma bu ülkedeki adalar ve tüneller için çalıştırıldığında algoritma sonunda Y kümesindeki tünellerin risk derecelerinin toplamı ne olur?

Şıklar:
A) 125250 | B) 250500 | C) 499500 | D) 500000 | E) 500500

Cevap: E 500500 ÇÖZÜM

Çözüm:
Verilen algoritma Kruskal’ın en küçük kapsayan ağaç algoritmasıdır. Adaların düğümlerle, tünellerin kenarlarla modellendiği bu tam çizgede verilen algoritma çalıştırıldığında en küçük kapsayan ağacın içerdiği kenarların ağırlıkları toplamı 500500 olarak bulunur.
Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 9

[Soru 9-10 için açıklama]
İstanbul ve Ankara'da birer ofisi olan bir işletmeniz var. Her hafta, İstanbul ofisinde mi yoksa Ankara
ofisinde mi çalışmak istediğinize karar vermeniz gerekiyor. Haftaya bağlı olarak, işletmeniz sizin bir ofiste
veya diğerinde olmanızla daha fazla kar elde ediyor. Ek kısıt olarak, sürece İstanbul'da başlamalı ve
İstanbul'da bitirmelisiniz, ancak arada istediğiniz kadar kez gidip gelebilirsiniz. (1. Hafta Ankara’da
çalışacaksanız, önce İstanbul’dan Ankara’ya uçmanız gerekiyor, aynı şekilde, son hafta Ankara’da
çalışacaksanız, işiniz bitince Ankara’dan İstanbul’a uçmanız gerekiyor.) Daha fazla kar elde edeceğiniz
konumda çalışmayı tercih edersiniz, ancak bir ofisten diğerine uçmak 1000 TL tutuyor. (Bu harcamayı
kardan düşmeniz gerekiyor.) Konumunuza bağlı olarak haftalık kar tablosu size veriliyor.
Örneğin 4 haftalık bir süreç için kar (TL) tablosu aşağıdaki gibi olsun. Buna göre önce İstanbul’dan
Ankara'ya uçar 1. ve 2. Hafta Ankara’da çalışırsanız, sonra İstanbul’a uçup 3. ve 4. Hafta İstanbul'da
çalışırsanız, toplam kar- 1000 + (1000 + 1600)- 1000 + (2000 + 1000) = 3600 olur.

<table><tr><td></td><td>1. Hafta</td><td>2. Hafta</td><td>3. Hafta</td><td>4. Hafta</td></tr><tr><td>İstanbul</td><td>200</td><td>300</td><td>2000</td><td>1000</td></tr><tr><td>Ankara</td><td>1000</td><td>1600</td><td>700</td><td>500</td></tr></table>

Tabloyu temsil etmek üzere size n uzunluğunda iki dizi veriliyor, IS[1..n] ve AN[1..n], burada IS[i], i.
haftayı İstanbul'da geçirmekten elde edilen kardır ve AN[i], i. haftayı Ankara'da geçirmekten elde edilen
kardır. Örneğin yukardaki tablo için, n=4, IS: {200, 300, 2000, 1000}, ve AN: {1000, 1600, 700, 500}
olacaktır. Verilen bu iki diziye göre n. hafta sonunda yapabileceğiniz maksimum toplam karı belirlemek
istiyorsunuz. Bunun için aşağıdaki özyineli denklemleri kullanıyorsunuz.
Aşağıdaki denklemlerde,
0 ≤ i≤niçin, TIS (i)’nin i. hafta dahil olmak üzere ilk i haftanın planlaması için elde edilen maksimum karı
ifade ettiğini ve burada i. haftanın İstanbul'da geçirildiğini varsayalım.
Aynı şekilde TAN (i)'nin de i. hafta dahil olmak üzere ilk i haftanın planlaması için elde edilen maksimum
karı ifade ettiğini ve burada i. haftanın Ankara'da geçirildiğini varsayalım.
TIS (0) = 0
TAN(0) =-1000
TIS(i) = IS[i] + max(TIS(i−1), TAN(i−1)- 1000), 1 i n
≤ ≤
TAN(i) = AN[i] + max(TAN(i−1), TIS(i−1)- 1000), 1 i n
≤ ≤
Bu durumda, TIS(n) değeri n hafta sonunda elde edilebilecek maksimum toplam karı verir. (İstanbul'da
bitirmek istiyoruz).

---

n=5, IS: {400, 100, 200, 50, 1100}, ve AN: {210, 900, 100, 1500, 20} ise elde edilebilecek maksimum toplam kar olur?

Şıklar:
A) 2900 | B) 2810 | C) 2000 | D) 1920 | E) 1850

Cevap: B 2810

Çözüm:
Sırasıyla hesaplanırsa TIS(1)=400, TAN(1)=-790, TIS(2)=500, TAN(2)=300, TIS(3)=700, TAN(3)=400, TIS(4)=750, TAN(4)=1900, TIS(5)=2000 olur.
Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 10

[Soru 9-10 için açıklama]
İstanbul ve Ankara'da birer ofisi olan bir işletmeniz var. Her hafta, İstanbul ofisinde mi yoksa Ankara
ofisinde mi çalışmak istediğinize karar vermeniz gerekiyor. Haftaya bağlı olarak, işletmeniz sizin bir ofiste
veya diğerinde olmanızla daha fazla kar elde ediyor. Ek kısıt olarak, sürece İstanbul'da başlamalı ve
İstanbul'da bitirmelisiniz, ancak arada istediğiniz kadar kez gidip gelebilirsiniz. (1. Hafta Ankara’da
çalışacaksanız, önce İstanbul’dan Ankara’ya uçmanız gerekiyor, aynı şekilde, son hafta Ankara’da
çalışacaksanız, işiniz bitince Ankara’dan İstanbul’a uçmanız gerekiyor.) Daha fazla kar elde edeceğiniz
konumda çalışmayı tercih edersiniz, ancak bir ofisten diğerine uçmak 1000 TL tutuyor. (Bu harcamayı
kardan düşmeniz gerekiyor.) Konumunuza bağlı olarak haftalık kar tablosu size veriliyor.
Örneğin 4 haftalık bir süreç için kar (TL) tablosu aşağıdaki gibi olsun. Buna göre önce İstanbul’dan
Ankara'ya uçar 1. ve 2. Hafta Ankara’da çalışırsanız, sonra İstanbul’a uçup 3. ve 4. Hafta İstanbul'da
çalışırsanız, toplam kar- 1000 + (1000 + 1600)- 1000 + (2000 + 1000) = 3600 olur.

<table><tr><td></td><td>1. Hafta</td><td>2. Hafta</td><td>3. Hafta</td><td>4. Hafta</td></tr><tr><td>İstanbul</td><td>200</td><td>300</td><td>2000</td><td>1000</td></tr><tr><td>Ankara</td><td>1000</td><td>1600</td><td>700</td><td>500</td></tr></table>

Tabloyu temsil etmek üzere size n uzunluğunda iki dizi veriliyor, IS[1..n] ve AN[1..n], burada IS[i], i.
haftayı İstanbul'da geçirmekten elde edilen kardır ve AN[i], i. haftayı Ankara'da geçirmekten elde edilen
kardır. Örneğin yukardaki tablo için, n=4, IS: {200, 300, 2000, 1000}, ve AN: {1000, 1600, 700, 500}
olacaktır. Verilen bu iki diziye göre n. hafta sonunda yapabileceğiniz maksimum toplam karı belirlemek
istiyorsunuz. Bunun için aşağıdaki özyineli denklemleri kullanıyorsunuz.
Aşağıdaki denklemlerde,
0 ≤ i≤niçin, TIS (i)’nin i. hafta dahil olmak üzere ilk i haftanın planlaması için elde edilen maksimum karı
ifade ettiğini ve burada i. haftanın İstanbul'da geçirildiğini varsayalım.
Aynı şekilde TAN (i)'nin de i. hafta dahil olmak üzere ilk i haftanın planlaması için elde edilen maksimum
karı ifade ettiğini ve burada i. haftanın Ankara'da geçirildiğini varsayalım.
TIS (0) = 0
TAN(0) =-1000
TIS(i) = IS[i] + max(TIS(i−1), TAN(i−1)- 1000), 1 i n
≤ ≤
TAN(i) = AN[i] + max(TAN(i−1), TIS(i−1)- 1000), 1 i n
≤ ≤
Bu durumda, TIS(n) değeri n hafta sonunda elde edilebilecek maksimum toplam karı verir. (İstanbul'da
bitirmek istiyoruz).

---

n=7, IS: {200, 500, 1600, 800, 1800, 1200, 400}, ve AN: {1300, 1800, 400, 1500, 200, 1500, 500} ise TAN
(7) ne olur?

Şıklar:
A) 5800
B) 6300
C) 6400
D) 6500
E) 6900

Cevap: B 6300

Çözüm:
Sırasıyla hesaplanırsa TIS (1)=200, TAN(1)=300, TIS(2)=700, TAN(2)=2100, TIS(3)=2700, TAN(3)=2500,
TIS(4)=3500, TAN(4)=4000, TIS(5)=5300, TAN(5)=4200, TIS(6)=6500, TAN(6)=5800, ve TAN(7)=6300
olur.
Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 12

[GÖRSEL]
Yukarıdaki çizgede a düğümünden başlamak üzere derinlik öncelikli arama (DFS) algoritması çalıştırılırsa
düğümler aşağıdaki sıralamaların hangisi ile ziyaret edilebilir?

Şıklar:
A) a,b,c,d,e
B) a,b,d,c,e
C) a,c,d,e,b
D) a,c,b,d,e
E) a,d,e,c,b

Cevap: C a,c,d,e,b

Çözüm:
Derinlik Öncelikli Aramanın (DFS) a düğümünden başladığında ve bu düğüme geri gelmeden önce önce
her komşu düğüm boyunca mümkün olduğu kadar uzağa gider. Bu çizgede ilk olarak a düğümünden sonra
DFS, bu düğüme komşu olan c düğümüne geçebilir. DFS, c düğümünden d düğümüne ve ardından e
düğümüne geçmek zorundadır. Son olarak DFS, e düğümüne komşu olan b düğümünü ziyaret eder.
Dolayısıyla, şıklardan tek doğru ziyaret edilen düğüm sıralaması a,c,d,e,b dir.
Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 13

3-boyutlu (3B) bir nesne köşe noktaları ve köşelerden oluşan yüzeyler olarak tanımlanmıştır. Sağdaki şekilde 12 köşe noktası vardır (\(K = 12\)): \(V = \{v_1, v_2, ..., v_k, ..., v_k\}\). Her bir nokta \(x, y, z\) koordinatlarından oluşmaktadır: \(v_k = (x_k, y_k, z_k)\). Şeklin en üstteki yüzeyi 9, 10, 11 ve 12 numaralı köşelerden oluşmaktadır. Tamamen kapalı bir 3B nesne su-geçirmez olarak nitelendirilir. Sağdaki şekilde koyu gri bölgede bir yüzey olmadığı için 3B nesne su-geçirmez değildir. 3B bir nesnenin su-geçirmez olduğunu bulmak için aşağıdaki adımlardan hangisi gerekli değildir?
[GÖRSEL]

Şıklar:
A) Şekildeki yüzeyler z koordinatına göre orta noktası önden arkaya olacak şekilde sıralanır. | B) Şekildeki tüm yüzeyler tek tek gezilir. | C) Her bir yüzeyin içindeki köşe noktaları bir sonraki nokta ile eşleşerek kenarları tanımlayan çiftler oluşturulur. Örneğin (9, 10, 11, 12) yüzeyi için (9,10), (10,11), (11,12), (12,9) kenarları. | D) Kenarlar küçük olan köşe indeksi ilk olacak şekilde güncellenir. Örneğin (9,10) □ (9,10) ve (12,9) □ (9,12) | E) Kenarların kaç defa tekrar ettiği sayılır. Sadece tek defa tekrar etmiş bir kenar mevcutsa şekil su-geçirmez değildir.

Cevap: D Kenarlar küçük olan köşe indeksi ilk olacak şekilde güncellenir. Örneğin (9,10) □ (9,10) ve (12,9) □ (9,12)

Çözüm:
3B su-geçirmez bir şekilde her kenar iki yüzey tarafından paylaşılır. Dolayısıyla tüm yüzeylerdeki kenarlar bulunarak her bir kenarın kaçar defa kullanıldığı sayıldığında tek defa kullanılan kenar tek yüzeyde mevcut demektir. İki yüzey tarafından paylaşılmayan ve tek defa kullanılan bir kenar mevcutsa 3B şekil su-geçirmez değildir. Şıklarda (B)-(E) adımları tek defa kullanılan kenar var mı sorusunun cevabını bulduğu için 3B şeklin su-geçirmez olduğunun anlaşılması için bu adımlar yeterlidir. Bu işlemler için yüzeylerin hangi sıra ile gezildiğinin bir önemi olmadığından yüzeylerin sıralanması gereksizdir.
Genişlik Öncelikli Arama (DFS) başlangıç düğümünün önce komşularını daha sonra onların komşularını seviye seviye gezer. Bu çizgede ilk olarak a düğümünden sonra BFS, bu düğüme komşu olan b ve c düğümünü bu sırada gezebilir. İkinci seviyede sırasıyla b'ye ve daha sonra c'ye komşu olan düğümler gezilecektir. Yani, d ve f düğümleri gezilir. Daha sonra 3. seviyede e ve g düğümleri ve son olarak 4. seviyede h düğümü gezilir.
Dolayısıyla, şıklardan tek doğru ziyaret edilen düğüm sıralaması a,b,c,d,f,e,g,h'dir.
Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 14

[GÖRSEL]
Yukarıdaki çizgede a düğümünden başlamak üzere genişlik öncelikli arama (BFS) algoritması çalıştırılırsa
düğümler aşağıdaki sıralamaların hangisi ile ziyaret edilebilir?

Şıklar:
A) a,b,c,d,e,f,g,h
B) a,b,c,d,e,g,f,h
C) a,b,c,f,d,e,h,g
D) a,b,c,d,f,e,g,h
E) a,b,c,d,e,g,h,f

Cevap: D a,b,c,d,f,e,g,h

Çözüm:
Genişlik Öncelikli Arama (DFS) başlangıç düğümünün önce komşularını daha sonra onların komşularını
seviye seviye gezer. Bu çizgede ilk olarak a düğümünden sonra BFS, bu düğüme komşu olan b ve c
düğümünü bu sırada gezebilir. İkinci seviyede sırasıyla b’ye ve daha sonra c’ye komşu olan düğümler
gezilecektir. Yani, d ve f düğümleri gezilir. Daha sonra 3. seviyede e ve g düğümleri ve son olarak 4.
seviyede h düğümü gezilir.
Dolayısıyla, şıklardan tek doğru ziyaret edilen düğüm sıralaması a,b,c,d,f,e,g,h’dir.
Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 15

n tane düğümü ve e tane kenarı olan yönsüz bir çizge G çizgesini göz önüne alın. G'yi temsil etmek için kullanılan komşuluk matrisindeki 1'lerin toplam sayısı aşağıdakilerden hangisidir? (G'nin basit olduğunu yani G'deki herhangi iki düğüm arasında en fazla bir tane kenar olduğunu varsayınız.)

Şıklar:
A) n | B) 2n | C) e | D) 2e | E) n+e

Cevap: D 2e

Çözüm:
Yönsüz bir çizgenin komşuluk matrisinde, 'i' düğümü ile 'j' düğümü arasında bir kenar varsa, matristeki (i, j) ve (j, i) konumundaki elemanların her ikisi de 1 olarak işaretlenir. 'u. Bu nedenle, her kenar komşuluk matrisinde iki tane 1 ile gösterilir. Dolayısıyla, komşuluk matrisindeki tüm 1'lerin toplam sayısı 2e olacaktır.
Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 16

Şekilde bir deniz canlısının ağırlık dağılımı gösterilmektedir. Bu canlı 2 kilogram ile 250 kilogram arasında ağırlıklarda olmaktadır. Bu deniz canlısı en yoğun olarak 130 kilogram civarı (en yüksek frekans) olmaktadır. Şekilde de (histogramda) görüldüğü üzere bu canlı ağırlıklarına göre 4 yoğun gruba bölünmüştür. Histogram verisi bir dizi içinde tam sayılar (frekanslar) olarak saklanmaktadır. Bu tip bir histogram verisi için aşağıdakilerden hangisi dizinin üzerinden tek bir defa gezerek bulunamaz?
[GÖRSEL]

Şıklar:
A) En yüksek frekans değeri | B) Bu canlının tüm üyelerinin toplam ağırlığı | C) Medyan (dizi sıralı ise ortada olan) frekans değeri | D) X-aksi boyunca frekansın sabit kaldığı en uzun aralık | E) En düşük frekans haricindeki frekansların ortalaması

Cevap: C Medyan (dizi sıralı ise ortada olan) frekans değeri

Çözüm:
En yüksek frekans değeri dizinin içindeki en büyük değeri bulma işlemidir ve dizi tek bir defa gezilerek bulunur. Canlının tüm üyelerinin ağırlığı dizinin elemanlarının toplamına eşittir ve dizi üzerinde tek defa gezilerek bulunur.  X-aksi boyunca frekansın sabit kaldığı aralığı bulmak için dizi üzerinde ilerlerken en son frekans aynı olduğu sürece bir sayaç arttırılır ve bu sayacın en büyük değeri bir değişkende tutulur. Dizide döngüde bakılan frekans en son frekanstan farklı ise sayaç sıfırlanır. Dolayısıyla x-aksi boyunca frekansın sabit kaldığı en uzun aralcı dizi tek bir defa gezilerek bulunabilir. Tüm frekansların ortalaması dizi toplamının dizideki eleman sayısına bölümüdür. En düşük frekans haricindeki frekansların ortalamasını bulmak için dizi tek bir defa gezilirken frekanslar toplamı, en düşük frekans ve en düşük frekansın kaç defa tekrar ettiği bulunur. En düşük frekans tekrar adedi ile çarpılarak bulunan toplamdan çıkarılır ve dizideki eleman sayısından en düşük frekans tekrar adedinin çıkarılmış haline bölünür. Böylece dizi tek bir defa gezilerek en düşük frekans haricindeki frekansların ortalaması bulunmuş olur. Medyan bulma işlemi dizi üzerinde tek bir defa gezip bulunamaz. En verimsiz şekilde yapılacak olursa dizinin sıralanması gerekir. Medyan değeri bulmak için kullanılabilecek en hızlı yöntemlerden biri olan quick-select yöntemi bile sonucu dizi üzerinde tek bir defa gezerek elde etmeyi garanti etmez.
Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 17

Şekilde en solda 5x5 boyutunda bir dama tahtası üzerinde taşlar (tahta-taş dizilimi) gösterilmektedir. Bir taş bir başka taşın üzerinden atlayabilir ve birden fazla atlama işlemi yapabilir. Soldaki tahta-taş diziliminden pek çok farklı hamleler yapılsa bile ancak sağdaki 6 tahta-taş dizilimi elde edilebilir. Verilen bir tahta-taş dizilimi için olası tüm hamleler yapıldığında elde edilebilecek farklı tahta-taş dizilimlerini bulabilmek için aşağıda şıklarda ifade edilen adımlardan hangisi doğru değildir?
[GÖRSEL]

Şıklar:
A) Her bir tahta-taş dizilimi tahtanın her bir hücresinde var/yok tutan bir veri tipi ile 2 boyutlu bir dizi oluşturularak ifade edilir (örneğin şekilde en soldaki tahta). | B) Bir tahta-taş dizilimi için seçilen bir taşın tek defa atlayarak oluşturabileceği tüm tahta-taş dizilimlerini 2 boyutlu tahta-taş dizileri olarak veren bir metoda ihtiyaç vardır. | C) Tahta-taş dizilimlerinin tekrarlı olmaması için set veri yapısı kullanılır. Matematiksel olarak bir set içinde bir veriden sadece bir tane bulundurabilir. | D) Her bir taş için yapılacak hamleler B maddesindeki metot ile alınır. Her bir taş için yapılacak hamleler sonucu elde edilecek tahta-taş dizilimlerinden set içinde olmayanlar için C maddesi yinelemeli olarak çalıştırılır. Set içinde olmayan tahta-taş dizilmleri set’e eklenir. | E) Tahta-taş dizilimleri tek bir referans değişkeni ile tutulabilir.

Cevap: E Tahta-taş dizilimleri tek bir referans değişkeni ile tutulabilir.

Çözüm:
Bir-tahta taş diziliminde seçilen bir taş hareket ettirildiğinde yeni bir tahta-taş dizilimi dizisi oluşturulmalıdır. Bu amaçla tahta-taş dizisinin klonu oluşturulup sonra klon üzerinde hamle uygulanır. Dolayısı ile her bir tahta-taş dizilimi ayrı bir nesne ve ayrı bir referans ile adreslenir.
Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 18

AKSARAY kelimesindeki harfleri yer değiştirerek anlamlı ya da anlamsız 7 harfli kaç kelime oluşturulabilir?

Şıklar:
A) 840 | B) 1260 | C) 1680 | D) 2520 | E) 5040

Cevap: A 840

Çözüm:
7 harf toplam 7! şekilde sıralanabilir. AKSARAY kelimesinde A harfi 3 defa geçmektedir. Bu harfler kendi aralarında 3! şekilde sıralanabilirler. Dolayısıyla cevap \(\frac{7!}{3!} = 840\)'dır.
Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 20

8X8'lik bir dama tahtasında toplam kaç adet kare vardır?

Şıklar:
A) 65
B) 204
C) 256
D) 1296
E) 4096

Cevap: B 204

Çözüm:
\color{green}{1} \times 1’lik kare sayısı \( 8 \times 8 = 64 \)’tür. \( 2 \times 2 \)’lik kare sayısı \( 7 \times 7 = 49 \)’dur. Genel olarak \( 1 \le i \le 8 \) olmak üzere \( i \times i \)’lik kare sayısı \( (9 - i)^2 \)’dir. Bu yüzden cevap \( \sum_{i=1}^{8} i^2 = \frac{8 \times 9 \times 17}{6} = 204 \)’tür.
Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 21

A kümesi 6'ya bölünebilen 3 basamaklı pozitif tamsayıların kümesidir. B kümesi ise 4'e bölünüp 8'e bölünemeyen 3 basamaklı pozitif tamsayıların kümesidir.
AUB kümesi kaç elemanlıdır?

Şıklar:
A) 224 | B) 225 | C) 263 | D) 265 | E) 300

Cevap: B 225

Çözüm:
A kümesinin en küçük elemanı 6×17 = 102, en büyük elemanı ise 6×166 = 996'dır. A kümesinin elemanları altışar altışar artmaktadır. Yani \(A = \{102, 108, ..., 996\}\)'dır. A kümesi \(\frac{996-102}{6} + 1 = 150\) elemandan oluşmaktadır.
B kümesinin en küçük elemanı 4×25 = 100, en büyük elemanı ise 4×249 = 996'dır. B kümesinin elemanları sekizer sekizer artmaktadır. Yani \(B = \{100, 108, ..., 996\}\)'dır. B kümesi \(\frac{996-100}{8} + 1 = 113\) elemandan oluşmaktadır.
A∩B kümesinin en küçük elemanı yukarıdan görülebileceği gibi 108'dir. Bu kümenin elemanları 24'er 24'er artmaktadır. Bunun sebebi 6 ile 8'in en küçük ortak katının 24 olmasıdır. Yani \(A \cap B = \{108, 132, ..., 996\}\)'dır. A∩B kümesi \(\frac{996-108}{24} + 1 = 38\) elemandan oluşmaktadır.
Öyleyse, AUB kümesinin eleman sayısı 150 + 113 - 38 = 225'dir.
Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 22

Yönlü ve döngüsüz bir çizgede, bir u düğümünden v düğümüne giden her yönlü kenar için u‘nun v'den önce gelecek şekilde sıralanması işlemine ne denir?

Şıklar:
A) Derinlik öncelikli arama ile sıralama | B) Genişlik öncelikli arama ile sıralama | C) İlk sıra gezisi (preorder traversal) ile sıralama | D) Son sıra gezisi (postorder traversal) ile sıralama | E) Topolojik sıralama

Cevap: E Topolojik sıralama

Çözüm:
Bu işlemin literatürde topolojik sıralama olarak bilinir.