全国高等学校パソコンコンクール
プログラミング部門 本選問題
平成２６年１１月８日(土)午後１時４５分～午後５時４５分

全国高等学校パソコンコンクール実行委員会

1 / 21

問題１

有益氏のオーディオルーム

（６点）

数学者である有益氏の趣味は音楽鑑賞で、家に念願のオーディオルームを作りました。完成したオーディオルームで、友人を招いてお披露目会を開きたいと考えています。全員にできるだけ良い音で聴いてもらいたいので、部屋の中の何か所かで音を計測し、友人たちの位置での音の質を計算するつもりです。
しかし、そのために必要な計測点を選択するのは面倒です。
計測点は、下の図の円弧と線分の交点である 1 番から 35 番までの点から選択します。１つの線分上にある点は、オーディオシステムからの距離が 100ｃｍから 500ｃｍまで 100ｃｍずつ離れて並んでいます。
１つの円弧状にある点は、もっとも右のもの（1 番から 5 番までの点）から反時計回りに、0°から 180°の範囲で 30°度刻みに並んでいます。
2025243027353433322613172228141823291519211612119761318102345オーディオシステム

このような円弧と線分に囲まれた領域内のどこかに友人が居ることになるので、友人の居る位置によって必要な計測点を選択します。友人の位置は、円弧に沿って反時計回りに測った角度とオーディオシス
テムからの距離で与えられます。必要な計測点は以下のように１点か、２点か、４点が選ばれます。
友人の位置

友人がちょうど計測点の位置にいれば、その１点を選びます。この図の例の場合、選ばれるのは 23番の点です。

友人の位置

友人が円弧（または線分）の上にちょうど乗っていれば、その円弧（または線分）上にある、友人に最も近い２点を選びます。この図の例の場合、選ばれるのは 18 番と 23 番の点です。

友人の位置

友人が円弧と線分によって囲まれた区画の内側（円弧や線分の上ではない）にいれば、区画を作っている４点を選びます。この図の例の場合、選ばれるのは17、18、22、23 番の点です。

有益氏を助けるために、必要な計測点の番号を求めるプログラムを作成してください。

2 / 21

入力
入力は以下の形式で与えられる。
Nr1 t1
r2 t2
:
rN tN
１行目に友人の数N(1≦N≦50)が与えられる。続くN行に、友人の位置が与えられる。友人の位置r i (100≦r i ≦500)はオーディオシステムからの距離を表す整数、t i (0≦t i ≦180)は円弧に沿って反時計回りに測った角度を表す整数である。

出力
各友人の位置について、計測点の番号を昇順で１行に出力する。

入出力例
入力例
4300 120300 105
250 105250 90

出力例2318 23
17 18 22 23
17 18

3 / 21

問題２対称３進数（６点）

1グラム、3グラム、9グラム、27グラムのおもりが１つずつあれば、天びんを使って1グラムから40グラムまで1グラム刻みで量れることが知られています。たとえば、天びんの一方の皿に重さを量りたいものと3グラムのおもりを載せ、もう一方の皿に27グラムと1グラムのおもりを載せて釣り合えば、量りたいものの重さは27-3+1=25グラムだとわかります。 さらに、1(=30)グラム、31グラム、…、3n-1グラム、3nグラムまでのおもりが１つずつあれば、天びんを使って(3n+1-1)/2グラムまで量れることが知られています。また、天びんが釣り合うようなおもりの置き方は一通りしかないことも知られています。
量りたいものとおもりを天びんに置いて、釣り合うようなおもりの置き方を文字列で表すことができま、す。3iグラムのおもりを量りたいものと同じ皿に載せたときは「-」、もう一方の皿に載せたときは「+」どちらにも載せなかったときは「0」を文字列の右端からi番目に書きます（右端を０番目と数えます）。
たとえば、先ほどの25グラムの例は +0-+ と表わせます。
それでは、量りたいものの重さが与えられたとき、天びんが釣り合うようなおもりの置き方を表す文字列を出力するプログラムを作成してください。ただし、３のべき乗グラムのおもりは、どのような重さのものでも必ず１つあるものとします。
（補足： 対称３進数について）
量りたいものの重さがwのとき、おもりの置き方を表す文字列はwの対称３進数になっています。対称３進数とは、３のべき乗の数で位取りを行い、各位に数 1、0、-1 を表す文字を書くことで表した数のことです。上の文字列では、文字「+」、「0」、「-」がそれぞれ数 1、0、-1 に対応します。たとえば、25グラムのものを量るときのおもりの置き方が +0-+ である対称３進数が表す数は、1×33＋0×32－1×31＋1×30 = 25となります。

入力
入力は以下の形式で与えられる。
ww(1≦w≦100000)は量りたいものの重さを表す整数である。

出力
おもりの置き方を表す文字列を出力する。ただし文字列の左端を 0 にしてはならない。

入出力例
入力例１25

出力例１+0-+

入力例２2

出力例２+-

入力例３5

出力例３+--

4 / 21

問題３ ニッシン館マラソン部（６点）

アイヅ市立ニッシン館は、文武両道を掲げる歴史ある学校です。ニッシン館マラソン部は熱血指導で有名であり、決められた練習時間の間、周回コースをひたすら走るという鬼の特訓を行います。このとき、脱水症状で倒れる部員がいないように、部員の実力に合わせて飲み物を提供する給水所を設けています。
各部員が１単位時間あたりに走れる距離(ペース)は部員ごとに決まっており、全員が１単位時間ごとに必ず給水できるように給水所を設けたうえで特訓を行います。部員は 1 単位時間で着いた給水所で必ず中身の入った容器を取り、そのまま走り続けます。さらに、次の１単位時間で着いた給水所で空の容器を置き、中身の入った容器を取って走り続けるということを繰り返します。また、空の容器は、置いてから 1 単位時間の時点で飲料が補充され、その瞬間から誰にでも提供できるようになります。
部員は全員同じ地点から、容器を持たずに出発します。決められた練習時間まで走ると練習を終えます(このときも給水が必要です)。複数の部員が同時に同じ給水所に到着する場合もあるので、一か所の給水所で同時に複数の容器が必要になることもあります。
鬼の特訓を安全に行うために、最低いくつの給水容器が必要になるか求めるプログラムを作成してください。

入力
入力は以下の形式で与えられる。
N R T
p1p2:pN
１行目に部員の数N(1≦N≦100)、周回コースの長さR(1≦R≦1000)、決められた練習時間T(1≦T≦1000)が与えられる。続くN行に、部員iのペースp i (1≦p i ≦1000)が与えられる。

出力最低いくつの給水容器が必要になるかを１行に出力する。

入出力例
入力例１1 10 201

出力例１11

入力例２2 5 1212出力例２85 / 21

問題４

デッドロックを検出せよ（８点）

コンピュータにおける「データベース」とは、情報を管理するための入れ物で、「データベースマネジ
メントシステム(DBMS)」とは、その管理をする仕組みです。複数のユーザが利用するデータベースでは、DBMS は慎重に構築する必要があります。
例えば、倉庫から商品を１つ取り出した人が、データベースに対して以下の処理を行うとしましょう。
(1) 商品の個数 N をデータベースから読む。
(2) 新たな商品の個数 N-1 をデータベースに書き込む。
ユーザ１が(1)を終えて(2)を始める前に、別のユーザ２が倉庫から商品を取り出して(1)を行ったとします。ユーザ２もユーザ１と同じ個数を読むので、２人が(2)を終えたときには商品は２個減るのにデータベース上では１個しか減らないというおかしな結果になります。このような問題を防ぐために、DBMS は特定のデータを操作中のユーザに、そのデータを「ロック」する権利を与えます。ロックされていれば、他のユーザはその値を操作できなくなるので、おかしな結果を返すことはなくなります。
これで安全に操作できることは保証されますが、今度は別の問題が起こります。例えば、ユーザ１とユーザ２が以下のような順番でデータＡとＢをロックしようとしたらどうなるでしょうか？
① ユーザ１がデータＡのロックを試みる → 成功（データＡがロック中になる）② ユーザ２がデータＢのロックを試みる → 成功（データＢがロック中になる）③ ユーザ１がデータＢのロックを試みる → データＢがロック中なのでユーザ１は待つ④ ユーザ２がデータＡのロックを試みる → データＡがロック中なのでユーザ２は待つ④を実行した時点では、ユーザ１がＡ、ユーザ２がＢをロックしているので、③④は永久に成功しません。これを「デッドロック」と呼びます。DBMS はこれを検出しなければなりません。

ある時点でデッドロックが起きているかどうかは、その時点でのすべてのユーザとデータの依存関係を書き、循環ができているかどうかで判断できます。依存関係は，ユーザがデータをロック済みの場合はデータからユーザの向きに矢印を、ユーザがデータのロックを試行していて待ち状態になっている場合はユーザからデータの向きに矢印を書くことで表します。

ユーザ１

データＡ

ユーザ２

データＢ

ロック済み:
ロック試行(待ち状態):

上の①から④の例であれば、④を実行した時点での依存関係は右上のような図になります。このとき、矢印の方向に進むと、ユーザ１→データＢ→ユーザ２→データＡ→ユーザ１という循環ができているた
め、デッドロックが起きていることがわかります。DBMS の苦労を体験するため、あなたにここでやってもらいたいのは、このようなデッドロックを検出するプログラムを作成することです。

6 / 21

入力
入力は以下の形式で与えられる。
Nrel 1
rel 2
:
rel N
１行目にユーザとデータの依存関係の数N(1≦N≦1000)が与えられる。続くN行に、ユーザとデータの依存関係rel i が与えられる。依存関係はlockとwaitの２種類あり、各rel i は以下のいずれかの形式で与えられる。
u lock dまたはu wait du lock d は、ユーザu(1≦u≦100)が、データd(1≦d≦100)をロック済みであることを表す。
u wait d は、ユーザu(1≦u≦100)が、データd(1≦d≦100)のロックを試行していて待ち状態であることを表す。
ただし、入力は以下の条件を満たしていると仮定してよい。


ロックされていないデータに対して、ユーザが待ち状態ではない。
二人以上のユーザにロックされているデータはない。



ユーザ自身がロックしているデータに対して、待ち状態ではない。
同じ依存関係は与えられない。

出力
デッドロックが発生しているなら 1、発生していないなら 0 を１行に出力する。

入出力例
入力例１41 lock 12 lock 21 wait 22 wait 1

出力例１1

入力例２43 lock 32 wait 33 lock 42 wait 4

出力例２07 / 21

問題５

新薬開発

（９点）

英世博士は日々研究を行い、新しい薬を開発しようとしています。新薬を開発するためには、色々な物質を組み合わせて薬を作り試験を行い、良い薬を見つけなければなりません。様々な組み合わせを試していくうちに、英世博士は物質の組み合わせが樹形図で表せることを突き止めました。
右の図は、薬の調合を表す樹形図の例です。図の中で丸く囲まれたものを物質ノード、三角で囲まれたものを選択ノードと呼びます。物質ノードは物質を表します。選択ノードは、物質の選択を表すもので、それ自体は物質を表しません。
選択ノードには or 型（∨が付いたもの）と alt 型（⇔が付いたもの）の２種類があります。また？が付いたノードは、それがオプションであることを表します。ただし、選択ノードの子ノード（下向きの枝の先にあるノード）がオプションになることはありません。樹形図に現れる異なる物質ノードは、それぞれ別の物質を表すものとします。
薬の調合を行うときは、樹形図の一番上のノードからはじめて、順々にノードをたどっていきながら以下のようにしてノードを選んでいきます。
たどり着いたノードがオプションでない物質ノードなら、それを必ず選ぶ。
オプションの物質ノードなら、それを選ぶかどうかは任意。

or 型の選択ノードなら、その子から少なくとも一つを選ぶ。ただし、その選択ノードがオプションなら、子を一つも選ばなくてもよい。

alt 型の選択ノードなら、その子から一つだけを選ぶ。ただし、その選択ノードがオプションなら、子を選ばなくてもよい。

あるノードが選ばれたときだけ、そのノードから下に向かう枝をそれぞれたどっていきます。選ばれなければ、それらをたどることはありません。
あなたは英世博士から、薬の物質の組み合わせを表す樹形図を受け取り、組み合わせの数が全部で何通りあるか求めるよう指示されました。樹形図が与えられたとき、組み合わせの総数を出力するプログラ
ムを作成してください。

入力
入力は以下の形式で与えられる。
N
node 1
node 2:
node N
s1 t1
s2 t2:
s N-1 t N-1

8 / 21

１行目にノードの数N(1≦N≦1000)が与えられる。続くN行に、i番目のノードの情報node i が与えられる。
１番目のノードを樹形図の一番上のノードとする。続くN-1行にs i 番目のノードからその子であるt i 番目のノード(1≦s i ≠t i ≦N)へ向かう枝が与えられる。t 1 からt N-1 までには、2からNまでの数が一度だけ現れる。
ノードの情報は以下の形式である。


E
E?

オプションでない物質ノード。
オプションである物質ノード。

typetype?

オプションでない選択ノード。typeはAかRのいずれかで、Aはalt型、Rはor型を表す。
オプションである選択ノード。typeの形式は同上。

入力から得られる樹形図は、以下の条件を満たす。
 選択ノードは２つ以上の子ノードを持つ。
 選択ノードの子ノードはオプションでない。
 樹形図の一番上のノードはオプションでない。
どのノードについても、子ノードの数は10を超えない。

出力与えられた樹形図から得られるすべての組み合わせの総数を１行に出力する。ただし、出力すべき値は非常に大きくなりうるので、代わりに 1,000,000,007 で割った余りを出力する。

入出力例
入力例１12

出力例１11A
E
E
E
R?
E?
E?
E
E
E
E?
E
1 2
1 3
1 42 54 64 75 85 97 107 1111 129 / 21

入力例２10E

出力例２24R?
ER
EEA
EEE
1 2
1 72 32 44 54 67 87 97 1010 / 21

問題６枠

（１２点）

画像の中から有益な情報を抽出する画像認識はコンピュータサイエンスの中でも重要な研究テーマのひとつです。デジタルカメラ、運転支援システム、防犯システムなどに幅広く応用されています。
このような研究のおかげで、私たちは画像解析を行うための多くのソフトウェアやプログラム集を使い様々な処理を行うことができます。一方、自力でプログラムを書いて解析することで、その仕組みを知り、楽しい時間を過ごすことができます。ここでは、一風変わった画像認識をしてみましょう。
画像として次のような各ピクセルが整数の値を持つ N×N のピクセルが入力として与えられます。この
画像の中から、線の太さが１ピクセルの長方形の枠（わく）を１つ抽出します。

枠が覆うピクセルの値の和が最大となるような枠を抽出して、その和を報告するプログラムを作成して下さい。ただし、下の図のように、縦、横のピクセル数が１つや２つの場合も枠とみなすものとします。

入力
入力は以下の形式で与えられる。
N
p 1,1 p 1,2 … p 1,Np 2,1 p 2,2 … p 2,N:
p N,1 p N,2 … p N,N
１行目に縦と横のピクセル数N(1≦N≦300)が与えられる。続くN行に、i行j列目のピクセルの値を表す
整数p i,j (-1000≦p i,j ≦1000)が与えられる。

時間制限
入力に対して、実行時間が１秒を超えてはならない。

出力
ピクセル値の和が最大となるような枠の、ピクセル値の和を１行に出力する。

11 / 21

入出力例
入力例１52 0 0 2 00 1 0 2 00 0 0 -1 00 4 0 3 0-1 0 0 1 0

出力例１12

入力例２30 0 00 -1 00 0 0

出力例２012 / 21

問題７

かぐや

（１２点）

いよいよ今月末に「はやぶさ２」が打ち上げられます。４年前に「はやぶさ」が帰ってきたときは、日本中が盛り上がったのを覚えている人も多いと思います。７年前には、「かぐや」が打ち上げられ、月の周りを回りながらたくさんの鮮明な画像を地球に送ってくれました。
月の軌道
右の図は、地球を原点とした空間座標（z軸は紙面から垂直に下から上に向いているものとします）に、月の軌道といくつかの月の位置、月の周りを回るかぐやの軌道を描いたものです。月の軌道は、x軸とy軸を通る平面上にある、原点を中心とする円とします。月の周りを回るかぐやの軌道は、x軸とz軸を通る平面に平行な平面上にある円とし、その中心は月の中心と一致します。月は、その軌道にyCA
地球x沿って描かれた矢印の方向に回っているものとします。
B
右の図で、月の位置はＡ，Ｂ，Ｃの３つが描かれています。月を横切る直線がかぐやの軌道です。かぐやは月の周りを回っているので軌道は円ですが、z軸の正の方向から見ているので、図のx軸に平行な直線に見えます（月の位置が変わっても、つねにx軸に平行であることに注意してください）。かぐやは、その軌道上に描かれた矢印の方向に回っているものとします。
かぐやが地球から見て月の裏側に隠れてしまうと、地球と直接通信ができなくなります。かぐやの管制を担当するあなたは、かぐやが月の裏側に隠れる時間が、与えられた時間の中でどれだけになるかをプログラムで求めようとしています。
月の地球に対する位置と分単位での時間tが与えられたとき、その位置から始めてt分後までの間に、かぐやが月の裏側に隠れる時間を求めるプログラムを作成してください。ただし、地球とかぐやは点、月は半径1800kmの球と考えます。月は半径380000kmの軌道を2500000秒で一周し、かぐやは月の表面から高度100kmの円上を２時間で一周するものとします。かぐやの最初の位置は、かぐやの軌道がz座標で最大の値をとる位置とします。

入力
入力は以下の形式で与えられる。
m tm(0≦m＜360)は月の位置を上の図のx軸の正の部分からy軸の正の部分に向かって反時計回りに測った角度を整数で表したものである。t(1≦t≦10000)は分で測った時間を表す整数である。

出力
はじめの位置から t 分経過するまでの間に、かぐやが月の裏側に隠れる時間（分）を実数で出力する。
ただし、誤差がプラスマイナス 1.0 分を超えてはならない。この条件を満たせば小数点以下何桁表示してもよい。

入出力例
入力例１90 10

出力例１0.013 / 21

入力例２0 120

出力例２47.73

14 / 21

問題８

ネットカフェ

（１２点）

あなたはネットカフェを経営しています。今日あなたは、顧客に指摘され続けている問題を解決しようと取り組んでいます。その問題とは、店舗の本棚の単行本が巻数順に並んでおらず、目的の単行本を探しだすのが面倒だという苦情です。
あなたの店舗で一番巻数の多い単行本は「名探偵 赤ベコ」（通称「赤ベコ」）です。あまりに長編なので、特別な本棚を「赤ベコ」のために用意しました。
単行本の各巻の重さと厚さは様々で、本棚の各段の幅と、各段に並べることができる本の重さの上限も様々です。あなたは、次の条件を満足するように本棚に本を並べることにしました。


1 巻からある巻までの「赤ベコ」が本棚に並んでいる。
それぞれの段には、巻数順に（途中で抜けている巻がないように）本が並ぶ。
各段に並べる本の重さの合計が、その段で定められた重さの上限を超えない。

各段に並べる本の厚さの合計が、その段の幅を超えない。

これらの条件を満たしたとき，この本棚に最大で何巻まで「赤ベコ」を並べることができるかを求めるプログラムを作成してください。

入力
入力は以下の形式で与えられる。
M N
w1 t1
w2 t2
:
wM tM
c1 b1
c2 b2:cN bN
最初の１行に「赤ベコ」の巻数M(1≦M≦200000)と本棚の段数N(1≦N≦15)が与えられる。続くM行に、「赤ベコ」の単行本i巻目の重さw i (1≦w i ≦100)と厚さt i (1≦t i ≦100) を表す整数が与えられる。続くN行に、本棚のi段目の重さの上限c i (1≦c i ≦108)と幅b i (1≦b i ≦108)を表す整数が与えられる。

時間制限
入力に対して、実行時間が２秒を超えてはならない。

出力
本棚に並べることができる最大の「赤ベコ」巻数を１行に出力する。

15 / 21

入出力例
入力例１3 42 23 34 43 34 4
1 12 2

出力例１3入力例２2 21 22 12 12 1

出力例２0

入力例３3 2
1 22 22 13 32 2出力例３2入力例４3 21 22 12 22 23 3

出力例４316 / 21問題 ９未知の病原菌（１４点）

英世博士は未知の病原菌を発見しました。この病原菌は、アクダマキンとゼンダマキンと呼ばれる二種類の菌が、一直線に連なった鎖状の構造をしています。人類のために、この病原菌を無害化したいと考えています。
この病原菌は、長さが２以下になると力が弱まり、免疫力によって無害化されることが分かっています。
英世博士は、この病原菌を任意の場所で切断して、前半と後半の２つの鎖にすることができます。また、２つの鎖を連結して１つの鎖にすることもできます。
しかし注意しなければいけないのは、アクダマキンの数が多い鎖はきわめて有害だということです。ある鎖においてアクダマキンの数がゼンダマキンの数よりも多くなると、その瞬間アクダマキンは無制限に増殖を始めます。これは長さ２以下の鎖についても例外ではないので、慎重に鎖を切断していかなければなりません。
どの瞬間においてもアクダマキンの数の方が多いような鎖を作ることなく、一本の鎖を長さ２以下にして無害化することは可能でしょうか。英世博士は、助手であるあなたに無害化が可能かどうか判定するプログラムを作成するよう指示しました。無害化が可能ならばその操作を出力し、不可能ならば不可能であると出力するプログラムを作成してください。ただし、その操作のステップ数が最小である必要はありません。

入力
入力は以下の形式で与えられる。
Q
str 1
str 2:
str Q
1 行目に病原菌の数 Q (1≦Q≦300)が与えられる。続くQ行に各病原菌の初期状態を表す'o' (ゼンダマキン) および 'x' (アクダマキン) からなる１つの文字列str i が与えられる。文字列str i の長さは1以上100以下である。

出力
str i について、要求を満たす切断・結合操作の列が存在する場合、出力の最初の行にはその操作列の長さを表す整数 n を出力し、続く n 行に操作の内容を１行に１操作ずつ、最初の操作から順に出力する。
切断操作は以下の形式で表すこと。
split a pa は切断する鎖の識別番号を表す整数であり、p はその鎖を切断する位置である。この操作の結果、鎖 aは先頭から p 番目（先頭を 0 から始める通し番号)の菌の直後で切断される。新しくできる２つの鎖のうち、前半のものに識別番号 m+1 が、後半のものに識別番号 m+2 が付与される（ここで、m はこれまでに付与された最も大きな識別番号を表す）。また、鎖 a は消滅する。

17 / 21

結合操作は以下の形式で表すこと。
join a ba,b は結合する鎖の識別番号を表す整数である。この操作の結果、鎖 a の末尾に鎖 b の先頭を結合した新しい鎖が作られる。新しく作られた鎖には、識別番号 m+1 が付与される(ここで、m はこれまでに付与された最も大きな識別番号を表す)。また、鎖 a,b は消滅する。
入力として与えられる最初の鎖には、識別番号 0 が付与されている。
操作の結果、問題の要求を満たすように鎖が分解されていた場合、どのような操作でも正答と判定される。操作列の長さも必ずしも最短である必要はない。ただし、操作列の長さは 20000 以下でなければならない。データセットにおいて、鎖が分解可能な場合、必ずこの条件を満たす操作列が存在することが保証される。
不正な操作列が出力された場合、誤答と判定される。不正な操作列には、以下の場合が含まれる。


切断操作 split a p において、0≦p＜(鎖 a の長さ)-1 が満たされていない場合。
切断・結合操作の対象となる鎖の識別番号がまだ生成されていないものである場合や、既に別の操作の対象となったため消滅している場合。
結合操作 join a b において、a と b が等しい場合。

要求を満たす切断・結合操作の列が存在しない場合、"-1"と出力する。

入出力例
入力例
6oooxxxx
ooooxxx
oxxooxxoooxxooooo

出力例-17split 0 0join 2 1
split 3 4split 4 0join 7 6split 8 2split 9 03split 0 1
split 2 1split 4 1-101split 0 0

例えば、入力例の２番目の病原菌 ooooxxx は、split 0 0 によりo(1)とoooxxx(2)ができる。ここで、()内の数字は識別番号を表す。

18 / 21join 2 1 によりoooxxxo(3)ができ1と2は消滅する。
split 3 4 によりoooxx(4)とxo(5)ができる。このとき{ oooxx(4), xo(5) }の鎖が存在する。
split 4 0 によりo(6)とooxx(7)ができる。{ xo(5), o(6), ooxx(7)}join 7 6 によりooxxo(8)ができる。{ xo(5), ooxxo(8)}split 8 2 によりoox(9)とxo(10)ができる。{xo(5), oox(9), xo(10) }split 9 0 により { xo(5), xo(10), o(11), ox(12) } となって終了する。

19 / 21

問題１０

アカベコ国王の配慮（１５点）

アカベコ国の国王には２人の王子がいます。国王は自分が退位するときに国を２つに分割し、それぞれの王子に一つずつ国を治めさせることにしました。新しい国の名前はアカ国とベコ国です。アカベコ国にはN個の町と、２つの町を繋ぐM本の道があります。国王は、以下の手順でアカベコ国の町と一部の道を２つの国に配分することにしました。
① 町を２つ選び、それぞれアカ国とベコ国に配分する。
② すでに配分された町sを選ぶ。さらに、町sから１本の道で繋がっている、まだ配分されていない町tを選ぶ。そして、町s、t間の道と町tを、町sが配分された国に配分する。
③ ②を、行えなくなるまで繰り返す。
実は２人の王子はあまり仲が良くないので、国王は２つの国の距離をなるべく大きくしたいと考えています。ここで、２つの国の距離とは、アカ国の町とベコ国の町を繋ぐ道の中で、最も短い道の長さです。
アカベコ国の町と道の情報が与えられたとき、分配後のアカ国とベコ国の距離の最大値と、そのような距離になる配分が何通りあるかを求めるプログラムを作成してください。ただし、２つの配分結果は、アカ国とベコ国に異なる町か道が配分された場合に区別されます。

入力
入力は以下の形式で与えられる。
N M
s1 t1 d1
s2 t2 d2:
sM tM dM
１行目は２つの整数からなる。N(2≦N≦100)は町の数、M(N-1≦M≦N(N-1)/2)は道の数を表す。続くM行に２つの町を繋ぐ道が与えられる。s i とt i (1≦s i ≠t i ≦N)はi番目の道が繋ぐ２つの町の番号を表す。
d i (1≦d i ≦109)はi番目の道の長さを表す。
入力は以下の条件を満たす。
 どの２つの町もいくつかの道を使い行き来が可能である。
 どの２つの町の間にも２本以上の道はない。
 同じ長さの道は５本以下である。

出力
分配後のアカ国とベコ国の距離の最大値と組み合わせの数を、空白区切りで１行に出力する。ただし、分配後の組み合わせの数は非常に大きくなりうるので、代わりに 1,000,000,007 で割った余りを出力する。

入出力例
入力例
6 71 2 1

出力例
7 1820 / 21

2 3 23 1 34 5 45 6 56 4 6
1 4 721 / 21