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