Rənglərin qarışdırılması
Frеnk Londonda yaşayır və oyunlar ilə riyaziyyatı çox sevir. Son vaxtlar o, mobil telefonunda bir oyun oynayır. Oyun olduqca sadədir: rəngli fiqurlar ardıcıllığı var və hər gedişdə oyunçu yeni bir rəng əldə etmək üçün qonşu fiqur cütlüyünü birləşdirməlidir. Bu proses, bütün ardıcıllıq tək bir son fiqura çevrilənə qədər təkrarlanır. Problem ondadır ki, hər rəng cütlüyü birləşdirilə bilməz. İcazə verilən kombinasiyaları təsvir edən qaydalar dəsti mövcuddur. Məsələn, aşağıdakı qaydalar verilsin:
mavi + sarı → yaşıl
sarı + qırmızı → narıncı
mavi + narıncı → qəhvəyi
və ardıcıllıq (mavi, sarı, qırmızı). Oyun iki addımda qəhvəyi fiqurla bitə bilər: (mavi, sarı, qırmızı) → (mavi, narıncı) → (qəhvəyi).
Hal-hazırda Frеnk Valensiyada məşhur proqramlaşdırma müsabiqəsindədir və universitetə çatmaq üçün tramvayı gözləyir. Bu arada, vaxt keçirmək üçün bu oyunu oynayır. Günəş o qədər parlaqdır ki, telefonunun ekranını düzgün görə bilmir. Frеnkin hər fiqurun mümkün rəngi ilə bağlı müəyyən bir əminliyi var və o, giriş ardıcıllığının qiymətləndirilməsi nəticəsində oyunun ən ehtimal olunan ssenarisindən sonra hansı rəngin nəticə olacağını düşünür.
Frеnkin iki rəng A və B qiymətləndirməsi var və A + B → C kombinasiyası, C rəngini əldə etmə ehtimalı cer(C) = cer(A) · cer(B) təşkil edir.
Giriş verilənləri
Birinci sətir rənglərin mümkün kombinasiyalarını təyin edən qaydaların sayını r (0 < r ≤ 100) ehtiva edir. Növbəti r sətir hər biri s_1, s_2, s_3 üç sətir ehtiva edir və s_1 + s_2 → s_3 kombinasiyasını təsvir edir. Növbəti sətir testlərin sayını t təyin edir. Hər test üçün fiqurların giriş ardıcıllığının uzunluğu c (0 < c ≤ 500) verilir. Növbəti c sətir hər biri fiquru təsvir edir, rəng k və müvafiq ehtimalı (0 < cer(k) ≤ 1.0) təyin edən cütlər siyahısını ehtiva edir. Siyahı END sözü ilə bitir. Hər fiqur üçün ehtimalların cəmi həmişə 1.0 təşkil edir. Testlərdəki hər rəng əvvəlcə oyunu təsvir edən qaydalarda rast gəlinir.
Çıxış verilənləri
Hər test üçün oyunun ən ehtimal olunan rənglə bitəcəyini çıxarın. Əgər oyunu bitirmək mümkün deyilsə, GAMEOVER çıxarın.
Nümunələrə izahlar
Birinci test
Birinci testdə cəmi iki fiqur var. Frеnk əmindir ki, ikinci fiqur Sarıdır, lakin birinci Qırmızı və ya Narıncı ola bilər. Oyunun iki mümkün həlli var:
1. (Qırmızı; Sarı) → (Narıncı) :
cer(Narıncı) = 0.7
2. (Narıncı; Sarı) → (Sarı) :
cer(Sarı) = 0.3
Frеnkin qiymətləndirmələrinə görə daha ehtimal olunan nəticə 1-dir, buna görə də son rəng Narıncıdır.
İkinci test
İkinci testdə bir neçə fiqur və qiymətləndirmə var. İki mümkün həll:
1. (Mavi,Sarı,Sarı,Qırmızı) → (Mavi,Sarı,Narıncı) → (Mavi,Sarı) → (Yaşıl)
cer(Yaşıl) = 0.006
2. (Yaşıl,Qırmızı,Ağ,Qara) → (Yaşıl,Çəhrayı,Qara) → (Yaşıl,Qırmızı) → (Sarı)
cer(Sarı) = 0.036
Frеnkin qiymətləndirmələrinə görə daha ehtimal olunan nəticə 2-dir, buna görə də son rəng Sarıdır.
Üçüncü test
Frеnk əmindir ki, onun iki fiquru var: Mavi və Narıncı. Onları birləşdirə biləcək qayda mövcud deyil, buna görə oyun həll edilə bilməz.