Time Limit: 2 sec / Memory Limit: 256 MB
問題文
新入生の PAKEN 君は, 入部記念に先輩から長さ N の整数列 A = {A_1, A_2, A_3, ..., A_N} をもらった.
PAKEN 君は机の上に N 枚のカードを一列に, 左から i 番目のカードに書かれている数が A_i となるように並べた.
あなたはこのカードの並びに対して, 以下のような操作を好きなだけすることができる.
- 隣り合う 2 枚のカードを選び, それを取り除き, その後, 取り除いた 2 つのカードの積が書かれたカードを, 取り除いた場所に置く.
- 例えば, カードの並びが {7, 6, 8, 4} であり, 6 と 8 を取り除く操作を行った場合, 操作後のカードの並びは {7, 48, 4} となる.
PAKEN 君は, 整数 P が大好きなので, 机の上に P が書かれたカードが 1 枚でもあれば喜ぶ. そのとき, PAKEN 君を喜ばせることができるかどうかを判定せよ.
入力
入力は以下の形式で標準入力から与えられる.
N P A_1 A_2 A_3 ... A_N
出力
PAKEN 君を喜ばせることができるなら Yay!
, そうでないなら :(
と出力せよ.
制約
- N は 1 以上 100 \ 000 以下の整数
- P は 1 以上 1 \ 000 \ 000 \ 000 以下の整数
- A_i は 1 以上 9 以下の整数
小課題
この問題には小課題 / 部分点はない.
入力例1
5 10 1 3 5 2 4
出力例1
Yay!
最初のカードの並びは, {1, 3, 5, 2, 4} である. その状態から, カード 5, 2 に対して操作を行うと, カードの並びは {1, 3, 10, 4} となる.
そうすると, 10 が出てくるので, PAKEN 君は喜ぶ.
入力例2
2 11 3 4
出力例2
:(
最初のカードの並びは {3, 4} である. まず最初の状態には P = 11 が書かれたカードはないので, 操作を行うしかない, ここから操作する方法は, 3, 4 に対して操作を行うという 1 通りしかない.
操作を行うと, カードの並びは {12} となるため, これでも 11 は作れない. そのため, PAKEN 君を喜ばせることはできない.
入力例3
20 23328 2 9 4 7 2 1 5 4 8 1 9 5 6 6 1 9 1 9 8 1
出力例3
Yay!
writer: TAISA_