Bilgisayar Olimpiyatı 2008, 1. Aşama, Soru 31

[28-32] soruları için açıklama
[GÖRSEL]
Bir derede daire şeklinde yerleşmiş 8 taş vardır ve kurbağalar bu taşların üzerinde güneşlenir. Bir taşta tek bir kurbağa güneşlenebilir. Kurbağalar taşlara çıkarken şekilde K ile gösterilen yerden taşların üzerine zıplarlar. Zıplarken zıpla(x) şeklinde bir fonksiyonu kullanırlar. Bu fonksiyon verilen x değeri için kurbağanın kaç kere zıplayacağını söyler.
Örneğin bu fonksiyon 3 değerini döndüyse kurbağa 3 kere zıplar ve 3. taş üzerine yerleşir.
8. taştan sonra kurbağa zıplamaya 1. taştan itibaren devam eder. Örneğin zıpla fonksiyonu
13 döndüyse kurbağa 5. taşa yerleşir.
Fakat kurbağanın zıpladığı taşta başka bir kurbağa varsa kurbağa o taşta kalamaz zıpla fonksiyonundaki tanıma göre bulunduğu yerden tekrar bir zıplama yapar. Buna göre zıpla fonksiyonu şu şekilde tanımlanır:
\[ z\mathrm{i p l a}(x)=(M/N) \]
M, zıplama miktarını, N ise zıplanan yerde kurbağa varsa yeni zıplama değerini verir.
Örneğin 'zıpla(x) = x | zıpla(x)' şeklinde tanımlanırsa ve kurbağa zıpla(3) şeklinde zıplarsa x = 3. taşa gider. 3. taşta kurbağa varsa fonksiyonun ikinci kısmındaki zıpla(x) ifadesine göre tekrar zıplar ve 6. taşa gider. 6. taşta da kurbağa varsa 9, yani 1. Taşa gider. Kurbağa boş bir taş buluncaya kadar zıplar. Bulamadığı sürece sonsuza kadar bunu tekrarlar. Fonksiyon tanımında t değişkeni kullanılabilir. O ≤ t ≤ 8, bulunulan taşın numarasını gösterir. Başlangıç noktasında t = O olarak kabul edilir. M ifadesi zıplamadan önce, N ifadesi zıplanan yerde (kurbağa bulunan) hesaplanır.
Kurbağalar geri zıplayamaz. Dolayısıyla zıplama sonucu O ya da daha küçük bir sayı geldiğinde kurbağa bulunduğu taşta (başka kurbağa olsa da) kalır, bir daha zıplayamaz.
## AÇIKLAMA
Kurbağaların başlangıç pozisyonu ve zıplama fonksiyonu soruya göre değiştiğinden; bu pakette soru çözümünü kolaylaştırıcı genel yolu bulmaktansa, soruları çözmeye başlayıp fonksiyonun adımlarını hızlıca uygulamak daha mantıklı olur.
• % işaretini mod olarak kullanacağız (I, n) aralığında değer veren özel mod diyelim), her atlamada
(taşın numarası+zıplama miktarı) %8 yeni taşın numarası olur.
28. 2., 5. ve 7. taşlarda kurbağalar varken: zıpla(x) = (x + 1| zıpla(x + 1)) tanımına göre kurbağa zıpla(1) ile başlarsa hangi taşa yerleşir?
A) 1          B) 6          C) 8          D) 3          E) 4
Fonksiyonumuza göre kurbağa önce x+1 kadar zıplar. Eğer taş doluysa zıpla(x+1) fonksiyonuna göre tekrar zıplar. Şimdi başlayalım:
• Kurbağa O. taşta. zıpla(l) gelir, 1+1 = 2 kadar zıplar ve 2.taş dolu olduğundan zıpla(l+1) çağrılır.
• Kurbağa 2. taşta. zıpla(2) gelir, 2+1 = 3 kadar zıplar ve 5.taş dolu olduğundan zıpla(2+1) çağrılır.
• Kurbağa 5. taşta. zıpla(3) gelir, 3+1 = 4 kadar zıplar ve 1.taşa gelir.
• 1.taş boş olduğundan kurbağa bu taşa yerleşir.

---

Taşların hepsi boşken zıpla(x) = (x | zıpla(x + t - 1)(mod 8)) tanımına göre elimizdeki bir çok kurbağayı arka arkaya zıpla(6) ile başlattığımızda en fazla kaç farklı taşı doldurabiliriz?

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

Cevap: B 5

Çözüm:
Fonksiyonumuza göre kurbağa önce x kadar zıplar. Eğer taş doluysa zıpla(x+t-1) mod 8) fonksiyonuna göre tekrar zıplar. Şimdi başlayalım:
- Kurbağa O. taşta. zıpla(6) gelir, x = 6 kadar zıplar. Bu kurbağa 6. taşa yerleşir ve arkasından gelen kurbağa bu taş dolu olduğundan zıpla((6+6-1) mod 8 = 3) fonksiyonuyla devam eder.
- Kurbağa 6. taşta. zıpla(3) gelir, x = 3 kadar zıplar. Bu kurbağa 1. taşa yerleşir ve arkasından gelen kurbağa bu t aş dolu olduğundan zıpla((3+1-1) mod 8 = 3) fonksiyonuyla devam eder.
- Kurbağa 1. taşta. zıpla(3) gelir, x = 3 kadar Zıplar. Bu kurbağa 4. taşa yerleşir ve arkasından gelen kurbağa bu T aş dolu olduğundan zıpla((3+4-1) mod 8 = 6) fonksiyonuyla devam eder.
- Kurbağa 4. taşta. zıpla(6) gelir, x = 6 kadar Zıplar. Bu kurbağa 2. taşa yerleşir ve arkasından gelen kurbağa bu Taş dolu olduğundan zıpla((2+6-1) mod 8 = 7) fonksiyonuyla devam eder.
- Kurbağa 2. taşta. zıpla(7) gelir, x = 7 kadar zıplar. 1. taş dolu olduğundan zıpla((7+1-1) mod 8 = 7) fonksiyonuyla devam eder.
- Kurbağa 1. taşta. zıpla(7) gelir, x = 7 kadar Zıplar. Bu kurbağa 8. taşa yerleşir ve arkasından gelen kurbağa buTaş dolu olduğundan zıpla((7+8-1) mod 8 = 6) fonksiyonuyla devam eder.
- Kurbağa 8. taşta. zıpla(6) gelir, x = 6 kadarZıplar. 6. taş dolu olduğundan zıpla((6+6-1)mod 8 = 3) fonksiyonuyla devam eder. Bu da 2.işlemde olan 6.taştan zıpla(3) ile zıplama olacağından daha fazla kurbağa yerleşemez.
- En son 6. 1, 4, 2 ve 8 numaralı taşlarda kurbağa bulunur.
- Kurbağa 3. taşta. zıpla(7) gelir, x = 7 kadarZıplar. Bu kurbağa 8. taşa yerleşir ve a rkasından gelen kurbağa bu taş dolu olduğundan Zıpla((7+8-1) mod 8 = 6) fonksiyonuyla devam eder.
- Kurbağa 3. taşta. zıpla(6) gelir, x = 6 kadar Ziplar. 6. taş dolu olduğundan zıpla((5+6-1) mod 8 = 3) fonksiyonuyla devam e der. Bu da 2.işlemde olan 6.taştan zıpl a(3) ile zıplama olacağından daha fazla kurbağ a yerleşemez.
- En son 6. 1, 4, 2 ve 8 numarali taşlarda kurbağa bulunur.