ACM 国際大学対抗プログラミングコンテスト (ACM/ICPC) は、大学生を対象とした世界的規模のプログラミングコンテスト。そこに出された過去問を解いていきたいと思う。

大会は1チーム(競技者3人+コーチ1人)で、3時間の間に6問を解くプログラムを書く形で競うらしいが、毎年ルールが少しずつ変わるようだ。使用できる言語は C++、C、Java、Pascal 。

ここでの解答プログラムはC言語で作成し、Linux (Fedore core 1) 上でコンパイルし、実行する。
なお、コンパイラーは Gnu GCC 3.3.2 20031022 (Red Hat Linux 3.3.2-1)。

Hanafuda Shuffle — 2004年 愛媛大会 国内予選 問題A

【問題】
 カードの山を混ぜて切る方法はいろいろとある.日本のカード遊びである「花札」における花札混ぜ切りは,札を切る方法の一つである.以下に,花札混ぜ切りの方法を示す.
 n枚のカードの山がある.図1に示すように,山の一番上からp枚目の札から連続したc枚の札を抜き取り,それをそのまま山の上に置く.この操作(カット操作という)を繰り返し行う.
 花札混ぜ切りをシミュレートし,最終的に山の一番上にくる札を答えるプログラムを書きなさい.
 イラストは こちら。

【入力】
 入力は複数のデータセットから構成される.各データセットはnとr という二つの正の整数を含む行から始まる.ただし,nは 1 <= n <= 50であり,rは1 <= r <= 50である. nとrはそれぞれ山にある札の枚数とカット操作の回数を表す.
 データセットはさらにr行続く.その各行は1回のカット操作を表しており,これらの操作は順に実行される.各行はpとcの二つの正の整数を含む.ただし,pとcは p + c <= n + 1を満足している.札の山の一番上からp枚目の札から,c枚の札を山から抜き取り,その山の一番上に置く.
 入力の終わりは0を二つ含む行によって表される.
 各入力行は一つの空白で区切られた二つの整数を含む.行内にその他の文字はない.

【出力】
 入力の各データセットに対して,最初に一番下を1番として順にn番までの札が積み上げられた山を仮定して,山を混ぜて切り終わったとき,山の一番上にある札の番号を出力しなさい.ただし,番号は前後に空白のような余分な文字を含まないこと.

入力例
5 2
3 1
3 1
10 3
1 10
10 1
8 3
0 0

【出力例】
4
4

Comments are closed.

Post Navigation