eolymp
bolt
Try our new interface for solving problems
Məsələlər

Sonlu avtomatla oyun

Sonlu avtomatla oyun

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Hamı bilir ki, sonlu avtomatla edilən zarafat çox pis nəticələnə bilər. Lakin Dima bunu heç də yaxşı anlamadı və sonlu avtomatlarla bağlı kurs işi üzərində işləyərkən iki nəfərlik yeni maraqlı oyun fikirləşdi. Oyun o dərəcədə cəlbedici oldu ki, onun bütün həmkursları günlərlə onu oynayırdılar... Əlbətdə ki, onlardan heç biri sonlu avtomatlarla bağlı kurs işlərini təhvil verə bilmədilər :)

Bu oyunun qaydası kifayət qədər sadədir. İki oyunçu n vəziyyəti və m simvollu əlifbası olan determinasiya olunan sonlu avtomat götürürlər. Oyun prosesində onlar başlanğıcda boş olan S sətrinə simvol əlavə edirlər (bir oyunçu bir gedişdə yalnız bir simvol əlavə edir). Əgər kiminsə gedişindən sonra avtomat S sətrini buraxırsa, onda bu oyunçu qələbə qazanmış hesab edilir.

Dima fikirləşir ki, sonlu avtomata görə O(m·n) zamanı ərzində hər iki oyunçunun optimal oynaması halında kimin qalib gələcəyini müəyyənləşdirmək olar. Hər iki oyunçunun optimal oynaması halında qalib gələcək oyunçunu təyin edən proqramı tərtib edin.

Giriş verilənləri

Giriş faylının ilk sətri avtomatın vəziyyətlərinin n (1n10^4) sayını və sonlu avtomatın əlifbasının m (1m10) qüvvətini ehtiva edir. Avtomatın vəziyyətləri sıfırdan başlayaraq nömrələnir, sıfır vəziyyəti başlanğıc sayılır. Sonra sonlu avtomatın keçid funksiyalarını təsvir edən n sətir verilir. Hər bir sətir 0-dan n-1-ə qədər m sayda ədəd ehtiva edir. Sonra avtomatın mümkün vəziyyətlərinin k sayı verilir. Sonuncu sətir mümükün vəziyyətlərin nömrəsini ehtiva edir. Başlanğıc vəziyyət mümükün hesab edilmir.

Çıxış verilənləri

Əgər oyunun mənası yoxdursa (yəni, onda avtomatın dili boşdur), çıxış faylına dırnaq işarələri olmadan "Automata language is empty." ifadəsini verin. Əgər hər iki oyunçunun optimal oynaması halında oyun heç-heçə tamamlanarsa, "Game is a draw." ifədəsini verin. Əgər birinci oyunçu qalib gələrsə, "Dimochka wins." ifadəsini, əks halda "Dimochka loses." ifadəsini verin. Oyunçulardan birinin qalib gəlməsi halında ikinci sətirdə (hər iki oyunçunun optimal oynaması halında) qələbə qazandıran sətrin ən qısa uzunluğunu verin.

Nümunə

Giriş verilənləri #1
2 1
0
1
1
1
Çıxış verilənləri #1
Automata language is empty.