Nim#1097

Nim

1 saniyə

64 meqabayt

Çox asan

Gəlin ənənəvi Nim oyununu oynayaq. Sən və mən bir masada oturmuşuq, qarşımızda yüz ədəd daş var (daşların dəqiq sayı məlumdur). Biz növbə ilə oynayırıq; hər növbədə bir oyunçu yığından bir ilə dörd arasında daş götürə bilər. Sən birinci oynayırsan. Son daşı götürən uduzur.

Bu oyunda qalib strategiya mövcuddur. Birinci, sən 4 daş götürürsən, yığında 96 daş qalır. Mən nə etsəm də, 92 ilə 95 arasında daş qalacaq. Sonra, sənin növbəndə mənə 91 daş qoymaq mümkündür (bunu yoxla). Bu proseduru təkrarlayaraq sən həmişə mənə $5 k + 1$ 5k+1 daş qoyursan və beləliklə, mən məcburən son daşı götürür və uduzuram. Əgər başlanğıcda 101 daş olsaydı, qalib strategiya məndə olardı və sən həmişə uduzardın.

Gəlin oyunu ümumiləşdirək. Əvvəlcə, tutaq ki, bu, komanda oyunudur. Hər komandada $n$ oyunçu var, $2 n$ oyunçu masada əyləşib, hər bir oyunçunun hər iki tərəfində rəqibləri var. Oyunçular ardıcıl növbə ilə oynayır, beləliklə komandalar növbə ilə hərəkət edir. İkincisi, hər oyunçunun öz növbəsində götürə biləcəyi maksimum daş sayı var (minimum həmişə birdir). Beləliklə, oyun asimmetrik və bəzən ədalətsiz olur.

Hər iki komanda optimal oynadıqda, nəticə tam şəkildə başlanğıc daşların sayı və hər bir oyunçunun növbəsində götürə biləcəyi maksimum daş sayından asılıdır. Beləliklə, həmişə hansısa komandanın qalib strategiyası olur.

Sən komandanın məşqçisisən. Hər bir oyunda, hakim başlanğıcda toplam daşların sayını və hər bir oyunçu üçün növbəsində götürə biləcəyi maksimum daş sayını elan edir. Sənin komandan birinci oynayır. Komandanın qalib strategiyası olub-olmadığını müəyyənləşdir.

Giriş

Hər bir giriş sətri (ələ sonuncu sətir istisna olmaqla) bir test vəziyyətini təmsil edir və aşağıdakı formatda tam ədədlər ardıcıllığından ibarətdir:

$n S M_{1} M_{2} \dots M_{2 n}$ n\ S\ M_1\ M_2\ \ldots\ M_{2n}

burada $n$ — komandadakı oyunçuların sayı, $S$ — daşların başlanğıc sayı, $M_{i}$ M_i — $i$ -ci oyunçunun növbəsində götürə biləcəyi maksimum daş sayıdır. $1$ , $3$ , $5$ , ... nömrəli oyunçular sənin komandan, $2$ , $4$ , $6$ , ... nömrəli oyunçular isə rəqib komandadır. Ədədlər boşluqlarla ayrılıb. Sonuncu sətrdə təkcə 0 var və o emal olunmamalıdır.

Aşağıdakı məhdudiyyətləri qəbul edə bilərsiniz: $1 \leq n \leq 10$ 1 \leq n \leq 10, $1 \leq M_{i} \leq 16$ 1 \leq M_i \leq 16, və $1 \leq S < 2^{13}$ 1 \leq S < 2^{13}.

Çıxış

Hər bir test üçün bir sətrə $1$ yazın – əgər komandanızın qalib strategiyası varsa, əks halda $0$ .

Nümunələr

Nümunə 1