When Can We Meet? — 2003年 会津大会 国内予選 問題A

英語の概略をすこし書くが、参考程度にしかならないだろう。

[ Problem ]
 The ICPC committee would like to have its meeting as soon as possible to address every little issue of the next contest. However, members of the committee are so busy maniacally developing (possibly useless) programs that it is very difficult to arrange their schedules for the meeting. So, in order to settle the meeting date, the chairperson requested every member to send back a list of convenient dates by E-mail. Your mission is to help the chairperson, who is now dedicated to other issues of the contest, by writing a program that chooses the best date from the submitted lists. Your program should find the date convenient for the most members. If there is more than one such day, the earliest is the best.
 「委員会会議を開きたいので、 日程の調整をして欲しい。つまり、できるだけ多くの委員が出席できる日にちを決めること。出席できる委員の数が同数の日にちがいくつもある場合は、最も早い日にちにすること。」

[ Input ]
 The input has multiple data sets, each starting with a line containing the number of committee members and the quorum of the meeting.

   N Q
 Here, N, meaning the size of the committee, and Q meaning the quorum, are positive integers. N is less than 50, and, of course, Q is less than or equal to N.
 「N (50以下の正の整数)、委員の数。 Q (N以下の正の整数)、定足数(会議の成立に必要な最低出席者数)。」

 N lines follow, each describing convenient dates for a committee member in the following format.
   M Date1 Date2 … DateM
Here, M means the number of convenient dates for the member, which is an integer greater than or equal to zero. The remaining items in the line are his/her dates of convenience, which are positive integers less than 100, that is, 1 means tomorrow, 2 means the day after tomorrow, and so on. They are in ascending order without any repetition and separated by a space character. Lines have neither leading nor trailing spaces.
 「M (0以上の整数)、各委員の出席できる日にちリストの長さ。日にちリスト Datei (100以内の正の整数、1は明日、2は明後日を表す。)。」

 A line containing two zeros indicates the end of the input.
 「入力最後の行にゼロが2つ並ぶ。」

[ Output ]
 For each data set, print a single line containing the date number convenient for the largest number of committee members. If there is more than one such date, print the earliest. However, if no dates are convenient for more than or equal to the quorum number of members, print 0 instead.
 「最も多くの委員が出席できる日にち(整数)を表示せよ。ただし、出席できる委員が同数の日にちが複数ある場合、最も早い日にちにすること。また、定足数未満の場合は、代わりに0で表示すること。」

[ Sample Input ]
3 2
2 1 4
0
3 3 4 8
3 2
4 1 5 8 9
3 2 5 9
5 2 4 5 7 9
3 3
2 1 4
3 2 5 9
2 2 4
3 3
2 1 2
3 1 2 9
2 2 4
0 0

[ Output for the Sample Input ]
4
5
0
2

Water Tank — 2004年 愛媛大会 国内予選 問題E

【問題】
 伝次郎氏は理科の先生である.彼は,水の流れに関する革新的な実験をするために水槽を注文していたのだが,今日ちょうどその水槽が届いたところである.

 水槽は,幅100cm,高さ50cm,奥行き30cmの大きさである.水槽の内部を区切るために,数枚の「区切り板」を水槽の側面と平行に水槽の底に設置する.区切り板の横幅はどれも水槽の奥行きである 30cm と等しい.板の高さは水槽の側板の高さである 50cm よりは低い.また,板の高さは,板ごとにどれも異なっている. 区切り板は十分に薄いので,その厚さは無視できるものとする.

 水槽の上方にはいくつかの蛇口があり,実験開始と同時に蛇口を開いて水を水槽へと注ぎ入れる.実験開始時に水槽は空である.あなたの仕事は,水槽内における水の流れをシミュレートするプログラムを書くことである.

【入力】
 入力は,複数のデータセットからなる. D はデータセットの数を表す.
   D
   DataSet1
   DataSet2
   …
   DataSetD

 各データセット (DataSetd , ただし 1 <= d <= D) の形式は次の通りである.
   N
   B1 H1
   B2 H2
   …
   BN HN
   M
   F1 A1
   F2 A2
   …
   FM AM
   L
   P1 T1
   P2 T2
   …
   PL TL

 データセットの各行には1個または2個の整数が現れる.

 N は彼が設置する区切り板の数を表す. Bi はi 番目の区切り板の x座標 (単位はcm) であり,Hi はその区切り板の高さ (単位はcm) を表す.ここで 1 <= i <= N である.
 Hi はどれも異なっている.以下の条件が成り立つと仮定してよい.
   0 < N < 10 ,
   0 < B1 < B2 < ... < BN < 100 ,
   0 < H1 < 50 , 0 < H2 < 50 , ..., 0 < HN < 50.

 M は水槽の上方に設置された水道の蛇口の数を表す. Fj はj番目の蛇口の x座標 (cm単位) であり, Aj はその蛇口から注ぎ込まれる水の流量 (cm3/秒)を表す.ただし 1 <= j <= Mである.
 区切り板の真上に蛇口が来ることはない.すなわち Fj が Bi と一致することはない.
 以下の条件が成り立つと仮定してよい.
   0 < M <10 ,
   0 < F1 < F2 < ... < FM < 100 ,
   0 < A1 < 100, 0 < A2 < 100, ... 0 < AM < 100.

 L は水の高さを測定する回数である. Pk は測定する場所の x 座標 (cm単位) であり, Tk は測定をする時刻 (実験開始からの経過時間,秒単位) である.ただし 1 <= k <= L である.
 Pk が Bi と一致することはない.
 以下の条件が成り立つと仮定してよい.
   0 < L < 10 ,
   0 < P1 < 100, 0 < P2 < 100, ..., 0 < PL < 100 ,
   0 < T1 < 1000000, 0 < T2 < 1000000, ... , 0 < TL < 1000000.

【出力】
 各データセットに対して,実数を1個ずつ含む行を L行出力しなさい.その実数は,指定された時刻 Tk における,指定された x 座標 Pk の水の高さ(cm)を表していること.
 解答の誤差は0.001を超えてはいけない.この条件を満たす限り,小数点以下は何桁数字を表示してもかまわない.
 水槽が満杯になって以後は,水槽の縁から水が溢れ出るのでどのPkの水の高さも水槽の高さと同じ,すなわち 50cm となる.

入力例
2
5
15 40
35 20
50 45
70 30
80 10
3
20 3
60 2
65 2
6
40 4100
25 7500
10 18000
90 7000
25 15000
25 22000
5
15 40
35 20
50 45
70 30
80 10
2
60 4
75 1
3
60 6000
75 6000
85 6000

【出力例】
0.666667
21.4286
36.6667
11.1111
40.0
50.0
30.0
13.3333
13.3333

Circle and Points — 2004年 愛媛大会 国内予選 問題D

【問題】
 xy平面上にN個の点が与えられる.半径1の円をxy平面上で動かして,それらの点をなるべくたくさん囲むようにする.このとき,最大でいくつの点を同時に囲めるかを答えなさい.ここで,ある円が点を「囲む」とは,その点が円の内部または円周上にあるときをいう.
 イラストは こちら

【入力】
 入力にはいくつかのデータセットが並び,最後に’0’一文字だけからなる行で終わる.各データセットは整数一つを含む行で始まり,そのデータセットに含まれる点の個数Nを与える.その後,点の座標を記述する N行が続く.その各行は,点のx座標およびy座標を記述する二つの小数XとYからなる.座標は小数点以下5桁で与えられる.
 1 <= N <= 300, 0.0 <= X <= 10.0, および0.0 <= Y <= 10.0と仮定してよい.二つの点の距離が0.0001より近くなることはない.二つの点の距離がほぼ2.0になることもない.より正確には,一つのデータセット中の任意の2点間の距離dが1.9999 <= d <= 2.0001を満たすことは決してない.最後に,一つのデータセット中の三つの点が,半径1の円周に,ともに非常に近くなることはない.より正確には,一つのデータセット中の任意の3点をP1, P2, P3とし,xy-平面上のある点からそれぞれへの距離をd1, d2, d3とする.このとき,0.9999 <= di <= 1.0001 (i = 1, 2, 3)が同時に成り立つことは決してない.

【出力】
 それぞれのデータセットに対して,データセット中の点で,半径1の円一つで同時に囲むことができる点の最大数を出力しなさい.それ以外の文字は,先頭や末尾の空白を含め,出力してはならない.

入力例
3
6.47634 7.69628
5.16828 4.79915
6.69533 6.20378
6
7.15296 4.08328
6.50827 2.69466
5.91219 3.86661
5.29853 4.16097
6.10838 3.46039
6.34060 2.41599
8
7.90650 4.01746
4.10998 4.18354
4.67289 4.01887
6.33885 4.28388
4.98106 3.82728
5.12379 5.16473
7.84664 4.67693
4.02776 3.87990
20
6.65128 5.47490
6.42743 6.26189
6.35864 4.61611
6.59020 4.54228
4.43967 5.70059
4.38226 5.70536
5.50755 6.18163
7.41971 6.13668
6.71936 3.04496
5.61832 4.23857
5.99424 4.29328
5.60961 4.32998
6.82242 5.79683
5.44693 3.82724
6.70906 3.65736
7.89087 5.68000
6.23300 4.59530
5.92401 4.92329
6.24168 3.81389
6.22671 3.62210
0

【出力例】
2
5
5
11

Unit Fraction Partition — 2004年 愛媛大会 国内予選 問題C

【問題】
 分子が1であり分母が正整数である分数を単位分数と呼ぶ.正の有理数 p/q を有限個の単位分数の和として表現したものを, p/q の単位分数への「分割」と呼ぶ.例えば, 1/2 + 1/6 は 2/3 の単位分数への分割である.足し算の順序の違いは無視する.例えば, 1/6 + 1/2 を 1/2 + 1/6 と区別しない.
 与えられた四つの正整数 pと qと aと n に対して, p/q の単位分数への分割で以下の二つの条件を満たすものの個数を数えなさい.
   分割は n個以下の単位分数の和である.
   分割に含まれる単位分数の分母の積は a 以下である.

例えば, (p,q,a,n) = (2,3,120,3) ならば, 4と報告しなければならない.なぜならば,

で,条件を満たす分割が尽くされるからである.

【入力】
 入力は,200個以下のデータセットの並びで,その後に終端行が続く.
 データセットは四つの正整数 p と q と a と n を含む行で, p,q <= 800 かつ a <= 12000 かつ n <= 7 を満たす.それらの整数は空白で区切られる.
 終端行は,空白で区切られた四つのゼロを含むちょうど1行で構成される.これは入力データの一部ではなく,入力終了を表す印(しるし)である.

【出力】
 出力は各行に一つの整数がある何行かで構成されなければならない.その他の文字は出力中に出現してはならない.
 データセット p, q, a, n に対応する出力の整数は p/q の n個以下の単位分数への分割で,単位分数の分母の積が a 以下となるものをすべて数えた個数でなければならない.

入力例
2 3 120 3
2 3 300 3
2 3 299 3
2 3 12 3
2 3 12000 7
54 795 12000 7
2 3 300 1
2 1 200 5
2 4 54 2
0 0 0 0

【出力例】
4
7
6
2
42
1
0
9
3

Red and Black — 2004年 愛媛大会 国内予選 問題B

【問題】
 正方形のタイルが敷き詰められた長方形の部屋がある.タイルの色は赤か黒である.最初に一人の人が部屋の黒いタイルの上に立っている.あるタイルからは隣接する四つのタイルに移動することができる.ただし,赤いタイルの上に移動することはできない.移動できるのは黒いタイルの上だけである.
 上記の移動を繰り返すことによって到達できるタイルの数を答えるプログラムを書きなさい.

【入力】
 入力は複数のデータセットからなる.データセットは,WとHという二つの正の整数からなる行で始まる.WとHは部屋のx方向, y方向にタイルがいくつ並ぶかを表す.WとHは20以下である.
 その後ろにH行続く.それぞれの行にはW個の文字が含まれている.それぞれの文字は次に示すようにタイルの状態を表す.
    ’.’ – 黒いタイル
    ’#’ – 赤いタイル
    ’@’ – 黒いタイルの上の人(一つのデータセットに1度だけ出現)
 入力の終わりは0を二つ含む行で表される.

【出力】
 入力のデータセットごとに,最初の位置から到達可能なタイルの数を1行で出力しなさい(最初のタイルも含む).

入力例
6 9
….#.
…..#
……
……
……
……
……
#@…#
.#..#.
11 9
.#………
.#.#######.
.#.#…..#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#…….#.
.#########.
………..
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
…@…
###.###
..#.#..
..#.#..
0 0

【出力例】
45
59
6
13

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