問題０１

パターンの回転（４０点）

この問題は、矢沢久雄賞の対象となります。
8文字×8行のパターンを右回りに90度、180度、270度回転させて出力し終了するプログラムを作成して
ください。

入力
8文字×8行からなるパターン（半角英数字および半角シャープ“#”と半角アスタリスク“*”）

出力90（半角数字固定）
90度回転させたパターン
180（半角数字固定）
180度回転させたパターン
270（半角数字固定）
270度回転させたパターン

入力例

出力例

#*******#*******#*******#*******#*******#*******#*******########

90#########*******#*******#*******#*******#*******#*******#*******
180########*******#*******#*******#*******#*******#*******#*******#
270*******#*******#*******#*******#*******#*******#*******#########
PC甲子園２００６本選問題

問題０２ 出口調査 (１０点)あるデパートで買い物金額の出口調査を行いました。買い物金額のデータを入力とし、1人あたりの平均買い物金額を計算し、出力して終了するプログラムを作成してください。調査人数は、10000人以下とし、全員の買い物金額の合計は10億円を超えないものとします。

入力
1行目
2行目

調査人数n（整数）
1人目の買い物金額（整数）::
n+1行目 n人目の買い物金額（整数）出力
平均買い物金額（整数：小数点以下は切り捨て）

入力例

出力例

6
12300
5600
33800
0
26495
52000

21699

PC甲子園２００６本選問題

問題０３

短針と長針の出会うころ…（１０点）

原始スローライフ主義組織「アカルイダ」から、いたずらの予告状が届きました。アカルイダといえば、要人の顔面にパイを投げつけたりするいたずらで有名ですが、最近では火薬を用いてレセプション
会場にネズミ花火をまき散らすなど、より過激化してきました。
予告状は次の文面です。
---パソコン ヒトの時間を奪う。良くない。
時計の短い針と長い針 出会うころ、アカルイダ
スローライフ 偉大なり。

正義行う。

たどたどしくてよく解らないのですが、時計の短針と長針とが重なったころにいたずらを決行するという意味のようです。
このいたずらを警戒するため、時刻を入力として、短針と長針が近い場
合は“alert”、遠い場合は“safe”、それ以外の場合は“warning”と出力して終了するプログラムを作成してください。ただし、「近い」とは短針と長針の角度が0°以上30°未満の場合をいい、「遠い」とは90°以上180°以下の場合をいいます。なお、時刻は00:00以上11:59以下とします。

入力
1行目
2行目
3行目

判定する時刻の個数n（1以上10000以下の整数）
第1の時刻 hh:mm（整数：整数；半角コロン区切り）
第2の時刻 hh:mm（整数：整数；半角コロン区切り）：：
n+1行目 第nの時刻 hh:mm（整数：整数；半角コロン区切り）

出力
1行目
2行目

n行目

第1の時刻の判定結果
第2の時刻の判定結果：：
第nの時刻の判定結果

safe、warning、 または alertsafe、warning、 または alertsafe、warning、 または alert

入力例

出力例

4
02:15
06:01
11:55
10:40

alert
safe
alert
warning

PC甲子園２００６本選問題

問題０４

身長の度数分布（１０点）

健康診断で生徒の身長を計測しました。その身長を入力とし、度数分布を作成して出力し終了するプロ
グラムを作成してください。度数分布の階級は5㎝刻みの6つの階級とし、度数は人数を*（半角アスタリスク）で表示します。ただし、その階級の度数（人数）が0（ゼロ）の場合、階級の見出しのみを出力してください。生徒の数は40人以下とします。

入力
1行目
2行目
3行目

生徒の数n（整数）
1人目の身長（実数：小数第1位まで）2人目の身長（実数：小数第1位まで）：
n+1行目 n人目の身長（実数：小数第1位まで）

出力
1行目
2行目
3行目
4行目
5行目
6行目

見出し「1:」につづいて165.0cm未満の人数分の*（半角）見出し「2:」につづいて165.0cm以上～170.0cm未満の人数分の*（半角）見出し「3:」につづいて170.0cm以上～175.0cm未満の人数分の*（半角）見出し「4:」につづいて175.0cm以上～180.0cm未満の人数分の*（半角）見出し「5:」につづいて180.0cm以上～185.0cm未満の人数分の*（半角）見出し「6:」につづいて185.0cm以上の人数分の*（半角）

入力例１

出力例１

4
180.3
168.2
165.5
175.3

1:
2:**
3:
4:*
5:*
6:

入力例２

出力例２

21
179.4
171.5
156.6
173.0
169.4
181.2
172.4
170.0
163.6
165.9
173.5
168.2
162.5
172.0
175.1
172.3
167.5
175.9
186.2
168.0
178.6

1:***
2:*****
3:*******
4:****
5:*
6:*

PC甲子園２００６本選問題

問題０５

平方採中法（２０点）

古典的な乱数生成方法の一つである平方採中法のプログラムを作成します。平方採中法は、フォンノイ
マンによって1940年代半ばに提案された方法です。
平方採中法は、生成する乱数の桁数をnとしたとき、初期値sの2乗を計算し、その数値を2n桁の数値とみて、（下の例のように2乗した桁数が足りないときは、0を補います。）その中央にあるn個の数字を最初の乱数とします。次にこの乱数を2乗して、同じ様に、中央にあるn個の数字をとって、次の乱数とします。
例えば、123を初期値とすると

1232
1512
2282
5192
26932

=
=
=
=
=

00015129
00022801
00051984
00269361
07252249

→
→
→
→
→

0151
0228
0519
2693
2522

の様になります。
この方法を用いて、初期値s（10000未満の正の整数）を入力とし、n=4の場合の乱数を10個生成し出力して終了するプログラムを作成してください。

入力
初期値s（整数）

出力
1行目
2行目

生成した乱数（整数；半角）生成した乱数（整数；半角）：：
10行目 生成した乱数（整数；半角）

入力例１

出力例１

123

151
228
519
2693
2522
3604
9888
7725
6756
6435

入力例２

出力例２

567

3214
3297
8702
7248
5335
4622
3628
1623
6341
2082
PC甲子園２００６本選問題

問題０６

陸上競技大会（２０点）

陸上競技大会200Ｍの準決勝3組のレースが行われました。それぞれの組に8名（計24名）の選手が出場します。各組上位2位までと各組の3位以下の全選手の中から上位2名の計8名が決勝に進出します。選手
番号とタイムを入力とし、決勝進出者8名の番号とそのタイムを出力して終了するプログラムを作成して下さい。入力データの1件目から8件目までが1組目、9件目から16件目までが2組目、17件目から24件
目までが3組目のデータとします。タイムは、1/100まで計測し、同タイムの選手はいないものとし、棄権は無いものとします。

入力
1行目 選手の選手番号 タイム（整数 実数：半角空白区切り）：
24行目 選手の選手番号 タイム（整数 実数：半角空白区切り）

出力
1行目
2行目
3行目
4行目
5行目
6行目
7行目
8行目

1組目の1位の決勝進出者の選手番号 タイム（整数 実数：半角空白区切り）
1組目の2位の決勝進出者の選手番号 タイム（整数 実数：半角空白区切り）
2組目の1位の決勝進出者の選手番号 タイム（整数 実数：半角空白区切り）
2組目の2位の決勝進出者の選手番号 タイム（整数 実数：半角空白区切り）
3組目の1位の決勝進出者の選手番号 タイム（整数 実数：半角空白区切り）
3組目の2位の決勝進出者の選手番号 タイム（整数 実数：半角空白区切り）
各組で3位以下の選手の中でタイムが1位の選手番号 タイム（整数 実数：半角空白区切り）
各組で3位以下の選手の中でタイムが2位の選手番号 タイム（整数 実数：半角空白区切り）

入力例

出力例

18 25.46
16 26.23
3 23.00
10 24.79
5 22.88
11 23.87
19 23.90
1 25.1123 23.88
4 23.46
7 24.1212 22.91
13 21.99
14 22.86
21 23.12
9 24.09
17 22.51
22 23.49
6 23.0220 22.23
24 21.89
15 24.14
8 23.77
2 23.42

5 22.88
3 23.00
13 21.99
14 22.86
24 21.89
20 22.23
17 22.51
12 22.91

PC甲子園２００６本選問題

問題０７

ヘビ（３０点）ある世界には，文字だけでできた不思議なヘビが住んでいます。このヘビには現在A種とB種の2種類が確認されていますが、それ以外の種類がいる可能性もあります。
A種は，">'"の後に"="が1個以上並んだ後、"#"が来て、さらに前と同じ個数の"="が来た後、"~"（半角チルダ）で終わります。
B種は，">^"の後に "Q="が1個以上並んだ後、"~~"で終わります。
A種の例：>'====#====~>'==#==~

B種の例：>^Q=Q=Q=Q=~~>^Q=Q=~~

ヘビを文字列データとして受け取り、それがどんな種類であるかを判別して、A種の場合は「A」、B種の場合は「B」、それ以外の種類の場合は「NA」を出力して終了するプログラムを作成してください。1匹のヘビは、100文字以下の、空白を含まない1行の文字列として入力されるものとします。

入力
1行目
2行目
3行目

判別されるヘビの数n（1以上10000以下の整数）
1匹目のヘビ（半角文字列）
2匹目のヘビ（半角文字列）：：
n+1行目 n匹目のヘビ（半角文字列）

出力
1行目
2行目

n行目

1匹目のヘビの種類
2匹目のヘビの種類：：
n匹目のヘビの種類

A、BまたはNA（半角）A、BまたはNA（半角）A、BまたはNA（半角）

入力例

出力例

3
>'======#======~>^Q=Q=Q=Q=Q=Q=Q=Q=Q=~~>'===#====~

A
B
NA

PC甲子園２００６本選問題

問題０８

バス路線（３０点）

図1のようなバス路線があります。停留所は10箇所で、それぞれ0～9の番号がついています。バスは停
留所0では折り返しますが、反対側は循環路線になっており、図のように5→6→7→8→9→5の順で循環します。

このバス路線について、乗車する停留所と降車する停留所を入力とし、乗車から降車までに通る停留所の番号を出力して終了するプログラムを作成してください。
ただし、0～5の停留所では2方向のバスに乗車できますが、より短い経路で降車停留所に到着するバスに乗車することとします。例えば、停留所4から停留所2へ行く場合、左方向に進むバスに乗り「4→3→2」の経路を通ります。また、一度バスに乗車したら途中下車はしないものとします。同じ停
留所を乗車停留所、降車停留所に指定することはありません。

入力
乗車する停留所番号 降車する停留所番号（整数；半角空白区切り）

出力
通過する停留所番号の並び（整数；半角空白区切り）

入力例１

出力例１

2 4

2 3 4

入力例２

出力例２

4 2

4 3 2

入力例３

出力例３

1 9

1 2 3 4 5 6 7 8 9PC甲子園２００６本選問題

問題０９

ぐるぐる模様（４０点）「ぐるぐる模様」を表示するプログラムを作成することにしました。「ぐるぐる模様」は以下のようなものとします。
1辺の長さがnの場合、n行n列の文字列として表示する。
z 左下隅を基点とし，時計回りに回転する渦状の模様とする。
z 線のある部分は#（半角シャープ）、空白部分は“ ”（半角空白）で表現する。
z 線と線の間は空白を置く。
z nは1以上100以下の整数とする。
z整数nを入力とし，1辺の長さがnの「ぐるぐる模様」を出力して終了するプログラムを作成してください。

入力
辺の長さn（整数）

出力
ぐるぐる模様（半角文字列）

入力例１

出力例１

5

#####
#
#
# # #
# # #
# ###

入力例２

出力例２

6

######### ## ## # ## # ## ####

入力例３

出力例３

7

########## ### #
# # # #
# # # #
# ### #####
PC甲子園２００６本選問題

問題１０

素数の性質（４０点）

4で割ると3あまる素数n(11、19、23など）には、面白い性質があります。
1以上n未満の自然数（1,2,・・・,n-1）を2乗したものをnで割ったあまりを計算した結果を並べると、同じ数になるものがあるため、互いに異なった数の個数は、になります。
この様にして得られた数の集合には、特別な性質があります。得られた数の集合から、互いに異なる2つaとbを選んでその差を計算します。差が負になったときは、その差にnを足します。さらに結果がより大きいときは、その差をnから引きます。
例えば、n=11のとき1と9の差は、1-9=-8 → -8+n=-8+11=3になります。9と1の差も9-1=8→ n-8=11-8=3で、同じ値3になります。この差は、円周上に0,1,・・・,n-1を書いて、二つの数字の間の短い方の円弧を考えるとわかりやすくなります。（右図参照）
こうして得られた数の「差」は、あり、同じ回数出現します。

のいずれかで【例】 n=11の時は、以下のようになります。
1. 2乗とnによる剰余の計算
1からn-1までの数を2乗したものをnで割った余りを計算します。
=
1 →
1
12

22
32
42
52
62
72
82
92
102

=
4
=
9
= 16
= 25
= 36
= 49
= 64
= 81
= 100

→
→
→
→
→
→
→
→
→

4
9
5
3
3
5
9
4
1

2. a,bの「差」の計算(1) 1 で得られた1,3,4,5,9 について異なる数同士の差を計算します。
(2) 計算結果が負の場合、n=11 を加算します。
(3) さらに、計算結果が=5 より大きい場合 n=11 から減算します。
3. 出現回数を求める
計算結果1,2,3,4,5の出現回数をそれぞれ数え上げます。

これらの計算結果から1,2,3,4,5の出現回数が4回であることがわかります。この性質は4で割ると3あまる素数特有の性質であり4で割ると1あまる素数ではこのようなことはおきません。このことを確認するため、10000以下の奇数nを入力とし、例題にあるような計算（nで割ったあまりの2乗の差の頻度を求める）を実行し、その出現回数を出力して終了するプログラムを作成してください。

入力
n（整数）

出力
剰余の平方の差が1である（a,b）の出現個数（整数）
剰余の平方の差が2である（a,b）の出現個数（整数）：：
剰余の平方の差がである（a,b）の出現個数（整数）

入力例１

出力例１

11

4
4
4
4
4

入力例２

出力例２

15

2
2
4
2
4
4
2
PC甲子園２００６本選問題

問題１１

織女と牽牛（５０点）

織女は天帝の子供でしたが、父の言いつけであけてもくれても機を織っていました。
織女のおる雲錦という見事な布で仕立てた服を着るのが天帝の楽しみでした。雲錦は寿命が短くすぐに劣化してしまいますが、働き者の織女が毎日織ってくれるので、問題はありませんでした。織女は、父の言いつけを守り、毎日毎日雲錦を織り続けていたので、ボーイフレンドはいませんでした。かわい
そうに思った父は、天の川の向こう岸に住む牽牛という働き者を紹介してやり、嫁入りさせました。
すると、織女は、結婚の楽しさに夢中になって、機織りなどそっちのけで、牽牛と遊び呆けています。天帝のお気に入りの雲錦の服も新しく仕立てられないためボロボロになってしまいました。
これには、父も怒って織女を宮殿に連れ戻したいと思いました。しかし人間である牽牛の前にボロボロの服で姿を現すわけにはいきません。遊び呆けている二人を3角形の壁で遮断し自分以外の全てのものが行き来できなくすることを考えました。そして、牽牛に見つからずに、織女に会って、まじめに機を織るか、さもなければ強制的に連れ帰ると宣言するというのです。

天帝はこの作戦遂行のために3角形の壁生成装置の開発を開発部署に命じました。3点を与えてそこに壁を作るという仕様で発注したつもりでしたが、開発部署では何を間違えたのか、ランダムに（無作為に）に3角形の壁を生成し、その3点を報告するシステムを作ってしまいました。発注者として、天帝は作り直しを命じたいのですが、服がますますボロボロになったので、最小限の手直しで手を打つことにしました。ランダムに壁ができたのではたまったもんじゃないので、作ろうとする3角形が決まった段階で、3点を報告し、それで満足するものならば（すなわち遮断ができていれば）天帝がOKボタンを押して壁の作成を指示するという仕様にしました。遮断できていなければ（遮断不全ならば）NGボタンを押し、やり直しとなります。織女と牽牛は時々刻々場所を変えます。壁生成装置からは無作為の3点がどんどん出力されてきます。
天帝は与えられた状況下で、壁の作成を指示すべきか否かを判定する必要に迫られました。そこで、天帝にかわり、3角形の3頂点の位置(xp1,yp1),(xp2,yp2),(xp3,yp3)、牽牛の位置(xk,yk)、および織女の位置(xs,ys)、を入力とし、三角形が牽牛と織女を遮断しているか否かを判定し、遮断できている場
合はOK、遮断できていない場合にはNGを出力し終了するプログラムを作成してください。ただし、遮断しているとは、牽牛と織女のいずれかが三角形の内側にあり、他方が外側にある場合を言います。牽牛と織女は三角形の頂点もしくは辺の上にはいないものとします。

入力
1行目
2行目

判別したい情報の個数n（整数）第1の位置情報 xp1 yp1 xp2 yp2 xp3 yp3 xk yk xs ys（整数；半角空白区切り）
三角形の3頂点の位置(xp1,yp1),(xp2,yp2),(xp3,yp3)
牽牛の位置(xk,yk)
織女の位置(xs,ys)
3行目 第2の位置情報 xp1 yp1 xp2 yp2 xp3 yp3 xk yk xs ys（整数；半角空白区切り）::
n+1行目 第nの位置情報 xp1 yp1 xp2 yp2 xp3 yp3 xk yk xs ys（整数；半角空白区切り）

出力
1行目
2行目

n行目

第1の位置情報の判定結果OKまたはNG（半角英字）
第2の位置情報の判定結果OKまたはNG（半角英字）::
第nの位置情報の判定結果OKまたはNG（半角英字）

入力例

出力例

5
2 5 9 2 8 9 2 11 6 5
2 5 9 2 8 9 2 11 12 6
2 5 9 2 8 9 2 11 11 9
14 1 25 7 17 12 17 9 20 5
14 1 25 7 17 12 22 13 20 5

OK
NG
NG
NG
OK

PC甲子園２００６本選問題

問題１２

パケット転送（５０点）

インターネットでは、データはパケットに分割され、パケットごとにルータと呼ばれる中継機器を介して宛先に転送されます。各ルータはパケットに記載された宛先から次に転送すべきルータを判断します。さらに、無限にルータ間を転送され続けることを防ぐため、パケットにはTTL（Time To Live）という値が付加されています。ルータは受け取ったパケットのTTLを1減算し、その結果が0ならそのパケットを破棄し、それ以外なら次のルータに転送します。
そこで、ネットワークの設計を手助けするプログラムを作ることになりました。ネットワークの接続
情報と送信パケットの情報を入力として、各パケットが宛先ルータに到着するまでに経由するルータの数のうち最小の値を表示して終了するプログラムを作成してください。
ネットワークは図のように複数のルータとそれらを結ぶケーブルで構成されています。ただし、各接続（ケーブル）は単方向であることに注意してください。各ルータが直接つながっているルータの番号の配列がネットワークの接続の情報として与えられます。ルータの数をnとすれば、nは100以下であり、各ルータは1からnまでの整数で識別されます。送信元から宛先ルータまでの経路が複数ある場合
は、経由するルータの数が少ない方の値を出力してください。また、パケットが宛先に到達しない場合
はNAと出力してください。例えば、以下の図のようなネットワークで、送信元ルータが6、宛先ルータ
が5の場合を考えます。最短経路は6→1→5であり経由するルータは3個です。この場合、TTLはルータ
6、1でそれぞれ減算されるので、送信時のTTLが3以上であればパケットは到達できます。宛先ルータではTTLを減算する必要はありません。また、送信元と宛先が同じルータになるようなパケットは無いものとします。

入力
1行目
2行目

ルータの総数n（整数）1番目のルータの接続情報r1 k1 t11 t22 ...（整数；半角空白区切り）

3行目

r1：1番目のルータ番号
k1：1番目のルータと直接接続しているルータの個数t11 t22 ...：1番目のルータから送信できるルータの番号(k1個)
2番目のルータの接続情報 r2 k2 t21 t22 ...（整数；半角空白区切り）：：
n+1行目 n番目のルータの接続情報 rn kn tn1 tn2 ...（整数；半角空白区切り）
n+2行目
n+3行目

パケットの個数p（整数）1番目のパケットの情報 s1 d1 v1（整数；半角空白区切り）
s1：送信元ルータの番号
d1：宛先ルータの番号
v1：TTLの値
n+4行目 2番目のパケットの情報 s2 d2 v2（整数；半角空白区切り）：：
n+p+2行目 p番目のパケットの情報 sp dp vp（整数；半角空白区切り）

出力
各パケットが経由するルータの個数（整数）またはNA（半角文字列）

入力例

出力例

7
1 4 2 5 4 3
2 1 5
3 1 6
4 1 7
5 2 7 6
6 1 1
7 0
6
1 2 2
1 5 3
1 2 1
5 1 3
6 3 3
1 7 4

2
2
NA
3
3
3

PC甲子園２００６本選問題

問題１３

カード（５０点）

正の整数が書かれた一組のカードがあります。カードを積んで山をいくつか作り、それらを横一列に並べます。その中から隣り合った2つのカードの山を選び、右側の山の上に左側の山をそのまま重ねます。この操作をカードの山が一つになるまで繰り返していきます。
2つのカードの山を重ねる時にそれらの一番上と下のカードに書かれた数をすべて掛け合わせます。
こうして得られた数をカードの重ね合わせのコストと呼ぶことにします。カードの山を一つにするためのコストはすべての重ね合わせのコストを足し合わせたものとします。
どのような順番でカードの山を重ねるかでコストは変わります。たとえば、3つのカードの山がある場合を考えます。それらの一番上と下のカードに書かれた数が，左側の山から順にそれぞれ3 と5, 2と8,5 と4 だったとします。このとき，はじめに左と真ん中の山を重ねたときのコストは、
3×5×2×8=240です。この重ね合わせによって、一番上のカードが3で一番下のカードが8である山ができます。
この山を右の山の上に重ねると、そのコストは3×8×5×4=480になります。したがって、この順番でカードの山を一つにまとめたときのコストは240+480=720です。（図1）
一方、はじめに真ん中と右の山を重ねてから最後に左の山を重ねることにすると、そのときのコストは2×8×5×4+3×5×2×4=440になります。したがって，後の場合のように重ねた方がコストが小さくなります。（図2）

カードの山の個数とそれぞれの山の一番上と下のカードに書かれた数を入力とし、カードの山を一つにまとめるのに必要な最小のコストを出力して終了するプログラムを作成してください。ただし、山の個数は100個以下とし、入力されるデータはどのような順番でコストを計算しても231-1を超えることはありません。

入力
1行目
2行目

カードの山の個数n(100以下の正の整数)
左から1番目の山の情報 a b（整数；半角空白区切り）
a 山の1番上のカードに書かれた数
b 山の1番下のカードに書かれた数
3行目 左から2番目の山の情報a b（整数；半角空白区切り）：：
n+1行目 左からn番目の山の情報a b（整数；半角空白区切り）

出力
カードの山を一つにまとめるのに必要な最小のコスト

入力例

出力例

3
3 5
2 8
5 4

440

PC甲子園２００６本選問題

問題１４

ルパン四世（５０点）

怪盗「ルパン四世」は会津藩士を末裔とする美女「富士峰子」より、会津若松市に会津藩が残した軍資金が眠っていることを聞かされる。ルパンの長年の仲間である「石川越ェ門」の報告によれば、軍資金は千両箱に収められいくつかの蔵に保管されている。蔵に見張りはいないが厳重に施錠されている。しかし、越ェ門は彼が父から伝授された秘伝「鋼鉄斬り」の技を繰り出せば瞬時に蔵を破れるという。
残った問題は千両箱の運搬だ。体力のないルパンと越ェ門は千両箱を一つも持てない。そこで、頼りになる男「無限大介」に運搬を頼んだ。大介は米俵を使った訓練を重ね、超人的な運搬能力を身につけた。
すべての千両箱を運び出すために、ルパンは以下のような計画を立案した。
まず、ルパンの運転で最初の蔵へ行き、越ェ門と大介を降ろす。

越ェ門が蔵を破る
大介がすべての千両箱を運び出す
z その千両箱を持ったままルパンが決めた次の蔵へ向かうzz

これを繰り返し、最後の蔵まで破り千両箱を運び出す。その間にルパンはヘリコプターを準備し最後の蔵で二人と千両箱を運び上げ脱出する。大介はどんなに重いものも運搬できるが、荷物の重さに応じて移動速度は遅くなる。ルパンは、このことを考慮して蔵を破る順番を決めなければならない。
ルパンに代わって、最初の蔵を破ってから最後の蔵に辿りつくまでの移動時間が最小となるような蔵を破る順番を出力して終了するプログ
ラムを作成してください。ただし、蔵はすべて鶴ヶ城からまっすぐ北に走る通りに面している。蔵の数は高々15個であり、城からの距離は高々10000メートル以下である。
z 千両箱の重さはいずれもひとつ20キログラムである。それぞれの蔵に収められている千両箱の個数は10000個以下である。
z 蔵から蔵への移動は、通りに沿って地下に設置されている地下道を使う。
z 大介はwキログラムの荷物を運ぶのに、分速2,000／(70+w)メートルで移動する。
z 富士峰子は計画を妨害する恐れがあるので事前に睡眠薬を飲ませて眠らせる。このほかの妨害についても、遺漏なく対処する。
z

入力データは、それぞれの蔵について蔵の番号（100以下の整数）と城からの距離（メートル）とその蔵に保管されている千両箱の個数が与
えられる。

入力
1行目
2行目
3行目

蔵の個数n（整数）第1の蔵の情報（蔵の番号 城からの距離 千両箱の数（整数；半角空白区切り））
第2の蔵の情報（蔵の番号 城からの距離 千両箱の数（整数；半角空白区切り））：：
n+1行目 第nの蔵の情報（蔵の番号 城からの距離 千両箱の数（整数；半角空白区切り））

出力
蔵を破る順番（整数；半角空白区切り）

入力例１

出力例１

2
1 100 1
2 200 2

1 2

入力例２

出力例２

3
11 100 1
13 200 20
12 300 3

11 12 13

入力例３

出力例３

5
13 199 1
51 1000 1
37 350 10
27 300 2
99 200 1000

51 37 27 13 99

PC甲子園２００６本選問題

問題１５

福縞軒（５０点）「福縞軒」は行列のできる人気のラーメン屋です。でも最近、お客さんの間から「待ち時間が長いのに、店に入ったら空席があるのは許せない」という声が聞こえるようになってきました。どうしてそん
な不満が出るのか調べたいのですが、お店が開いているあいだは忙しくて、実際の行列の様子を調べることができません。しかし、長年の経験からお客さんが来る間隔や人数は分かっているので、それをもとに待ち時間の分析をすることにしました。
店内にはカウンターに向かって17の席があります。開店時間は正午で、お客さんは次のようにやってきます。
0番から99番までの100組のグループが来ます。
i番目のグループは正午から 5i 分後にお店に到着します。
z i番目のグループの人数は i%5 が 1 のとき5人、それ以外のときは2人です。
（x%yはxをyで割ったときの余りを表わします。）
z i番目のグループは、席に着くと 17(i%2)+3(i%3)+19 分間で食事を済ませます。
zz

最初の10グループの到着時刻、人数、食事時間は次のようになります。
グループ番号到着時刻（分後）
人数（人）
食事時間（分）

0
0
2
19

1
5
5
39

2
10
2
25

3
15
2
36

4
20
2
22

5
25
2
42

6
30
5
19

7
35
2
39

8
40
2
25

9
45
2
36

また、お客さんを席に案内するときには、次のようにしています。
zz

席には0から16までの番号が付いています。
x人のグループは連続してx個あいている席があった時だけ着席できます。

また、座れる場所が複数あった場合は、席の番号が最も小さくなるところに座ります。例えば、0、1、
2、4、5番の席だけが空いていた場合、5人のグループは着席できません。2人のグループであれば0、1番に着席します。
一度着席したら、席を移動してもらうことはしません。
z お客さんは1分単位で出入りします。各時刻には次の順序でお客さんを案内します。
1. 前のグループの離席と同時に次のグループの着席が可能となります。
2. お客さんを着席させる際には、行列の先頭にいるグループから順に、できる限り多くのグループを同じ時刻に着席させます。行列の順序を追い越すことはしません。つまり、先頭のグループが着席できなければ、行列内の他のグループが着席できたとしても、着席させません。
3. その時刻に到着したグループは、行列が残っている場合は行列の最後尾に並びます。行列が無く、着席できる場合は着席し、できない場合は並んで待ちます。例として最初の10グループが到着するまでの様子を示すと以下のようになります。各行の3つの欄は、左から時
刻、座席の様子、行列の様子を示しています。座席は「_」が空席で、番号はその席にその番号のグループが座っていることを示しています。
z

時刻:
0:
5:
10:
15:
18:
19:
20:
25:
30:
34:
35:
40:
41:
42:
43:
44:
45:

座席
00_______________:
0011111__________:
001111122________:
00111112233______:
00111112233______:__111112233______:
44111112233______:
4411111223355____:
4411111223355____:
4411111223355____:
4411111__3355____:
4411111__3355____:
4411111__3355____:__11111__3355____:__11111__3355____:
6666677883355____:
666667788335599__:

行列

66666
66666
6666677
666667788
666667788
666667788
666667788

グループ6が到着
グループ7が到着
グループ8が到着

グループ6、7、8が着席
グループ9が到着、着席

例えば、時刻40では8番目のグループが到着しますが、着席できないので行列に加わります。4番目のグ
ループは時刻41まで食事をします。時刻42では、4番目のグループの席が空きますが、連続した席数が足りないので6番目のグループはまだ着席できません。1番目のグループは時刻43まで食事をします。時
刻44で1番目のグループの席が空くので、6番目のグループが着席し、同時に7番目、8番目のグループも着席します。9番目のグループは時刻45で到着し、席が空いているのでそのまま着席します。
これらの情報を基にして、0以上99以下の整数nを入力として、n番目グループのお客さんが待つ時間（分単位）を出力して終了するプログラムを作成してください。

入力
n(0以上99以下の整数)

出力
n番目のお客の分単位の待ち時間（0以上の整数）

入力例１

出力例１

5

0

入力例２

出力例２

6

14

入力例３

出力例３

7

9

入力例４

出力例４

8

4
PC甲子園２００６本選問題