SuperCon '95 本選課題

                            石 選 び 問 題

〔課題〕

  ＊石選び問題とは＊

  まず，異なった重さの石が $n$ 個与えられているものとする．このとき，与え
  られた目標の重さに対し，合計がその重さになるような石の選び方を求める問
  題（解が複数ある場合には，その一つを求めればよい）．

具体的には，決められた重さの 40 個の石（slist 参照）に対して，以下の各問題
ジャンルを解くプログラム  s5.c, s10.c, s.c を作成するのが課題．

問題セット：
（ジャンルＡ）石 5 個でできる重さ 10 問
（ジャンルＢ）石 10 個でできる重さ 10 問
（ジャンルＣ）石 ? 個でできる重さ 10 問

〔審査方法〕

審査委員会では，上記のプログラム 3 本を，順次（s5.c, s10.c, s.c の順）実
行するプログラムを走らせ，総経過時間（Total Elapsed Time）が 10 分となっ
た時点で打ち切る．その際，以下の方法でポイントを数え，何ポイント取れるか
で競う．

ポイントの決め方
（ジャンルＡ）正解 1 つにつき 1 ポイント
（ジャンルＢ）正解 1 つにつき 5 ポイント
（ジャンルＣ）正解 1 つにつき 10 ポイント
近似解： 誤差 100 の解 1 つにつき x 0.1 ポイント
         以下，誤差 1000 の解，x 0.01 ポイント，... となる．


〔計算機性能と使用条件〕

審査に用いるコンピュータは C916/12256（クレイ社製）で，以下の性能を持って
いる．

クロックスピード 4 ナノ秒，CPU 数： 12， メモリ： 2 ギガバイト
1 CPU あたりのピーク性能： 1 ギガフロップス
（つまり 1 秒間に $10^9$ 回の浮動小数点演算が可能）

ただし，今回は使用 CPU 数 9 個以下であること，使用可能メモリ 128 メガバイト
以下であること，といった条件を設ける．なお，審査の際は，他のジョブをすべて
停止し，対象プログラムだけを走らせて時間を測る．