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

### [11-17] soruları için açıklama
Aşağıda üç adet karşılıklı özyinelemeli yapının söz dizim kuralları verilmiştir. Bu tanımlarda yer alan • gibi semboller tanımlanan yapıların söz dizimlerinde yer almaktadırlar, fazla ya da eksik kullanılamazlar. Bu tanımlara uygun olarak oluşturulan ifadeleri aşağıdaki sorularda \(X_1\), \(X_2\) ve \(X_3\) nesneleri olarak adlandıracağız.
\[X_1 = \begin{cases} A_0 & \text{ya da} \\ A_1 \bullet X_1 & \text{ya da} \\ A_2 \bullet X_2 & \text{ya da} \\ A_3 \bullet X_3 & \text{ya da} \end{cases}\]
\[X_2 = \begin{cases} B_0 & \text{ya da} \\ B_1 \bullet X_1 & \text{ya da} \\ B_2 \bullet X_2 & \text{ya da} \\ B_3 \bullet X_3 & \text{ya da} \end{cases}\]
\[X_3 = \begin{cases} C_0 & \text{ya da} \\ C_1 \bullet X_1 & \text{ya da} \\ C_2 \bullet X_2 & \text{ya da} \\ C_3 \bullet X_3 & \text{ya da} \end{cases}\]
**X₁, X₂ ve X₃** nesneleri üzerinde aşağıdaki fonksiyonlar tanımlanmaktadır. Fonksiyonların parametrelerinin türleri parametreden sonra | ile belirtilmiştir ve T pozitif tamsayıları ifade etmektedir. Bu fonksiyon tanımlarında \(f_r, f_2, f_3, g_r, g_2, g_3\) fonksiyon adlarını, px1
ve \(px'_1, X₁\) nesnelerini, \(px₂\) ve \(px'_2, X₂\) nesnelerini ve \(px₃\) ve \(px'_3, X₃\) nesnelerini, n ise pozitif tamsayıları göstermektedir. \(f_r, f_2\) ve \(f_3\) fonksiyonları pozitif tamsayıları, \(g_r\) fonksiyonu yeni \(X₁\) nesnelerini, \(g₂\) fonksiyonu yeni \(X₂\) nesnelerini, \(g₃\) fonksiyonu yeni \(X₃\) nesnelerini üretmektedirler. \(g_r, g₂, g₃\) fonksiyonları 2 adet tamsayı parametre almaktadır ve bu parametrelerden ikincisi birincisinin katı olmalıdır (aksi durumda bu fonksiyonlar tanımlı değildir).
\[f_1(px_1 | X_1) = \begin{cases} 0 & \text{eğer } px_1 = A_0 \text{ ise} \\ 1 + f_1(px'_1) & \text{eğer } (px_1 = A_1 \cdot px'_1) \text{ ise} \\ 2 + f_2(px'_2) & \text{eğer } (px_1 = A_2 \cdot px'_2) \text{ ise} \\ 3 + f_3(px'_3) & \text{eğer } (px_1 = A_3 \cdot px'_3) \text{ ise} \end{cases}\]
\[f_2(px_2 | X_2) = \begin{cases} 0 & \text{eğer } px_2 = B_0 \text{ ise} \\ 10 + f_1(px'_1) & \text{eğer } (px_2 = B_1 \cdot px'_1) \text{ ise} \\ 20 + f_2(px'_2) & \text{eğer } (px_2 = B_2 \cdot px'_2) \text{ ise} \\ 30 + f_3(px'_3) & \text{eğer } (px_2 = B_3 \cdot px'_3) \text{ ise} \end{cases}\]
\[f_3(px_3 | X_3) = \begin{cases} 0 & \text{eğer } px_3 = C_0 \text{ ise} \\ 100 + f_1(px'_1) & \text{eğer } (px_3 = C_1 \cdot px'_1) \text{ ise} \\ 200 + f_2(px'_2) & \text{eğer } (px_3 = C_2 \cdot px'_2) \text{ ise} \\ 300 + f_3(px'_3) & \text{eğer } (px_3 = C_3 \cdot px'_3) \text{ ise} \end{cases}\]
\[g_1(n | T, m | T) = \begin{cases} A_0 & \text{eğer } m = 0 \text{ ise} \\ A_1 \cdot g_1(n, (m-1)) & \text{eğer } n = 1 \text{ ise} \\ A_2 \cdot g_2(n, (m-2)) & \text{eğer } n = 2 \text{ ise} \\ A_3 \cdot g_3(n, (m-3)) & \text{eğer } n = 3 \text{ ise} \end{cases}\]
\[g_2(n | T, m | T) = \begin{cases} B_0 & \text{eğer } m = 0 \text{ ise} \ \ B_1 \cdot g_1(n, (m-1)) & \text{eğер } n = 1 \text{ ise} \ \ B_2 \cdot g_2(n, (m-2)) & \text{eğер } n = 2 \text{ ise} \ \ B_3 \cdot g_3(n, (m-3)) & \text{eğер } n = 3 \text{ ise} \end{cases}\]
\[g_3(n | T, m | T) = \begin{cases} C_0 & \text{eğер } m = 0 \text{ ise} \ \ C_1 \cdot g_1(n, (m-1)) & \text{eğér } n = 1 \text{ ise} \ \ C_2 \cdot g_2(n, (m-2)) & \text{eğér } n = 2 \text{ ise} \ \ C_3 \cdot g_3(n, (m-3)) & \text{eğér } n = 3 \text{ ise} \end{cases}\]
**AÇIKLAMA**
\(g_{1,2,3}\) fonksiyonları sırasıyla \(A_{1,2,3}\), \(B_{1,2,3}\), \(C_{1,2,3}\) sembollerini bir sonraki fonksiyon ile üretilecek nesnenin sonuna ekler. \(f_{1,2,3}\) fonksiyonları ise uygun formatta \(A_{1,2,3}\), \(B_{1,2,3}\), \( C_{1,2,3}\) sembollerinin karşılık gelen değerlerini toplama ekler (\(A_0\), \(B_0\), \(C_0\) sembollerinin değerleri 0 olduğu için bitirme sembol olarak sayıyoruz). Her sembolün değerleri f fonksiyonuna göre aşağıdaki gibidir:
\(A_1 = 1\), \(A_2 = 2\), \(A_3 = 3\), \(B_1 = 10\), \(B_2 = 20\), \(B_3 = 30\), \(C_1 = 100\), \(C_2 = 200\), \(C_3 = 300\).
[GÖRSEL]
f fonksiyonları her zaman uygun formatta çalıştığından herhangi bir nesne f fonksiyonlarından birine girdiğinde, f fonksiyonu elemanlarının değerlerinin toplamını döner. Yani \(C_2 \cdot B_2 \cdot B_2 \cdot B_0\) nesnesi f fonksiyonuna verildiğinde (Doğru format için \(f_3\) gerekli) f fonksiyonu \(2O+2O+2O=24O\) döner.
Bir de nesnelerin oluşma şekline, yani g fonksiyonlarına göz atalım.
- İlk olarak görürüz ki n her zaman sabit kalıyor ve m her zaman n kadar azalıyor.
- Buradan (n ≡ O mod m) olduğunu çıkartabiliriz(formata uygun olması için gerekir.)
- (n ≡ O mod m) olduğunu biliyoruz. Bu şartlara baktığımızda nesnemizin • sembolleri hariç m/n tane sembolden oluştuğunu biliyoruz.
- Yani \(g_n(n, m)\) çağırıldığında sonraki ve ondan sonraki her adımda \(g_n\) fonksiyonu çağırılacağından ilk sembol \(X_n\) sonraki ler \(N_n\) olur. (Büyütünce karşılık gelen ifadeymiş gibi düşünün x=1 ise X=A, x=2 ise X=B, x=3 ise X=C, n için de aynısı geçerli)
Bu genellemeye göre f(g_n(n, m)) değeri: \(X_n\) (n değeri) + (m/n-1)*(N_n (n değeri) olur.

---

\(f_3(g_3(3, f_2(g_2(3, (f_1(g_1(3, 3))))))\) işleminin sonucu aşağıdakilerden hangisidiri?

Şıklar:
A) 3 | B) 30 | C) 300 | D) 3000 | E) 30000

Cevap: A 3

Çözüm:
\(3/3 = 1\) olduğundan \(f_3(g_3(3, 3)) = A_3 = 3\) olur.
\(3/3 = 1\) olduğundan \(f_2(g_2(3, 3)) = B_3 = 30\) olur.
\(30/3 = 10\) olduğundan \(f_3(g_3(3, 30)) = C_3 + 9*C_3 = 10*300 = 3000\) olur.
gcd(a, b) = gcd(a mod b, b) özelliğini kullanalım:
gcd(3722, 5854)
= gcd(3722, 2134)
= gcd(1588, 2134)
gcd(1588, 546)
= gcd(50, 546)
= gcd(50, 46)
gcd(4, 46)
= gcd(4, 2)
= 2