Metrodakı sirr#11747

Metrodakı sirr

3 saniyə

128 meqabayt

Çətin

İki Olimpiada tamaşaçısı növbədə dayanıb. Onların hər birinin Paris metrosunun xəritəsi var və vaxtı əyləncəli keçirmək üçün bir oyun düşünüblər. Əvvəlcə $A$ oyunçusu rast gələn xətti seçir (bütün xətlərdən bərabər ehtimalla) və $B$ oyunçusu bu xətti tapmalıdır. Bunun üçün $B$ oyunçusu dəfələrlə müəyyən bir stansiyada həmin xəttin dayanıb-dayanmadığını soruşur və $A$ oyunçusu hər suala düzgün cavab verir. Kifayət qədər sual verildikdən sonra, adətən $B$ oyunçusu hansı xəttin seçildiyini dəqiq müəyyənləşdirə bilir. Əlbəttə, $B$ oyunçusu soruşmalı olduğu sualların sayını minimum etmək istəyir.

Sizə $m$ xətt (1-dən $m$ -ə kimi nömrələnmişdir) və $n$ stansiyadan ( $0$ -dan $n - 1$ n-1-ə kimi nömrələnmişdir) ibarət olan metro xəritəsi verilib. Hər xətt üçün həmin xəttin dayandığı stansiyalar verilib. B oyunçusunun optimal strategiya ilə seçilmiş xətti tapmaq üçün gözlənilən minimum sual sayını hesablayın.

Başqa sözlə, $S$ hər hansı strategiyadır və $Q_{S, j}$ Q_{S,j} seçilmiş xətt $j$ olduqda bu strategiya ilə verilmiş sualların sayını göstərir. Onda

E_{S} = E [Q_{S}] = \frac{1}{m} j = 1 \sum m Q_{S, j}

E_S = E[Q_S] = \frac{1}{m} \sum_{j=1}^m Q_{S,j}

gözlənilən sualların sayını, xəttin təsadüfi (bərabər ehtimalla) seçilməsi ilə ifadə edir. Tapşırıq — $min_{S} E_{S}$ \min_S E_S-i hesablayın. Əgər $B$ oyunçusu həmişə seçilmiş xətti dəqiq müəyyən edə bilmirsə, **not possible** çap edin.

Giriş

Birinci sətirdə $n$ ( $1 \leq n \leq 18$ 1 \leq n \leq 18) — stansiyaların sayı verilir. İkinci sətirdə $m$ ( $1 \leq m \leq 50$ 1 \leq m \leq 50) — xətlərin sayı verilir. Sonra $m$ sətir: $k$ -cı sətirdə əvvəlcə $p \leq n$ p \leq n müsbət tam ədədi, sonra boşluq və $p$ ədəd $s_{1}, s_{2}, \dots, s_{p}$ s_1, s_2, \ldots, s_p — $k$ xəttinin dayandığı stansiyaların nömrələri verilir. Hər bir xətt hər stansiyada ən çox bir dəfə dayanır.

Çıxış

Bir ədəd çap edin: seçilmiş xətti tapmaq üçün $B$ oyunçusunun soruşmalı olduğu minimal gözlənilən sual sayı və ya **not possible** (kiçik hərflərlə). Cavablar $1 0^{- 4}$ 10^{-4} dəqiqliklə düzgün hesab olunur.

Nümunələr

2-ci nümunəyə izah. Simmetriyaya görə, əvvəlcə $0$ -cı stansiyanı soruşmaq optimaldır. Bu, $0$ -cı stansiyada dayanan $1$ -ci xətti, dayanmayan $2$ və $3$ -cü xətlərdən fərqləndirir. Lazım gələrsə, $2$ -ci və $3$ -cü xətləri fərqləndirmək üçün ikinci sual verilir.

Əgər tapılmış xətt $1$ -ci olarsa, $B$ oyunçusu bir sual verir; digər hallarda isə iki sual verir. Buna görə gözlənilən sual sayı $(1 + 2 \cdot 2) /3$ (1 + 2 \cdot 2)/3-ə bərabərdir.

Nümunə 1

Nümunə 2