▶ 問題番号【０１】勉強の時間問

配点：４

題

三度の飯よりゲーム好きのだいご君は暇さえあればゲームばかりしていました。ですが、だいご君も高校３年生。クラスはもう受験モードに入っています。
受験勉強をするからには、当然ゲームで遊べる時間が短くなってしまいます。
まずは 1 日に勉強をする時間を決めて、残った時間をゲームなどに使うことにしましたが、だいご君は今まで計画を守れたためしがありませんでした。
見かねたあなたは、だいご君の勉強時間を管理するプログラムを書くことにしました。
1 日にやらなければならない勉強の目標時間を t、勉強を開始した時刻を s、終了した時刻を f とおきます。1 日で勉強した時間の合計が t 以上であるかをチェックし、達していない場合は足りない時間を求めます。なお、時間は 1 時間を 1 単位とし、分や秒は考えないものとします。時刻は 24 時間
表記で 1 時間単位で表します。
また、勉強できる時間帯は 6 時から 22 時までで、それぞれ行った勉強時間は重複しません。
1 日の勉強の目標時間と、実際に勉強した時間の情報（勉強の回数 n、それぞれの勉強の開始時刻 s と終了時
刻 f）を入力とし、勉強時間の合計が目標に達しているかを調べ、達していれば ”OK”（半角英字）を、達していない場合は足りない時間を出力するプログラムを作成してください。ただし、n は 1 以上 10 以下とし、s、fは、6 以上 22 以下とします
例：目標時間を勉強した時間の計算

目標時間

10 時間

14 時間

勉強した時間
6 時~11 時＝ 5 時間12 時~15 時＝ 3 時間18 時~22 時＝ 4 時間

6 時~11 時＝ 5 時間13 時~20 時＝ 7 時間パソコン甲子園２０１１予選問題 問題番号０１OK!!

2 時間不足【１／３ページ】

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下のとおりです。
1 行目 １日の目標時間 t（整数）2 行目 勉強の回数 n（整数）3 行目 第 1 の勉強の開始時刻 s 終了時刻 f（整数 整数；半角空白区切り）：
n+2 行目 第 n の勉強の開始時刻 s 終了時刻 f

出力

入力データセットごとに、OK または足りない時間を出力します。

パソコン甲子園２０１１予選問題 問題番号０１【２／３ページ】

入力例

出力例

10OK

326 11
12 15
18 22
142
6 1113 200

パソコン甲子園２０１１予選問題 問題番号０１【３／３ページ】

▶ 問題番号【０２】カロリー計算

問

配点：4題

天高く馬肥ゆる秋。そろそろ食べ物が美味しくなる季節です。高校生のよしお君も、テレビや読書のお供についついお菓子に手が伸びてしまいます。そのせいか最近体重は増える一方で、健康的にもよろしくありません。しかしどうしても直ぐに間食がやめられないよしお君は、お菓子の栄養素やカロリーが制限された場合に、食べたいお菓子を、食べてもよいお菓子と食べてはいけないお菓子に分類することにしました。
食べ物には 3 大栄養素と呼ばれる「たんぱく質」「脂質」「炭水化物」の３つの栄養素が含まれています。１g（グラム）あたりたんぱく質と炭水化物は 4kcal（キロカロリー）、脂質は 9kcal と計算されます。たとえば、下の表によると番号１のケーキにはタンパク質 7g、脂質 14g、炭水化物 47g が含まれています。これをもとに含まれるカロリーを計算すると、4 × 7 + 9 × 14 + 4 × 47 = 342 kcal となります。その他も同様に計算されています。

番号

名前

たんぱく質(g)脂質(g)炭水化物(g)カロリー(kcal)

1

ケーキ

71447342

2

ポテトチップス

53555555

3

どら焼き

6359287

4プリン

6515129

分類の対象となるお菓子の個数 n と各お菓子の情報、制限の情報を入力とし、そのお菓子一つだけなら制限を超えることがない（食べてもよい）お菓子の一覧を出力するプログラムを作成してください。
お菓子の情報は、お菓子の番号 i、そのお菓子に含まれるたんぱく質の重量 p、脂質の重量 q、炭水化物の重量 r から成り立っています。制限の情報には、含むことができる最大のたんぱく質の重量 P、脂質の重量 Q、炭水化物の重量 R、および摂取することができる最大のカロリーC からなっており、タンパク質、脂質、炭水化物、カロリーのいずれかの一つでも超えると制限違反となり、「食べてはいけないお菓子」と判断されます。
お菓子の個数 n は 1 以上 1000 以下の整数、お菓子の番号 i は 1 以上 1000 以下の整数、各栄養素の重量 p, q,r は 0 以上 100 以下の整数で与えられます。各栄養素の制限値 P, Q, R は 0 以上 100 以下の整数、カロリーC は0 以上 1700 以下の整数とします。食べてもよいお菓子の一覧は、食べてもよいお菓子の番号を入力順に出力してください。なお、食べてもよいお菓子がなければ”NA”と出力してください。
上の表にある 4 個のお菓子について、P=10,Q=15,R=50,C=400 という制限の場合、ケーキとプリンはそれぞれの栄養素及びカロリーが制限値未満なので食べてもよいお菓子に分類されますが、ポテトチップスは炭水化物とカロリー、どら焼きは炭水化物の量が制限値を超えているため食べてはいけないお菓子に分類されます。

パソコン甲子園２０１１予選問題 問題番号０２【１／３ページ】

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下のとおりです。
1 行目 お菓子の数 n（整数）2 行目 第 1 のお菓子の情報 i p q r（整数 整数 整数 整数；半角空白区切り）
3 行目 第 2 のお菓子の情報：
n+1 番目 第 n のお菓子の情報
n+2 番目 各栄養素及びカロリーの制限値 P Q R C（整数 整数 整数 整数；半角空白区切り）

出力

入力データセットごとに、食べてもよいお菓子の番号または”NA”を出力します。

パソコン甲子園２０１１予選問題 問題番号０２【2／３ページ】

入力例

出力例

41

1 7 14 47

42 5 35 55

NA

3 6 3 59
4 6 5 15
10 15 50 400
21 8 10 78
2 4 18 33
10 10 50 300
0パソコン甲子園２０１１予選問題 問題番号０２【３／３ページ】

▶ 問題番号【０３】

問

金利計算

配点：６

題

金利は銀行に預けているお金に付き、その計算方法や利率は銀行によって様々です。利息と元金を合わせたものを元利と呼びますが、元利の計算方法として、利息を元金に組み入れずに計算する「単利」と利息を元金に組み入れて計算する「複利」というものがあり、より多くの元利を得るためにはこの差異を理解していなければなりません。
元利の計算方法は以下のようになります。
単利: 元利 = 元金 × �1 + 年数 ×

複利: 元利 = 元金 × �1 +100

年数年利率100年利率��
元利
45000
40000
35000
30000
25000

単利(10%)

20000

複利(5%)

15000
10000
0151015202530

年数

例：元利を同じ額（1万円）で始めた場合できれば、わずかな金利でもより多くお金を増やしたいと思うものです。相沢さんの家庭では、今まで預けていた銀行は金利が低い事に気づき、新しい銀行に乗り換えようとしています。しかし、相沢さん一家は金利のことについてあまり詳しく知らなかったので、金利に詳しいあなたに助けを求めてきました。比較すべき銀行の数は多いうえ、相沢さん一家以外にも助けを求められそうです。作業を効率化するためにより良い銀行を計算するプログラムを作成しておきましょう。
銀行の数 n、お金を預ける年数 y、各銀行の情報（銀行番号 b、金利の種類 t、年利率 r パーセント）を入力とし、最も元利が高くなる銀行番号を出力するプログラムを作成してください。ただし n、b はそれぞれ 1 以上50 以下の整数、y は 1 以上 30 以下の整数、r は 1 以上 100 以下の整数とします。また、金利の種類 t は、単利の場合は 1、複利の場合は 2 で与えられます。また、最も元利が高くなる銀行は一つだけです。

パソコン甲子園２０１１予選問題 問題番号０３【１／３ページ】

入力

複数のデータセットが入力として与えられます。入力の終わりはゼロひとつで示されます。各データセットは以下の通りです。
1 行目 n (整数)
2 行目 y (整数)
3 行目 第 1 の銀行の情報 b r t (すべて整数 ; 半角空白区切り)
4 行目 第 2 の銀行の情報：
n+2 行目 第 n の銀行の情報

出力

入力データセットごとに、最も元利が高くなる銀行番号を出力します。

パソコン甲子園２０１１予選問題 問題番号０３【２／３ページ】

入力例

出力例

22811 5 22 6 1291 5 22 6 10

パソコン甲子園２０１１予選問題 問題番号０３【３／３ページ】

▶ 問題番号【０４】四元数のかけ算

問

配点：６

題

複素数を拡張したものに四元数と呼ばれるものがあります。物体の回転などを表現するのに便利なので、ロボットの腕の制御などに使える便利な数です。四元数は、４つの実数𝑥、𝑦、𝑧、𝑤と特別な数（虚数を拡張したもの）𝑖、𝑗、𝑘を用いて、𝑥 + 𝑦𝑖 + 𝑧𝑗 + 𝑤𝑘と表されます。このような四元数の和は次のように定義されます。
(𝑥1 + 𝑦1 𝑖 + 𝑧1 𝑗 + 𝑤1 𝑘) + (𝑥2 + 𝑦2 𝑖 + 𝑧2 𝑗 + 𝑤2 𝑘) = (𝑥1 +𝑥2 ) + (𝑦1 + 𝑦2 )𝑖 + (𝑧1 + 𝑧2 )𝑗 + (𝑤1 + 𝑤2 )𝑘

一方、1、𝑖、𝑗、𝑘の間の積は次のように与えます。

1A

11iijkjkii-1-kjBjjkk-1-ik-ji-1

この表は、２つの特別な数AとBの積 ABを表しています。例えば、 𝑖と𝑗の積 𝑖𝑗は 𝑘であり、 𝑗 と𝑖の積𝑗𝑖は−kであることを表しています。

一般の四元数の積は、この関係を満たすように計算されます。例えば、2 つの四元数、1 + 2i + 3j + 4kと7 + 6𝑖 + 7𝑗 + 8𝑘の積は次のように計算します。

(1 + 2𝑖 + 3𝑗 + 4𝑘) × (7 + 6𝑖 + 7𝑗 + 8𝑘) = 7 + 6𝑖 + 7𝑗 + 8𝑘+14𝑖 + 12𝑖 2 + 14𝑖𝑗 + 16𝑖𝑘+ 21𝑗 + 18𝑗𝑖 + 21𝑗 2 + 24𝑗𝑘となり、上の表を適用することにより+ 28𝑘 + 24𝑘𝑖 + 28𝑘𝑗 + 32𝑘 2= −58 + 16𝑖 + 36𝑗 + 32𝑘となります。

4 つの係数𝑥、𝑦、𝑧、𝑤が整数でかつすべてがゼロとはならない 2 つの四元数(𝑥1 + 𝑦1 𝑖 + 𝑧1 𝑗 + 𝑤1 𝑘)と(𝑥2 + 𝑦2 𝑖 +𝑧2 𝑗 + 𝑤2 𝑘)を入力とし、その積(𝑥3 + 𝑦3 𝑖 + 𝑧3 𝑗 + 𝑤3 𝑘)をとする時の𝑥3 、𝑦3 、𝑧3、𝑤3 を出力するプログラムを作成してください。ただし、与えられる係数はすべて-1000 以上 1000 以下とします。

パソコン甲子園２０１１予選問題 問題番号０４【１／３ページ】

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下のとおりです。
1 行目 四元数の組の個数𝑛（整数）2 行目 第 1 の四元数の組の情報 𝑥1 𝑦1 𝑧1 𝑤1 𝑥2 𝑦2 𝑧2 𝑤2（すべて整数；半角空白区切り）

3 行目 第 2 の四元数の組の情報：𝑛 ＋1 行目 第𝑛の四元数の組の情報

出力

入力データセットごとに、四元数の積を出力します。

パソコン甲子園２０１１予選問題 問題番号０４【2／３ページ】

入力例

出力例

2-58 16 36 32

1 2 3 4 7 6 7 8-50 32 28 48

5 6 7 8 3 2 3 40

パソコン甲子園２０１１予選問題 問題番号０４【３／３ページ】

▶ 問題番号【０５】入力候補問

配点：１２題携帯電話には、メールなどの文章を効率良く入力するために入力候補を表示する機能が搭載されています。これは、使われる頻度が高い単語を記録しておき、入力された文字を頭文字に持つ単語を入力候補として提示するものです。例えば、普段”computer”という単語を多く入力しているなら、”c”と入力するだけで候補として”computer”が提示されます。
このような機能を自作するために、その基本部分として、記録されている文章の中から、指定された文字を頭文字に持つ単語を出現回数が多い順に出力するプログラムを作成しましょう。
記録された文章、文字 k（半角英字）を入力とし、その文字 k を頭文字に持つ単語を出現数の順に出力するプ
ログラムを作成してください。ただし、記録された文章は半角英小文字と半角空白からなり、文字数は 1 文字以上 1024 文字以下とします。空白によって区切られる単語は 1 文字以上の 20 文字以下であり、また空白が 2 つ以上連続して入力されることはありません。出現数が同じ単語が複数ある場合は、アルファベット順に、より若い文字が先にある単語から出力します。出力する単語は最大 5 つまでとします。該当する単語が存在しない場合は”NA”と出力してください。

パソコン甲子園２０１１予選問題 問題番号０５【１／３ページ】

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつで表されます。各データセッ
トは以下のとおりです。
1 行目 文章（半角英小文字及び半角空白の列）
2 行目 頭文字 k （半角英字）

出力

入力データセットごとに、指定された文字を頭文字にもつ単語または”NA”と出力します。

パソコン甲子園２０１１予選問題 問題番号０５【2／３ページ】

入力例
ben likes bananas the best among many fruits because bananas are sweet and cheap
bwinners get to visit aizu and the university of aizu and make many friends as wella
ask alex about the answer for the assignment on android appsaprogramming is both a sport and an intellectual puzzle
c0

出力例
banana because ben best
aizu and as
about alex android answer apps
NA

パソコン甲子園２０１１予選問題 問題番号０５【３／３ページ】

▶ 問題番号【０６】問

塗りつぶしゲーム

配点：１２題タブレット型の端末の流行は留まるところを知らず、携帯電話もその影響を受けたりしながら、私たちの生活のありとあらゆる所に浸透してきています。なぜここまで人々に受け入れられているのか。理由としては、指で画面にタッチして操作できる、直感的なインターフェースはその一端を担っていると言えるでしょう。
もちろんゲームの分野でもこの技術は利用され、新しい操作感を持つ様々な種類のゲームが作られています。
現在、ＡＺ社が開発しているゲームもその一つです。ＡＺ社のプログラマーであるあなたは、このゲームのロジックの一部分を開発することになりました。
このソフトウェア（ゲーム）の要件は以下の通りです。
・ 画面には x 列×y 行の 2 次元グリッドがあります。
・ グリッドのセルは赤(R)、緑(G)、茶(B)の 3 色のいずれかで塗られています。
・ セルの色を変更するボタン R、G、B があり、このボタンが押下されると一番左上(0,0)のセルがその色に変更されます。
・ 一番左上のセルの色が変更されると、そのセルの元の色と同じ色に塗られた隣接するすべてのセルが指定された色に変わります。すなわち、元の色が同じ色のセルでつながったセルはすべて指定された色に変更されます。
このようにグリッドを塗りつぶしていき、最終的にグリッド全体を一色にするというゲームです。少ない手順で解くと高得点が与えられます。
まずは、この最高得点を計算するため、このゲームを最短で解いた場合、最低何回選択ボタンを操作すればグリッドが一色になるかをもとめるプログラムを作ることにしました。
2 次元のグリッドのサイズ x×y と各セルの初期状態の色（R、G、B のいずれか）を入力とし、すべてのセルを同一色にするために必要な選択ボタンの操作回数の最小値を出力するプログラムを作成してください。ただし、x と y は 2 以上 10 以下とします。

変更を適用するセル

パソコン甲子園２０１１予選問題 問題番号０６

塗りつぶし領域【１／３ページ】

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつで示されます。
1 行目 x y（整数 整数；半角空白区切り）
2 行目 1 行目のセルの色 s1 … sx（すべて半角英字；半角空白区切り）：y＋1 行目 y 行目のセルの色出力

入力データセットごとに、ボタン操作の最少回数を出力します。

パソコン甲子園２０１１予選問題 問題番号０６【２／３ページ】

入力例

出力例

3 3

2R G B

4G G G

4G B B
2 4
R GG GR B
B R
4 3
G G B RG R R GB G G R
0 0

パソコン甲子園２０１１予選問題 問題番号０６【３／３ページ】

▶ 問題番号【０７】温泉旅行

問

配点：１２題

温泉好きのたけしさんは、次の長期休暇を利用してとある温泉地への旅行を計画しています。移動は長距離バスを乗り継ぎ、なるべくお金をかけずに目的地へたどり着きたいと思っています。
貯金があるとはいえ、資金に心許ないたけしさんは、おじいさんに相談することにしました。計画を聞いて感心したおじいさんは、たけしさんに特別な切符を渡しました。
その切符は、長距離バスの連続した 2 区間を 1 回だけ無料で乗れるというものでした。使いようによってはかなりの移動費削減が見込めますが、より大きな効果を発揮させるためにはしっかりした計画を練る必要があります。
出発地と目的地、及び中継地点が合わせて n 個、2 つの地点を結ぶ路線が m 個与えられます。各地点にはそれぞれ 1 から n までの数字が割り振られています。出発地は 1、目的地は n です。路線の情報は、その路線が結ぶ 2 つの地点 a と b、及びその料金 c で表されます。
おじいさんからもらった特別な切符の効力により、任意の地点から、一度だけ連続した 2 つの路線を料金 0で通過することができます。ただし、途中で目的地を通過しても、目的地にたどり着いたことにはなりません。
出発地、目的地、及び中継地点の総数 n と路線の数 m、各路線の情報を入力とし、料金の最小値を出力するプログラムを作成してください。ただし、必ず出発地から目的地へと到達する経路が存在するものとします。
また n は 2 以上 100 以下、c は 1 以上 1000 以下とします。

無料区間
271091113

出発地

21415486

目的地
95

パソコン甲子園２０１１予選問題 問題番号０７【１／３ページ】

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各デー
タセットは以下の通りです。
1 行目 n m （整数 整数；半角空白区切り）
2 行目 第 1 の路線の情報 a1 b1 c1 （整数 整数 整数；半角空白区切り）：
m+1 行目 第 m の路線の情報 am bm cm

出力

入力データセットごとに、料金の最小値を出力します。

パソコン甲子園２０１１予選問題 問題番号０７【２／２ページ】

入力例

出力例

2 151 2 503 27

1 2 5
2 3 56 91 2 7
1 3 9
1 5 142 3 102 4 15
3 4 113 5 24 5 9
4 6 80 0

パソコン甲子園２０１１予選問題 問題番号０７【３／３ページ】

▶ 問題番号【０８】タイムセール

問

配点：１２

題

より良い物を、より安く。今日もどこかのスーパーマーケットで行われるタイムセールでは、激しい闘いが繰り広げられています。
ここ会津にある「LL 堂」もそんなスーパーマーケットのひとつで、他の全国チェーン店と対抗すべく、少し変わったタイムセールを実施しています。一般的なタイムセールでは複数の商品が同じ時間に安くなるものですが、LL 堂では対象となる商品によって、タイムセールを開始する時間が別々に設定されているのです。こうすることによって他店との差別化を図っています。
坂井家は LL 堂をよく利用する家庭の一つです。そんな坂井家では、奥様主導のもと、次の日曜に行われるタイムセールに向けて作戦会議を開き、どのような順番で買い物をすれば値引きが最大となるかを分析することになりました。店内を熟知している坂井家は売り場の見取り図を書き、また欲しい品物がどこにあるか、値引きは幾らであるか、売り切れるまでの時間を把握することに成功しました。
ここまでは完璧だった坂井家ですが、分析を行える人がいませんでした。そこで坂井家と親交があったあな
たはプログラムを書くことにしました。一人の人が動くことを想定してシミュレーションを行います。
商品は 10 種類あり、数字 1 桁の商品番号 g によって区別されます。タイムセール情報には商品番号 g、値引き額 d、タイムセールの開始時刻 s と売り切れ時刻 e があります。
店内は横 x、縦 y のマスで構成される 2 次元グリッドで表され、マスごとに通路、商品棚のどちらかが割り当てられています。一つの商品棚には1 種類の商品があり、それは商品番号 g で区別されます。
どの商品を買ってもよいですが、同じ商品番号の商品を複数買ってはいけません。商品棚からは、上下左右に隣接する通路のマスならどんな向きでも商品を取れます。
タイムセールが始まる時刻から商品を取ることができますが、売り切れる時刻からは商品を取ることができません。また、時間は入店した時点で 0 から始まります。
移動は現在いるマスから上下左右の隣接する通路マスに移動することができますが、商品棚のマスに移動することはできません。グリッドで表される店の外に出ることもできません。１回移動する毎に１単位時間経過します。また、商品を取る時間は考えないものとします。
店内の見取り図と買い物をする人の初期位置と商品のタイムセール情報を入力とし、取ることのできた商品の値引き額の合計の最大値を出力するプログラムを作成してください。ただし、店舗の大きさ x, y は 3 以上 20以下、タイムセール情報の数 n は１以上 8 以下、タイムセールが始まる時刻 s、商品が売り切れる時刻 e はともに 0 以上 100 以下とします。

パソコン甲子園２０１１予選問題 問題番号０８【１／３ページ】

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下の通りです。
1 行目 店舗の大きさ x y（整数 整数；半角空白区切り）
2 行目 １行目の店内情報

m1 m2 … mx（すべて半角文字；半角空白区切り）

各記号の値と意味は次の通りです。
. (ピリオド)：通路のマス

数字：商品の番号P：買い物をする人の初期位置のマス

3 行目 2 行目の店内情報：
y+1 行目 y 行目の店内情報
y+2 行目 タイムセール情報の数 n（整数）y+3 行目 第 1 のタイムセール情報 g d s e（すべて整数；半角空白区切り）
y+4 行目 第 2 のタイムセール情報：
y+n+2 行目 第 n のタイムセール情報

出力

入力データセットごとに、取ることのできる商品の値引き額合計の最大値を出力します。

パソコン甲子園２０１１予選問題 問題番号０８【２／３ページ】

入力例

出力例

6 51801 1 . 0 0 4
1 . . . . .
. . 2 2 . .
. . 2 2 3 3
P . . . . .
50 50 5 10
1 20 0 10
2 10 5 15
3 150 3 54 100 8 90 0

パソコン甲子園２０１１予選問題 問題番号０８【３／３ページ】

▶ 問題番号【０９】ばらばら饅頭問

配点：１６題会津若松市にある和菓子屋・友栗堂の店長さんは、とても腕のいい職人さんなのにちょっと気分屋なのが玉にキズです。店長さんの作る饅頭はとても美味しいのですが、その時の気分によって大きさがまちまちになってしまいます。時には普通の饅頭の何倍もの大きさで作ってしまうこともあるほどです。大きさや重さをいちいち量り、一つ一つ違う値段をつけるのはお客さんにとっても店にとっても不便なので困りものでした。
見かねた店長さんの奥さんは、この大きさと重さがばらばらな饅頭を袋に詰めて売り出すことを思いつきました。一定の重さになるように饅頭を袋に詰めて売れば、一つ一つの大きさはばらばらでも一定の値段で売り出すことが出来ますし、どんな饅頭が入っているのか開けるまでわからないというサプライズも売りになるかもしれません。
「ばらばら饅頭」という名前で売りだしたところ、新しいアイディアが話題となり友栗堂はたちまち評判となりました。しかし、問題もあり、袋に入れる饅頭の組み合わせ方によって作れる「ばらばら饅頭」の数が変わり、無駄が発生してしまうことがありました。アルバイトで友栗堂に来ていたあなたは無駄なく袋に詰めるためにプログラムをつくることにしました。
饅頭の重さは 1 から 9 の 9 種類あります。
袋に詰める時には、饅頭の重さの合計がぴったり 10 になるように詰め込みます。饅頭の組み合わせ方は1+1+2+4+2=10 や 1+1+1+1+1+5=10 などで、同じ重さの饅頭をいくつ使っても構いません。

作られる饅頭の個数 n と饅頭の重さの情報を入力とし、作ることのできる「ばらばら饅頭」の最大の数を出力とするプログラムを作成してください。ただし、n は 2 以上 100 以下の整数とします。

パソコン甲子園２０１１予選問題 問題番号０９【１／３ページ】

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつで示されます。各データセットは以下の通りです。
1 行目 饅頭の個数 n（整数；半角空白区切り）
2 行目 各饅頭の重さ m1

出… mn（すべて整数；半角空白区切り）

力

入力データセットごとに、詰め込むことのできた「ばらばら饅頭」の最大の数を出力します。

パソコン甲子園２０１１予選問題 問題番号０９【２／３ページ】

入力例

出力例

514 9 1 3 841048 5 3 6 2 1 4 5 4 595 7 3 8 2 9 6 4 10

パソコン甲子園２０１１予選問題 問題番号０９【３／３ページ】

▶ 問題番号【１０】氷の迷路

問

配点：１６

題

四角のマスを縦横にならべた長方形の迷路があります。この迷路では東西南北の隣接するマスへ移動しながら、スタートのマス S を出発し、ゴールのマス G を目指します。マスの種類には、平原、山、氷の３種類があります。S と G は、平原のマスに置かれています。平原のマスには移動できますが、山のマスには移動できません。氷のマスは移動できますが、条件によって氷が割れ動けなくなります。


氷のマスは東西南北に隣接するもの全体でひとつの塊として扱われます。



氷の塊のなかで、マスの個数の半分より多くのマスに移動すると、塊全体が割れます。
例えば、図１は与えられた迷路の最短経路のステップ数で１１であることを示しています。
北

東

西

南
図１
しかし、図２のように氷のマスを通って近道をしようとすると、大きさが６の氷の塊に対する４回目の移動後に動けなくなってしまい G には到達できません。

図２

パソコン甲子園２０１１予選問題 問題番号１０【１／３ページ】

このような迷路の情報を入力とし、SからGまでの最短経路のステップ数を求めるプログラムを作成してください。マスの種類はそれぞれ以下の文字で表されます：
文字（半角）

マスの種類. （ピリオド） 平原#（シャープ） 山
X

氷

与えられる迷路は必ず解けるものとします。迷路はその東西方向のマスの数x、南北方向のマスの数yとx×y個の文字として与えられます。x、yはともに2以上12以下とします。

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下のとおりです。
1 行目 x y （整数 整数；半角空白区切り）
2 行目 迷路の 1 行目の情報（長さ x の半角英文字列）:
y＋1 行目 迷路の y 行目の情報

出力

入力データセットごとに、最小のステップ数を出力します。

パソコン甲子園２０１１予選問題 問題番号１０【２／３ページ】

入力例

出力例

5 5

11.X.S.

10.X#..

10.XX##

33.#XG.
..X..
7 3
SXX.XXG
X.#.#X.
XXX.XX#
4 4
S...
X.X.
GX..
...X
10 10..XXXXX.XX.X.#.#X.XX
SX.#X.X..X#X.##.X.XX..XXXX#.XX##.##.##XX....X.XX#X.##X..#X#X....XX#..X...#XXG..X
0 0

パソコン甲子園２０１１予選問題 問題番号１０【３／３ページ】