問題一覧 > 通常問題

No.74 貯金箱の退屈

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 113
作問者 : kroton
16 ProblemId : 127 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:46:44

問題文

貯金箱くんはとても退屈していました。
そこで自分が持っている硬貨で遊ぶことにしました。

まず自分の持っている硬貨を床にばらまき、そこから N 枚硬貨を選び円形に並べます。
次に N 枚の硬貨から適当に1枚選びます。選んだ硬貨の額面を D 円としたとき、選んだ硬貨から時計回りに D 個先の硬貨と、反時計回りに D 個先の硬貨をひっくり返します。
ただし時計回りでも反時計回りでも同じ硬貨だった場合はその硬貨を1回だけひっくり返します。
貯金箱くんは、この操作を繰り返しすべての硬貨を表向きにしたいです。

硬貨の並び、額面、最初の裏表が与えられるのですべての硬貨を表向きにできるか判定してください。
ただし同じ硬貨を複数回選んでもよいとします。

入力

N
D1 D2 D3  DN
W1 W2 W3  WN

入力はすべて整数で与えられます。

  • 3N100 は硬貨の枚数を表します。
  • 1Dk1000k 番目の硬貨の額面を表します。
  • 0Wk1k 番目の硬貨の裏表を表し、Wk=0 の場合は「裏向き」を Wk=1 の場合は「表向き」を表します。
  • 硬貨は時計回りに与えられます。

出力

すべての硬貨を表向きに出来る場合は「Yes」を、できない場合は「No」を出力してください。

サンプル

サンプル1
入力
3
1 2 3
1 1 1
出力
Yes

最初の状態ですべて表向きになっているので1枚も選ぶ必要がありません。

サンプル2
入力
3
1 2 3
0 1 1
出力
Yes

最初に 2 円の硬貨を選び、時計回りに2 個先の 1 円の硬貨と反時計回りに 2 個先の 3 円の硬貨をひっくり返します。
次に 3 円の硬貨を選ぶと時計回りでも反時計回りでも 3 円の硬貨になるので、3 円の硬貨をひっくり返し、すべての硬貨が表向きになります。

図: 表向きを青、裏向きをピンクとしたときの様子

サンプル3
入力
3
1 1 1
0 0 0
出力
No

どのように硬貨を選んでもすべての硬貨を表向きにすることはできません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。