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

## [22-24 soruları için ek açıklama]
Bir süre durumu izleyen Kermit, sihirli taşların üzerindeki sayıların zaman zaman değiştiğini görüyor. Kermit, bu değişimin en baştaki taşın sayısı değişirken gerçekleştiğini görüyor. En baştaki sayı çıkarılınca, en sonda bulunan taştaki sayı en başa geliyor. Bu durum kuralı bozabileceği için o taştan gidilebilecek her iki taş da kontrol ediliyor, ve eğer sayılar mevcut taştaki sayıdan büyükse, büyük olanla sayı yer değiştiriyor. Eğer her ikisi de büyükse, o durumda büyük olan sayı ile yer değişikliği yapılıyor. Böylelikle en yukarıya taşınan sayı kuralı bozmayacak şekilde en sona doğru hareket ediyor.

---

Taşların sırası – 60, 50, 29, 17, 41, 6, 20, 5, 2, 32 – durumunda iken, Kermit ilk taşın çıkarılmasına denk gelince son durumda taşlar nasıl olacaktır?

Şıklar:
A) 50, 29, 17, 41, 6, 20, 52, 32 | B) 32, 50, 29, 17, 41, 6, 20,5,2 | C) 29, 50, 32, 17, 41, 6, 20, 52 | D) 50, 32, 29, 17, 41, 6, 20, 52 | E) 50, 41, 29, 17, 32, 6, 20, 52

Cevap: E 50, 41, 29, 17, 32, 6, 20, 52

Çözüm:
Taşların hareketleri 32-60, 32-50, 32-41 olacağından cevap E şıkkı olur.
Bilgisayar Olimpiyatı 2019, 1. Aşama, Soru 23

## [22-24 soruları için ek açıklama]
Bir süre durumu izleyen Kermit, sihirli taşların üzerindeki sayıların zaman zaman değiştiğini görüyor. Kermit, bu değişimin en baştaki taşın sayısı değişirken gerçekleştiğini görüyor. En baştaki sayı çıkarılınca, en sonda bulunan taştaki sayı en başa geliyor. Bu durum kuralı bozabileceği için o taştan gidilebilecek her iki taş da kontrol ediliyor, ve eğer sayılar mevcut taştaki sayıdan büyükse, büyük olanla sayı yer değiştiriyor. Eğer her ikisi de büyükse, o durumda büyük olan sayı ile yer değişikliği yapılıyor. Böylelikle en yukarıya taşınan sayı kuralı bozmayacak şekilde en sona doğru hareket ediyor.

---

22. sorudaki çıkarma işleminde kaç kere taş değişikliği yapılmıştır?

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

Cevap: C 3

Çözüm:
3 adet değiştirme işlemi gerçekleştirilir: 32-60, 32-50 ve 32-41.
Bilgisayar Olimpiyatı 2019, 1. Aşama, Soru 24

## [22-24 soruları için ek açıklama]
Bir süre durumu izleyen Kermit, sihirli taşların üzerindeki sayıların zaman zaman değiştiğini görüyor. Kermit, bu değişimin en baştaki taşın sayısı değişirken gerçekleştiğini görüyor. En baştaki sayı çıkarılınca, en sonda bulunan taştaki sayı en başa geliyor. Bu durum kuralı bozabileceği için o taştan gidilebilecek her iki taş da kontrol ediliyor, ve eğer sayılar mevcut taştaki sayıdan büyükse, büyük olanla sayı yer değiştiriyor. Eğer her ikisi de büyükse, o durumda büyük olan sayı ile yer değişikliği yapılıyor. Böylelikle en yukarıya taşınan sayı kuralı bozmayacak şekilde en sona doğru hareket ediyor.

---

Taşların sırası – 60, 50, 29, 17, 41, 6, 20, 5, 2, 32 – durumunda iken, üç kere taş çıkarma işlemi gerçekleşirse son durumda taşlar nasıl olacaktır?

Şıklar:
A) 17, 41, 6, 20, 5, 2, 3 | B) 29, 17, 6, 20, 5, 32, 2 | C) 32, 17, 29, 20, 6, 5, 2 | D) 17, 20, 6, 2, 5, 32, 29 | E) 32, 17, 29, 5, 2, 6, 20

Cevap: E 32, 17, 29, 5, 2, 6, 20

Çözüm:
Birinci adım sonrası: 50, 41, 29, 17, 32, 6, 20, 5, 2
İkinci adım sonrası: 41,32,29,17,2,6,20,5
Üçüncü adım sonrası: 32, 17, 29, 5, 2, 6, 2
Bilgisayar Olimpiyatı 2019, 1. Aşama, Soru 25

## [25-28 soruları için açıklama]
Ünlü bir iş kadını olan Zeynep müşterilerinin taleplerine yetişemeyecek kadar çok fazla sipariş almaya başlamıştır. Her bir sipariş için önceden belirlenen bir iş süreci bulunmaktadır, dolayısıyla Zeynep her bir işin kaç gün süreceğini biliyor. Zeynep en kısa işleri ilk başta yapmayı ve sonra diğerleriyle uğraşmayı daha doğru buluyor. Zeynep kendince üç farklı algoritma geliştiriyor:
1- Zeynep bütün işleri art arda koyup ikinci işten başlıyor. Daha önceki işin süresiyle kıyaslamasını yapıyor. Eğer daha önce yer alan işin süresi küçükse herhangi bir değişiklik yapmayıp, sıradaki işi yerleştirmeye çalışıyor. Eğer bir önceki iş daha büyükse, o zaman her iki işin yerini değiştirip, kendisinden daha büyük olmayan bir işle karşılaşana kadar aynı işlemi tekrar ediyor. Böylelikle, incelemeye aldığı yeni işten önceki işleri kendi arasında karşılaştırmış oluyor.
2- Zeynep tüm işleri yine art arda yazıyor. Baştan sona tüm listeyi kontrol edip en küçük işi buluyor. Onu en baştaki işle değiştiriyor, ve bir sonra gelecek işi bulmak için aynı işlemi tekrar ediyor. Eğer en baştaki iş en kısa sürecek iş ise, bu durumda değiştirme işlemi yapılmıyor.
3- Akıllı bir kadın olan Zeynep, listeyi ortadan ikiye bölüp her parçayı kendi arasında çözmenin işe yarayabileceğini düşünüyor. İkiye bölebilmesi için ortadaki elemanı bulması gerekiyor (Eğer tek sayıda eleman varsa her böldüğünde kalanı da dahil ederek bölünecek yeri belirliyor, örneğin 5/2=3). Eğer bu bölme işlemini elinde birer iş kalana kadar yaparsa, hangisinin daha kısa süreceğini anlaması zor olmayacaktır. Bu işlerin hangi sırayla yapılacağını her bir alt listede karar verirse, bir önceki adımda bölünmüş iş listesiyle birleştirmesi oldukça kolay olacaktır. Zeynep tüm listeyi bu şekilde bölüp, daha sonra en alttan birleştire birleştire yukarıya doğru giderek işlerin hangi sırayla yapılacağına karar verebilir.
25-28 numaralı soruları aşağıda süreleri verilen iş listesine göre cevaplayınız:
16, 45, 37, 28, 15, 12, 21, 44, 48, 40, 41

---

1 numaralı algoritma kullanılırsa kaç adet yer değiştirme işlemi uygulanır?

Şıklar:
A) 18 | B) 20 | C) 22 | D) 24 | E) 26

Cevap: C 22

Çözüm:
Toplam 22 yer değiştirme işlemi yapılır:
45 için 0
37 için 1
28 için 2
15 için 4
12 için 5
21 için 3
44 için 1
48 için 0
40 için 3
41 için 3
Bilgisayar Olimpiyatı 2019, 1. Aşama, Soru 26

2 numaralı algoritma kullanılırsa kaç adet yer değiştirme işlemi uygulanır?

Şıklar:
A) 2 
B) 4 
C) 6 
D) 8 
E) 10

Cevap: D 8

Çözüm:
Toplam 8 yer değiştirme işlemi yapılır.  
1.index için  
12-16 12, 45, 37, 28, 15, 16, 21, 44, 48, 40, 41 
2.index için 
3.index için 
4.index için 
5.index için 
6.index için 
7.index için 
8.index için 
9.index için 
15-45 12, 15, 37, 28, 45, 16, 21, 44, 48, 40, 41 
16-37 12, 15, 16, 28, 45, 37, 21, 44, 48, 40, 41 
21-28 12, 15, 16, 21, 45, 37, 28, 44, 48, 40, 41 
28-45 12, 15, 16, 21, 28, 37, 45, 44, 48, 40, 41 - 
12, 15, 16, 21, 28, 37, 45, 44, 48, 40, 41 
40-45 12, 15, 16, 21, 28, 37, 40, 44, 48, 45, 41 
41-44 12, 15, 16, 21, 28, 37, 40, 41, 48, 45, 44 
44-48 12, 15, 16, 21, 28, 37, 40, 41, 44, 45, 48 
10.index için - 
12, 15, 16, 21, 28, 37, 40, 41, 44, 45, 48 
11.index için -
Bilgisayar Olimpiyatı 2019, 1. Aşama, Soru 27

## [25-28 soruları için açıklama]
Ünlü bir iş kadını olan Zeynep müşterilerinin taleplerine yetişemeyecek kadar çok fazla sipariş almaya başlamıştır. Her bir sipariş için önceden belirlenen bir iş süreci bulunmaktadır, dolayısıyla Zeynep her bir işin kaç gün süreceğini biliyor. Zeynep en kısa işleri ilk başta yapmayı ve sonra diğerleriyle uğraşmayı daha doğru buluyor. Zeynep kendince üç farklı algoritma geliştiriyor:
1- Zeynep bütün işleri art arda koyup ikinci işten başlıyor. Daha önceki işin süresiyle kıyaslamasını yapıyor. Eğer daha önce yer alan işin süresi küçükse herhangi bir değişiklik yapmayıp, sıradaki işi yerleştirmeye çalışıyor. Eğer bir önceki iş daha büyükse, o zaman her iki işin yerini değiştirip, kendisinden daha büyük olmayan bir işle karşılaşana kadar aynı işlemi tekrar ediyor. Böylelikle, incelemeye aldığı yeni işten önceki işleri kendi arasında karşılaştırmış oluyor.
2- Zeynep tüm işleri yine art arda yazıyor. Baştan sona tüm listeyi kontrol edip en küçük işi buluyor. Onu en baştaki işle değiştiriyor, ve bir sonra gelecek işi bulmak için aynı işlemi tekrar ediyor. Eğer en baştaki iş en kısa sürecek iş ise, bu durumda değiştirme işlemi yapılmıyor.
3- Akıllı bir kadın olan Zeynep, listeyi ortadan ikiye bölüp her parçayı kendi arasında çözmenin işe yarayabileceğini düşünüyor. İkiye bölebilmesi için ortadaki elemanı bulması gerekiyor (Eğer tek sayıda eleman varsa her böldüğünde kalanı da dahil ederek bölünecek yeri belirliyor, örneğin 5/2=3). Eğer bu bölme işlemini elinde birer iş kalana kadar yaparsa, hangisinin daha kısa süreceğini anlaması zor olmayacaktır. Bu işlerin hangi sırayla yapılacağını her bir alt listede karar verirse, bir önceki adımda bölünmüş iş listesiyle birleştirmesi oldukça kolay olacaktır. Zeynep tüm listeyi bu şekilde bölüp, daha sonra en alttan birleştire birleştire yukarıya doğru giderek işlerin hangi sırayla yapılacağına karar verebilir.
25-28 numaralı soruları aşağıda süreleri verilen iş listesine göre cevaplayınız:
16, 45, 37, 28, 15, 12, 21, 44, 48, 40, 41

---

3 numaralı algoritma kullanılırsa elimizde karşılaştırmak için birer iş olarak 16 ve 45 kalana kadar kaç adet bölme işlemi uygulanır?

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

Cevap: D 4

Çözüm:
Toplam 4 bölme işlemi yapılır:
1. bölme işlemi sonucu - 16, 45, 37, 28, 15, 12 ve 21, 44, 48, 40, 41
2. bölme işlemi sonucu - 16, 45, 27 ve 28,15,12
3. bölme işlemi sonucu - 16,45 ve 37
4. bölme işlemi sonucu - 16 ve 45
Bilgisayar Olimpiyatı 2019, 1. Aşama, Soru 28

## [25-28 soruları için açıklama]
Ünlü bir iş kadını olan Zeynep müşterilerinin taleplerine yetişemeyecek kadar çok fazla sipariş almaya başlamıştır. Her bir sipariş için önceden belirlenen bir iş süreci bulunmaktadır, dolayısıyla Zeynep her bir işin kaç gün süreceğini biliyor. Zeynep en kısa işleri ilk başta yapmayı ve sonra diğerleriyle uğraşmayı daha doğru buluyor. Zeynep kendince üç farklı algoritma geliştiriyor:
1- Zeynep bütün işleri art arda koyup ikinci işten başlıyor. Daha önceki işin süresiyle kıyaslamasını yapıyor. Eğer daha önce yer alan işin süresi küçükse herhangi bir değişiklik yapmayıp, sıradaki işi yerleştirmeye çalışıyor. Eğer bir önceki iş daha büyükse, o zaman her iki işin yerini değiştirip, kendisinden daha büyük olmayan bir işle karşılaşana kadar aynı işlemi tekrar ediyor. Böylelikle, incelemeye aldığı yeni işten önceki işleri kendi arasında karşılaştırmış oluyor.
2- Zeynep tüm işleri yine art arda yazıyor. Baştan sona tüm listeyi kontrol edip en küçük işi buluyor. Onu en baştaki işle değiştiriyor, ve bir sonra gelecek işi bulmak için aynı işlemi tekrar ediyor. Eğer en baştaki iş en kısa sürecek iş ise, bu durumda değiştirme işlemi yapılmıyor.
3- Akıllı bir kadın olan Zeynep, listeyi ortadan ikiye bölüp her parçayı kendi arasında çözmenin işe yarayabileceğini düşünüyor. İkiye bölebilmesi için ortadaki elemanı bulması gerekiyor (Eğer tek sayıda eleman varsa her böldüğünde kalanı da dahil ederek bölünecek yeri belirliyor, örneğin 5/2=3). Eğer bu bölme işlemini elinde birer iş kalana kadar yaparsa, hangisinin daha kısa süreceğini anlaması zor olmayacaktır. Bu işlerin hangi sırayla yapılacağını her bir alt listede karar verirse, bir önceki adımda bölünmüş iş listesiyle birleştirmesi oldukça kolay olacaktır. Zeynep tüm listeyi bu şekilde bölüp, daha sonra en alttan birleştire birleştire yukarıya doğru giderek işlerin hangi sırayla yapılacağına karar verebilir.
25-28 numaralı soruları aşağıda süreleri verilen iş listesine göre cevaplayınız:
16, 45, 37, 28, 15, 12, 21, 44, 48, 40, 41

---

3 numaralı algoritma kullanılırsa kaç adet birleştirme işlemi uygulanır?

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

Cevap: D 10

Çözüm:
Cevap n-1 yani 10’dur.
[GÖRSEL]
Bilgisayar Olimpiyatı 2019, 1. Aşama, Soru 29

## [29-30 soruları için açıklama]
Uzun uğraşlar sonucunda bilim adamları ışınlanmayı buldular ve dünyayı büyük bir saldırıdan kurtaracak olan mücevheri bulmak üzere K642 isimli gezegene gittiler. Efsanelerden ve haritalardan çıkardıklarına göre bu mücevher uzun bir köprünün herhangi bir noktasında bulunmaktadır. Arama işlemi başlangıç noktasından başlayıp köprünün diğer ucu baz alınacak şekilde gerçekleştirilecektir. Fakat ışınlanma teknolojisinin çok fazla enerji tükettiği bilindiğinden, çeşitli kısıtlamalar getirilmiştir. Buna göre astronot bulunduğu pozisyondan ileriye dönüp en son erişilen yolun yarısına kadar, ya da geriye dönüp en son erişilen yolun yarısına kadar ışınlanabilmektedir. Her ışınlandığı pozisyonda özel yapılan arama cihazı sayesinde mücevherin daha ileride mi olduğu yoksa geride mi kaldığı net bir şekilde belirlenebilmektedir.

---

Eğer açıklamalarda belirtilen köprünün uzunluğu 100.000 birim olursa en fazla kaç kere ışınlanarak mücevher bulunabilir?

Şıklar:
A) 14 | B) 15 | C) 16 | D) 17 | E) 18

Cevap: D 17

Çözüm:
Cevap [log2 100.000] = 17.
Bilgisayar Olimpiyatı 2019, 1. Aşama, Soru 30

## [29-30 soruları için açıklama]
Uzun uğraşlar sonucunda bilim adamları ışınlanmayı buldular ve dünyayı büyük bir saldırıdan kurtaracak olan mücevheri bulmak üzere K642 isimli gezegene gittiler. Efsanelerden ve haritalardan çıkardıklarına göre bu mücevher uzun bir köprünün herhangi bir noktasında bulunmaktadır. Arama işlemi başlangıç noktasından başlayıp köprünün diğer ucu baz alınacak şekilde gerçekleştirilecektir. Fakat ışınlanma teknolojisinin çok fazla enerji tükettiği bilindiğinden, çeşitli kısıtlamalar getirilmiştir. Buna göre astronot bulunduğu pozisyondan ileriye dönüp en son erişilen yolun yarısına kadar, ya da geriye dönüp en son erişilen yolun yarısına kadar ışınlanabilmektedir. Her ışınlandığı pozisyonda özel yapılan arama cihazı sayesinde mücevherin daha ileride mi olduğu yoksa geride mi kaldığı net bir şekilde belirlenebilmektedir.

---

Köprü uzunluğu 100 birim ve mücevher 68. pozisyonda ise astronot kaç kere ileriye, kaç kere geriye doğru ışınlanmıştır?

Şıklar:
A) 3 ileri, 1 geri | B) 3 ileri, 2 geri | C) 4 ileri, 2 geri | D) 4 ileri, 1 geri | E) 4 ileri, 0 geri

Cevap: C 4 ileri, 2 geri

Çözüm:
Cevap 4 ileri 2 geridir.
\[1 \rightarrow 50 \quad \text{ileri}\]
\[50 \rightarrow 75 \quad \text{ileri}\]
\[75 \rightarrow 62 \quad \text{geri}\]
\[62 \rightarrow 69 \quad \text{ileri}\]
\[69 \rightarrow 66 \quad \text{geri}\]
\[66 \rightarrow 68 \quad \text{ileri}\]
Bilgisayar Olimpiyatı 2019, 1. Aşama, Soru 31

## [31-35 soruları için açıklama]
Verilen bir **S** karakter dizisinin içinde daha küçük bir **P** dizisinin karakterleri sırayla fakat ardışık olma şartı olmadan geçiyorsa bu durumu **gizli alt-dizi** olarak adlandırmaktayız. Mesela aşağıdaki **S** dizisinde
### gmtcoarbbhpoheaccvbttya
12345678901234567890123
**merhaba** dizisi [2,4,7,10,15,19,23] indislerinde gizli alt-dizi olarak geçmektedir. Aynı **merhaba** dizisi ayrıca [2,4,7,13,15,19,23] indislerinde de gizli alt-dizi olarak geçmektedir. Verilen bir **P** dizisinin bir **S** dizisi içinde kaç kez gizli alt-dizi olarak geçtiğini aşağıdaki özyineli yöntem ile bulabiliriz. **F(i,j)** fonksiyonu **P** dizisinin ilk **i** karakterinin **S** dizisinin ilk **j** karakteri içinde kaç kez gizli alt-dizi olarak geçtiğini göstersin. |**P**| de bir dizideki karakter sayısını ve **P[i]** **P** dizisinin **i**. karakterini göstersin.
\[F(0,0) = 1\]
\[F(i,0) = 0 \quad 1'den |P|'ye kadar olan i değerleri için\]
\[F(0,j) = 1 \quad 1'den |S|'ye kadar olan j değerleri için\]
\[F(i,j) = F(i,j-1) \text{ eğer } P[i] S[j]'den farklı ise\]
\[F(i,j) = F(i-1,j-1) + F(i,j-1) \text{ eğer } P[i] \text{ ve } S[j] \text{ aynı karakter ise}\]
Bir **P** dizisinin bir **S** dizisi içinde kaç kez gizl i alt-dizi olarak geçtiğini bulmak için **F(|P|,|S|)** değerini hesaplamak yeterli olacaktır.
Sadece ‘A’ karakterlerinden oluşan **M** uzunluğundaki bir dizide sadece ‘A’ karakterlerinden oluşan **N** uzunluğundaki bir dizi kaç kez gizli alt-dizi olarak geçer?
A) **M**!
B) **N**!
C) **M**! / **N**!
D) **M**! / ((**M**-**N**)!-**N**!)
E) **M**!-**N**!
Aynı karakterlerden oluşan iki dizi verildiğinde küçük dizinin büyük dizi içerisinde kaç kez gizli alt-dizi olarak bulunduğu sorusu “M adet karakter içinde kaç farklı şekilde N adet karakter seçebiliriz?” sorusu ile aynı soru haline gelir. Bu da **M**’nin **N**’li kombinasyonuna eşittir yani cevap D şıkkıdır.

---

Sadece ‘A’ karakterlerinden oluşan M uzunluğundaki bir dizide sadece ‘A’ karakterlerinden oluşan N 
uzunluğundaki bir dizi kaç kez gizli alt-dizi olarak geçer?

Şıklar:
A) M! 
B) N! 
C) M! / N! 
D) M! / ((M-N)!∙N!) 
E) M!∙N!

Cevap: D M! / ((M-N)!∙N!)

Çözüm:
Aynı karakterlerden oluşan iki dizi verildiğinde küçük dizinin büyük dizi içerisinde kaç kez gizli alt-dizi olarak 
bulunduğu sorusu “M adet karakter içinde kaç farklı şekilde N adet karakter seçebiliriz?” sorusu ile aynı soru 
haline gelir. Bu da M’nin N’li kombinasyonuna eşittir yani cevap D şıkkıdır.
Bilgisayar Olimpiyatı 2019, 1. Aşama, Soru 33

## [31-35 soruları için açıklama]
Verilen bir **S** karakter dizisinin içinde daha küçük bir **P** dizisinin karakterleri sırayla fakat ardışık olma şartı olmadan geçiyorsa bu durumu **gizli alt-dizi** olarak adlandırmaktayız. Mesela aşağıdaki **S** dizisinde
### gmtcoarbbhpoheaccvbttya
12345678901234567890123
**merhaba** dizisi [2,4,7,10,15,19,23] indislerinde gizli alt-dizi olarak geçmektedir. Aynı **merhaba** dizisi ayrıca [2,4,7,13,15,19,23] indislerinde de gizli alt-dizi olarak geçmektedir. Verilen bir **P** dizisinin bir **S** dizisi içinde kaç kez gizli alt-dizi olarak geçtiğini aşağıdaki özyineli yöntem ile bulabiliriz. **F(i,j)** fonksiyonu **P** dizisinin ilk **i** karakterinin **S** dizisinin ilk **j** karakteri içinde kaç kez gizli alt-dizi olarak geçtiğini göstersin. |**P**| de bir dizideki karakter sayısını ve **P[i]** **P** dizisinin **i**. karakterini göstersin.
\[F(0,0) = 1\]
\[F(i,0) = 0 \quad 1'den |P|'ye kadar olan i değerleri için\]
\[F(0,j) = 1 \quad 1'den |S|'ye kadar olan j değerleri için\]
\[F(i,j) = F(i,j-1) \text{ eğer } P[i] S[j]'den farklı ise\]
\[F(i,j) = F(i-1,j-1) + F(i,j-1) \text{ eğer } P[i] \text{ ve } S[j] \text{ aynı karakter ise}\]
Bir **P** dizisinin bir **S** dizisi içinde kaç kez gizl i alt-dizi olarak geçtiğini bulmak için **F(|P|,|S|)** değerini hesaplamak yeterli olacaktır.
Sadece ‘A’ karakterlerinden oluşan **M** uzunluğundaki bir dizide sadece ‘A’ karakterlerinden oluşan **N** uzunluğundaki bir dizi kaç kez gizli alt-dizi olarak geçer?
A) **M**!
B) **N**!
C) **M**! / **N**!
D) **M**! / ((**M**-**N**)!-**N**!)
E) **M**!-**N**!
Aynı karakterlerden oluşan iki dizi verildiğinde küçük dizinin büyük dizi içerisinde kaç kez gizli alt-dizi olarak bulunduğu sorusu “M adet karakter içinde kaç farklı şekilde N adet karakter seçebiliriz?” sorusu ile aynı soru haline gelir. Bu da **M**’nin **N**’li kombinasyonuna eşittir yani cevap D şıkkıdır.

---

‘ABCCBAABCCBA’ dizisinde ‘ABC’ dizisi kaç kez gizli alt-dizi olarak geçer?

Şıklar:
A) 2 
B) 4 
C) 8 
D) 10 
E) 12

Cevap: E 10

Çözüm:
Açıklamalarda verilen özyineli fonksiyonu kullanıp 4x13 boyutundaki aşağıdaki matrisi doldurduğumuzda 
cevabın matrisin sağ alt köşesinde bulunan 12 olduğunu görürüz. 

<table>
  <tr>
    <td></td><td>-</td><td>A</td><td>B</td><td>C</td><td>C</td><td>B</td><td>A</td><td>A</td><td>B</td><td>C</td><td>C</td><td>B</td><td>A</td>
  </tr>
  <tr>
    <td>-</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td>
  </tr>
  <tr>
    <td>A</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>2</td><td>3</td><td>3</td><td>3</td><td>3</td><td>3</td><td>4</td>
  </tr>
  <tr>
    <td>B</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>2</td><td>2</td><td>2</td><td>5</td><td>5</td><td>5</td><td>8</td><td>8</td>
  </tr>
  <tr>
    <td>C</td><td>0</td><td>0</td><td>0</td><td>1</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>7</td><td>12</td><td>12</td><td>12</td>
  </tr>
</table>
Bilgisayar Olimpiyatı 2019, 1. Aşama, Soru 34

## [31-35 soruları için açıklama]
Verilen bir **S** karakter dizisinin içinde daha küçük bir **P** dizisinin karakterleri sırayla fakat ardışık olma şartı olmadan geçiyorsa bu durumu **gizli alt-dizi** olarak adlandırmaktayız. Mesela aşağıdaki **S** dizisinde
### gmtcoarbbhpoheaccvbttya
12345678901234567890123
**merhaba** dizisi [2,4,7,10,15,19,23] indislerinde gizli alt-dizi olarak geçmektedir. Aynı **merhaba** dizisi ayrıca [2,4,7,13,15,19,23] indislerinde de gizli alt-dizi olarak geçmektedir. Verilen bir **P** dizisinin bir **S** dizisi içinde kaç kez gizli alt-dizi olarak geçtiğini aşağıdaki özyineli yöntem ile bulabiliriz. **F(i,j)** fonksiyonu **P** dizisinin ilk **i** karakterinin **S** dizisinin ilk **j** karakteri içinde kaç kez gizli alt-dizi olarak geçtiğini göstersin. |**P**| de bir dizideki karakter sayısını ve **P[i]** **P** dizisinin **i**. karakterini göstersin.
\[F(0,0) = 1\]
\[F(i,0) = 0 \quad 1'den |P|'ye kadar olan i değerleri için\]
\[F(0,j) = 1 \quad 1'den |S|'ye kadar olan j değerleri için\]
\[F(i,j) = F(i,j-1) \text{ eğer } P[i] S[j]'den farklı ise\]
\[F(i,j) = F(i-1,j-1) + F(i,j-1) \text{ eğer } P[i] \text{ ve } S[j] \text{ aynı karakter ise}\]
Bir **P** dizisinin bir **S** dizisi içinde kaç kez gizl i alt-dizi olarak geçtiğini bulmak için **F(|P|,|S|)** değerini hesaplamak yeterli olacaktır.
Sadece ‘A’ karakterlerinden oluşan **M** uzunluğundaki bir dizide sadece ‘A’ karakterlerinden oluşan **N** uzunluğundaki bir dizi kaç kez gizli alt-dizi olarak geçer?
A) **M**!
B) **N**!
C) **M**! / **N**!
D) **M**! / ((**M**-**N**)!-**N**!)
E) **M**!-**N**!
Aynı karakterlerden oluşan iki dizi verildiğinde küçük dizinin büyük dizi içerisinde kaç kez gizli alt-dizi olarak bulunduğu sorusu “M adet karakter içinde kaç farklı şekilde N adet karakter seçebiliriz?” sorusu ile aynı soru haline gelir. Bu da **M**’nin **N**’li kombinasyonuna eşittir yani cevap D şıkkıdır.

---

‘ABCCCAABBBAABCAABCABC’ dizisinde ‘AB’ dizisi 24 kez gizli alt-dizi olarak geçiyorsa ve aynı dizide ‘ABC’ dizisi 55 kez gizli alt-dizi olarak geçiyorsa ‘ABCCCAABBBAABCABCAABCAAAAABC’ dizisinde ‘ABC’ dizisi kaç kez alt-dizi olarak geçer?

Şıklar:
A) 55 | B) 79 | C) 92 | D) 128 | E) 256

Cevap: C 92

Çözüm:
Bu soruda büyük bir tablo doldurmaya gerek kalmadan verilen sayıları kullanarak soruyu çözebiliriz. İkinci verilen uzun dizide bir önceki diziye göre 6 tane A eklendiğinden toplam A sayısı 13 olmuştur. Yani uzun dizideki sonra karakterden bir önceki karakter B olduğundan ‘AB’ dizisi sondan bir önceki karaktere kadar olan (ve o karakter dahil) kısımda toplam 24+13 yani 37 kez geçmektedir. Arada başka ‘C’ olmadığından ‘ABC’ dizisi de hala bu yeni uzun dizide sondan bir önceki karaktere kadar olan kısımda 55 kez geçtiğinden ve son karakter de C olduğundan sorunun cevabı 37+55=92 olarak bulunur.