İkiqat hərəkət

Alisa və Bob oyun oynayır, Samantha isə onlara kömək edir. $n$ daş var və bu daşlar 1-dən $n$-ə qədər nömrələnib. Oyun üç mərhələdən ibarətdir.

Birinci mərhələdə, Alisa və Bob növbə ilə hərəkət edirlər. Alisa birinci hərəkət edir. Hər bir hərəkətdə oyunçu hansı daşı götürmək istədiyini bəyan edir, lakin konkret olaraq hansı daşı götürəcəyini demək əvəzinə iki variant təklif edir. Bu iki variant eyni ola bilər. Həmçinin əvvəlki hərəkətlərdə bəyan edilmiş daşları da təklif etmək olar. Birinci mərhələdə faktiki olaraq daş götürülmür - oyunçular sadəcə ikinci mərhələ üçün niyyətlərini bəyan edirlər. Birinci mərhələ $n+1$ bəyanat verildikdə başa çatır.

Budur $n=3$ üçün birinci mərhələnin nümunəsi:

1. Alisa: "Mən ya daş 1-i, ya da daş 3-ü götürəcəm"

2. Bob: "Mən ya daş 2-ni, ya da daş 2-ni götürəcəm"

3. Alisa: "Mən ya daş 3-ü, ya da daş 2-ni götürəcəm"

4. Bob: "Mən ya daş 1-i, ya da daş 3-ü götürəcəm"

İkinci mərhələdə, verilmiş $n+1$ bəyanat üçün Samantha iki variantdan birini seçir, "birinci" və ya "ikinci" deyir. Samantha tərəfindən seçilmiş hər bir $n+1$ variant ardıcıllığını ssenari adlandıraq. Qeyd edək ki, dəqiq olaraq $2\cdot 2\cdot 2\cdot \cdots \cdot 2=2^{n+1}$ mümkün ssenari mövcuddur. (Hətta bəzi bəyanatlarda birinci və ikinci variantlar eyni olsa belə, biz fərqli ssenarilər əldə etmək üçün "birinci" və ya "ikinci" variantı seçməyi nəzərə alırıq.)

Yuxarıdakı nümunədə Samantha tərəfindən seçilə bilən 16 ssenaridən biri:

1. "Birinci": Alisa birinci daşı götürəcək

2. "Birinci": Bob ikinci daşı götürəcək

3. "İkinci": Alisa ikinci daşı götürəcək

4. "Birinci": Bob birinci daşı götürəcək

Üçüncü mərhələdə Alisa və Bob Samantha-nın qərarlarına uyğun olaraq daşları faktiki olaraq götürməyə başlayırlar. Müvafiq daşı artıq götürüldüyü üçün tələb olunan hərəkəti edə bilməyən ilk oyunçu oyunu uduzur. Qeyd edək ki, $n$ daş və $n+1$ hərəkət olduğuna görə, oyunçulardan biri mütləq uduzmalıdır.

Yuxarıdakı nümunədə Alisa birinci daşı götürməklə başlayır. Sonra Bob ikinci daşı götürür. Alisa ikinci daşı götürməli olacaq, lakin o artıq götürülüb. Buna görə Alisa uduzur və Bob qalib gəlir.

Sizə $n$ sayı və birinci mərhələdə oyunun müəyyən bir anındakı vəziyyət verilir: artıq edilmiş $k$ bəyanat ardıcıllığı. Bu bəyanatlar tamamilə təsadüfi ola bilər.

Bu andan etibarən Alisa və Bob oyunu optimal şəkildə oynayacaqlar, aşağıdakı paraqrafda təsvir edildiyi kimi.

Alisa və Bob necə oynasalar da, Samantha hər bir mümkün ssenarini $2^{n+1}$ ilə eyni ehtimalla seçəcək. Alisa və Bob bunu bilirlər və buna görə də optimal oynayaraq, hər ikisi uduzduqları ssenarilərin sayını minimuma endirməyə çalışırlar.

Tutaq ki, Alisa və Bob oyunun qalan hissəsini yuxarıda təsvir edildiyi kimi oynayacaqlar. Hər iki oyunçu üçün oyunu qazandıqları ssenarilərin sayını tapın.

Giriş verilənləri

Birinci sətir iki tam ədəd $n$ və $k$ ($1\le n\le 35$, $0\le k\le n+1$) — daşların sayı və artıq edilmiş bəyanatların sayı.

Növbəti $k$ sətir bəyanatları edildiyi ardıcıllıqla təsvir edir. Növbəti sətirlərdən hər biri iki tam ədəd — daşların nömrələrini (hər ikisi $1$-dən $n$-ə qədər daxil olmaqla, mütləq fərqli deyil) ehtiva edir.

Qeyd edək ki, əgər $k<n+1$ olarsa, növbəti bəyanatı edəcək oyunçu $k$-nın cüt və ya tək olmasından asılıdır.

Çıxış verilənləri

İki ədəd çıxarın: Alisa-nın oyunu qazandığı ssenarilərin sayı və Bob-un oyunu qazandığı ssenarilərin sayı, hər iki oyunçunun oyunun qalan hissəsini yuxarıda təsvir edildiyi kimi oynadığını nəzərə alaraq.

Qeyd edək ki, çıxarılan iki ədədin cəmi $2^{n+1}$-ə bərabər olmalıdır.

Nümunələr

Qeyd

Birinci nümunə məsələnin şərtindəki nümunəyə uyğundur. Artıq bəyanatlar etmək lazım deyil, buna görə də sadəcə Samantha-nın qərarlarından hansılarının Alisa-nın qələbəsinə, hansılarının isə Bob-un qələbəsinə gətirib çıxardığını görməliyik. Alisa qalib gəlir, əgər Samantha ona birinci hərəkətdə $1$, ikinci hərəkətdə isə $3$ seçərsə, və digər hallarda uduzur.

İkinci nümunədə, əgər Alisa "1 1" bəyanatı ilə başlasa, Bob "2 2" ilə davam edəcək, o zaman Alisa üçüncü hərəkətdə hansı bəyanatı etsə də - o uduzacaq, çünki Samantha birinci hərəkətdə birinci daşı və ikinci hərəkətdə ikinci daşı seçməli olacaq və Alisa-nın üçüncü hərəkəti üçün daş qalmayacaq. Lakin bu Alisa üçün optimal birinci addım deyil: bunun əvəzinə o "1 2" bəyanatı ilə başlamalıdır. O zaman, Bob-un ikinci hərəkətdə nə etdiyindən və Alisa-nın üçüncü hərəkətdə nə etdiyindən asılı olmayaraq, hər biri $8$-dən $4$ halda qalib gələcək.

Qiymətləndirmə

Blok 1 (15 bal): $n\le 4$.

Blok 2 (34 bal): $n\le 10$.

Blok 3 (20 bal): $n\le 25$.

Blok 4 (10 bal): $k=0$.

Blok 5 (21 bal): əlavə məhdudiyyətlər olmadan.