Sorry, no corresponding articles.
--
--
--
no comments

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Related Posts

Next and Prev

Comments + Add Comment

Leave a comment

05
05
2011
0 comments

ACMプログラミングコンテストの問題サンプル

ACMのコンテストに参加する学生や彼らに指導するCPをサポートするため、
彼らの感覚を理解しようと過去問やネット上の例題を解いてます。


10問ちょっと解きました(それ以外は解けないorさっぱりわからない多数)が、
その中で一番簡単でわかりやすい問題を紹介します。


Hanafuda Shuffle


2004年度の日本の国内予選(愛媛大会)の一番最初の問題です。

原文


日本の国内予選は日本語で出題らしいのですが、大会は基本的に全て英語です。

導入

カードの山を混ぜて切る方法はいろいろとある.日本のカード遊びである「花札」における花札混ぜ切りは,札を切る方法の一つである.以下に,花札混ぜ切りの方法を示す.

n枚のカードの山がある.図1に示すように,山の一番上からp枚目の札から連続したc枚の札を抜き取り,それをそのまま山の上に置く.この操作(カット操作という)を繰り返し行う.

花札混ぜ切りをシミュレートし,最終的に山の一番上にくる札を答えるプログラムを書きなさい.

A.gif
Figure 1: Cutting operation

Input

入力は複数のデータセットから構成される.各データセットは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を二つ含む行によって表される.

各入力行は一つの空白で区切られた二つの整数を含む.行内にその他の文字はない.

Output

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

Sample Input

5 2
3 1
3 1
10 3
1 10
10 1
8 3
0 0

Output for the Sample Input

4
4

英語版


問題文を英語に直すとこのようになります。
※北京大学のサイトより抜粋

Description

There are a number of ways to shuffle a deck of cards. Hanafuda shuffling for Japanese card game 'Hanafuda' is one such example. The following is how to perform Hanafuda shuffling.

There is a deck of n cards. Starting from the p-th card from the top of the deck, c cards are pulled out and put on the top of the deck, as shown in Figure 1. This operation, called a cutting operation, is repeated.

Write a program that simulates Hanafuda shuffling and answers which card will be finally placed on the top of the deck.

1978_1.jpg
Figure 1: Cutting operation

Input

The input consists of multiple data sets. Each data set starts with a line containing two positive integers n (1 <= n <= 50) and r (1 <= r <= 50); n and r are the number of cards in the deck and the number of cutting operations, respectively.

There are r more lines in the data set, each of which represents a cutting operation. These cutting operations are performed in the listed order. Each line contains two positive integers p and c (p + c <= n + 1). Starting from the p-th card from the top of the deck, c cards should be pulled out and put on the top.

The end of the input is indicated by a line which contains two zeros.

Each input line contains exactly two integers separated by a space character. There are no other characters in the line.

Output

For each data set in the input, your program should write the number of the top card after the shuffle. Assume that at the beginning the cards are numbered from 1 to n, from the bottom to the top. Each number should be written in a separate line without any superfluous characters such as leading or following spaces.

Sample Input

5 2
3 1
3 1
10 3
1 10
10 1
8 3
0 0

Sample Output

4
4

補足


サンプルのインプットは以下の2つのデータセットから成り立ちます。

5 2
3 1
3 1



10 3
1 10
10 1
8 3

1つ目のデータセットでは、5枚の山札を2回切ります。
(最初:下から数えて5番目のカードが一番上)
1回目:上から3枚目のカード(3)のみを抜いて、一番上に置きます。
(一番上は3に:山札は上から3,5,4,2,1)
2回目:上から3枚目のカード(4)のみを抜いて、一番上に置きます。
(一番上は4に:山札は上から4,3,5,2,1)

2つ目のデータセットでは、10枚の山札を3回切ります。
(最初:下から数えて10番目のカードが一番上)
1回目:一番上のカードから10枚(つまり全部)抜いて、一番上に置きます。
(変らず10のカードが一番上)
2回目:上から10枚目のカード(1)のみを抜いて、一番上に置きます。
(一番上は1に:山札は上から1,10,9,8,7,6,5,4,3,2)
3回目:上から8枚目のカード(4)から10枚目のカード(2)までを一番上へ。
(一番上は4に:山札は上から4,3,2,1,10,9,8,7,6,5)

ゆえにサンプルの出力結果は、どちらも4となります。

問題通りにプログラムを組めばよい&変数上限が低くアルゴリズムの計算量が少ないので、
とても素直で参加全チームが解けるような問題です。

Comments + Add Comment

Leave a comment

Urgench Time

Urgench Temp

Click for Urgench, Uzbekistan Forecast

Tweets

Counter (visitor)

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。