2003/Contest/ソウル大会

Problem E : Marathon

問題概要

駅伝大会が行われる。ルールは以下の通り。(とりあえず原文のままで)

   l Each team consists of exactly N runners.
   l The winner is the team that runs the longest distance for D days.
   l For each day, exactly one runner from each team should run.
   l If a team member runs on a particular day, that team member should run for the entire day. That is, runner exchanges are only possible at the beginning of each day.
   l Each of the N runners on a team should run for at least one day, but at most three days.
   l If a runner participates in running for a day or for a sequence of days, and then, is switched with another runner, he/she cannot participate in the marathon again.

チームメンバーそれぞれについて

a : 一日で走れる距離

b : 二日で走れる距離(合計)

c : 三日で走れる距離(合計)

が与えられます。このチームがこの駅伝で走れる最長距離を出力せよ。という問題です。

与えられる値はすべて整数。0 < N <= 50,0 < D <=150,a <= b <= c。入力が不正、またはルール上大会に出場できないならば-1を出力します。

難易度

普通。

解法

(n日目に走れる距離をLnとします)

参加者をmax{L2,(L2+L3)/2} をキーとして大きい順にソートし、順に余計に走らせるようにすればO.K.。L2 > (L2 + L3)/2 ならばとりあえず二日間だけ。L2 < (L2 + L3)/2 なら三日間。

とりあえず二日間走ることが決まった人については、L3をキーにして参加者のソートされた列に再度挿入し、再度選択されたら3日間走ることにします。

(このやり方の場合、)最後の一日は別処理が必要。

議論・その他

もしある人が二日以上走った場合

   一日目に走れる距離 > 二日目に走れる距離 > 三日目に走れる距離

を仮定できると、問題が簡単になりますが、問題文を読む限りそうでは無いようです。


ファイルを添付する

[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

Last-modified: 2009-11-06 (金) 13:26:46 (3243d)