問題一覧 > 通常問題

No.123 カードシャッフル

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 539
作問者 : nmnmnmnmnmnmnm
10 ProblemId : 284 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-10-14 11:54:56

問題文

1からNまでの数字を描いたカードが各1枚、合計N枚あります。
カードは1からNまで順に上から積まれています。いちばん上が1のカードです。
上からAi番目のカードを抜いていちばん上に積みます。これを1回のシャッフルとします。
M回のシャッフルが行われた後にいちばん上にあるカードの数字はいくつでしょう？

入力

N M
A1A2…Am

Nはカードの最大の数字であり枚数。(1≤N≤50)
Mはシャッフルの回数。(1≤M≤100000)
Aiはi回目のシャッフルで上からAi番目のカードを抜き上に積むことをあらわす。(1≤Ai≤N)

出力

M回のシャッフルを行った後でいちばん上にあるカードの数字を答えよ。
最後に改行を忘れずに。

サンプル

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

最初に1から3までの3枚のカードが積まれています。上から1,2,3の順です。
1回目のシャッフルで上から2番目の2の数字のカードを抜いていちばん上に積みます。
よって、いちばん上のカードは2になります。

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

最初に1から3までの3枚のカードが積まれています。上から1,2,3の順です。
1回目のシャッフルで上から3番目の3の数字のカードを抜いていちばん上に積みます。
カードは上から順に3,1,2の順で積まれています。
2回目のシャッフルで上から2番目の1の数字のカードを抜いていちばん上に積みます。
よって、いちばん上のカードは1になります。

サンプル3
入力
4 4
1 1 1 1
出力
1

最初に1から4までの4枚のカードが積まれています。上から1,2,3,4の順です。
上から1番目のカードを抜いて上に積むシャッフルを4回行います。
カードの順番はまったく動きません。よって、いちばん上のカードの数字は1です。

サンプル4
入力
10 8
6 10 4 2 7 1 4 3
出力
10

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