Bilgisayar Olimpiyatı 2014, 1. Aşama, Soru 32

[32 – 35] Sorular için Açıklama
X, Y ve Z aşağıda verildiği gibi tanımlanmış karşılıklı özyineli nesnelerdir. Tanımlarda toplam dört farklı (atomik) sembol (a, b, c ve ●) vardır. X, Y ya da Z ile tanımlanamayan tüm nesneler geçersizdir.
\[
X = \begin{bmatrix} a & ya da; \\ b \cdot X' \cdot a & ya da; \\ b \cdot Y' \cdot b & ya da; \\ b \cdot Z' \cdot c & ya da; \end{bmatrix} \quad Y = \begin{bmatrix} \cdot \cdot \cdot X' \cdot a & ya da; \\ \cdot \cdot \cdot Y' \cdot b & ya da; \\ \cdot \cdot \cdot Z' \cdot a & ya da; \end{bmatrix} \quad Z = \begin{bmatrix} a \cdot b & ya da; \\ c \cdot X' \cdot X'' & ya da; \\ b \cdot Y' \cdot Y'' & ya da; \\ a \cdot Z' \cdot Z'' & ya da; \end{bmatrix}
\]
İfadelerdeki X' ve X'' nesneleri X; Y' ve Y'' nesneleri Y; Z' ve Z'' nesneleri Z cinsinden nesnelerdir. Sırasıyla X, Y ve Z tipinden nesneleri girdi olarak alan f, g ve h fonksiyonları aşağıda tanımlanmıştır. Bu fonksiyonlar karşılıklı özyineli fonksiyonlar olup tamsayı değerler döndürürler.
\[
\begin{array}{l@{\quad}l@{\quad}l}
\text{ff(X)} = \begin{cases} -1 & \text{eğer } X = a \\ -4 + \text{f(X')} & \text{eğer } X = b \cdot X' \cdot a \\ -2 + \text{g(Y')} & \text{eğer } X = b \cdot Y' \cdot b \\ -1 + \text{h(Z')} & \text{eğer } X = b \cdot Z' \cdot c \end{cases} & \text{g(Y)} = \begin{cases} -2 & \text{eğer } Y = \cdot \\ \text{f(X')} & \text{eğer } Y = X' \cdot cX'' \\ -1 + 2\text{g(Y')} & \text{eğer } Y = Y' \cdot bY'' \\ -3 + 3\text{h(Z')} & \text{eğer } Y = Z' \cdot aZ'' \end{cases}
\end{array}
\]
AÇIKLAMA
Her nesnenin yukarıda belirtilen durumlarını yukarıdan aşağı numaralandıralım (X nesnesinin 1.durumu a, 2.durumu b • X' • a ...) ve soruları ona göre çözelim. Aynı zamanda çözümü hızlandırmak için X, Y ve Z nesnelerinin ● durumları sayısını artıralım.
\[
X: a, a \cdot b, b \cdot a, a, b \cdot \cdot \cdot \cdot b, b \cdot a \cdot b \cdot c
\]
\[
Y: \cdot, a \cdot c, a, \cdot \cdot b, \cdot a \cdot b \cdot a \cdot a \cdot b
\]
\[
Z: a \cdot b, c \cdot a, b \cdot \cdot \cdot \cdot a, a \cdot a \cdot b \cdot a \cdot b
\]

---

Hangisi bir Y nesnesidir?

Şıklar:
A) \(a \bullet b \bullet ab \bullet \bullet \bullet ba\) | B) \(a \bullet b \bullet a \bullet b \bullet \bullet b \bullet a \bullet\) | C) \(a \bullet c \bullet a \bullet cc \bullet \bullet b \bullet a \bullet c\) | D) \(a \bullet a \bullet bb \bullet \bullet \bullet aa \bullet b\) | E) Hiçbiri

Cevap: D \(a \bullet a \bullet bb \bullet \bullet \bullet aa \bullet b\)

Çözüm:
Bu soruda her şıkkın Y nesnesi olup olmayacağını belirlememiz gerekmektedir. Bütün şıklar \(a \bullet\) ile başladığından Z nesnesinin 4. durumu ile başlar Y nesnesi olması için Y'nin 4.durumu sağlanmalı ve nesne \(a \bullet Z \bullet a\) Z formatında olması gerekir:
A) A şıkkındaki nesnemiz \(a \bullet b \bullet ab \bullet \bullet \bullet \bullet ba'dır\).
-1 tane \(a\) bulunur ve onun öncesinde b vardır. Yani 2 tane Z bulunamayacağından olamaz.
B) B şıkkında sağ taraftaki \(a\) yı seçeriz ve onun sağındaki \(a \bullet Z\) nesnesi olmadığından sağlamaz. (soldaki seçilemez)
C) C şıkkında yine aynı sebepten sağdaki \(a \bullet a\) yı seçeriz ve onun sağındaki \(a \bullet Z \text{ nesnesi olmadığından sağlamaz}\).
D) D şıkkında 1 tane \(a\) vardır ve sağ tarafında \(a \bullet b\) vardır. Sol tarafında ise \(a \bullet b\) ve \(b \bullet \bullet \bullet\) vardır. Bunların hepsi Z nesnesi olduğundan formata uyar. Yani Y nesnesidir.