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

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

問題１

お年玉（３点）兄弟であるＡ君とＢ君は、毎年それぞれお年玉をもらっています。とても仲の良い２人は、２人のお年玉を足し合わせて半分ずつに分けています。２人がもらうお年玉の金額は、それぞれ 1000 の倍数です。

課題
Ａ君とＢ君がもらった金額が与えられたとき、１人当たりが得る金額を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
a b
１行に、Ａ君がもらった金額 a(1000≦a≦50000)とＢ君がもらった金額 b(1000≦b≦50000)が与えられる。

出力
１人当たりが得る金額を整数で１行に出力する。

入出力例
入力例１
1000 3000

出力例１2000

入力例２5000 5000

出力例２5000

入力例３1000 2000

出力例３1500

問題２買い物（４点）

あなたは、今日発売された新刊「プログラミング甲子園必勝法」を買うために、友達のＡ君と本屋に来ています。あなたはどうしてもその本を買いたいので、手持ちの金額で足りないときは、Ａ君からお金を借りようと思っています。それでも足りなければ、今回はあきらめるしかありません。

課題
あなたの手持ちの金額、Ａ君の手持ちの金額、本の値段が与えられたとき、本を買うためにＡ君から借りなければならない最小の金額を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
m f b
１行に、あなたの手持ちの金額 m(0≦m≦10000)とＡ君の手持ちの金額 f(0≦f≦10000)と本の値段 b(100≦b≦20000)が与えられる。

出力
本を買うためにＡ君から借りなければならない最小の金額を１行に出力する。ただし、Ａ君の手持ちの金額をすべて借りても本を買えないときは、「NA」と 1 行に出力する。

入出力例
入力例１1000 3000 3000

出力例１2000

入力例２5000 3000 4500

出力例２0入力例３500 1000 2000

出力例３NA問題３９月Ｘ日（４点）

２０１７年９月９日は土曜日です。２０１７年の９月Ｘ日は何曜日でしょうか？

課題
２０１７年９月の日にちが与えられたとき、その日が何曜日か報告するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
X
１行に、２０１７年９月の日にち X(1≦X≦30)が与えられる。

出力与えられた日の曜日を１行に出力する。ただし、月曜日は「mon」、火曜日は「tue」、水曜日は「wed」、木曜日は「thu」、金曜日は「fri」、土曜日は「sat」、日曜日は「sun」と出力せよ。

入出力例
入力例１1出力例１fri

入力例２9出力例２sat

入力例３30出力例３sat

問題４

エルの予約

（５点）

ＰＣＫ研究所が運用するスーパーコンピュータ「エル」は、研究所外部の企業や大学などの依頼に応じて様々な計算を行っています。エルの使用には予約が必要で、予約の際は開始時刻と終了時刻を指定します。ただし、異なる予約が重複してはいけません。

課題
新しい予約が、すでに存在する予約のどれかと重複するかを報告するプログラムを作成せよ。ただし、ある予約の終了時刻と、別の予約の開始時刻が同じ場合は重複しないと考えて良い。また、すべての時刻は、エルの運用開始からの経過分数で与えられる。

入力
入力は以下の形式で与えられる。
a bN
s1 f1
s2 f2
:sN fN
１行目に新しい予約の開始時刻aと終了時刻b(0≦a＜b≦1000)が整数で与えられる。２行目にすでに存在する予約の数N(0≦N≦100)が与えられる。続くN行に、すでに存在する予約の開始時刻siと終了時刻fi(0≦si＜fi≦1000)が整数で与えられる。すでに存在する予約どうしに重複は無い。

出力
新しい予約がすでに存在する予約と重複するなら 1、重複しないなら 0 と、1 行に出力する。

入出力例
入力例１5 73
1 44 57 10

出力例１0入力例２3 737 10
1 44 5

出力例２1問題５電線（６点）

ぼくは内装職人です。今回依頼があったお客さんの家には、長方形の壁一面にパネルがぴったりと敷き詰められています。パネルはすべて横の長さが２ｍ、縦の長さが１ｍの長方形で、横方向に x 枚、縦方向に y 枚並んでいます。この壁の左上隅から右下隅まで、まっすぐ電線を張ることになりました。電線は図のように、壁の隅を含めたパネルの継ぎ目と電線の交点で固定することにします。下の図の場合には、交点の数は９つです（○が交点の位置を示しています）。
x＝４枚

y＝６枚

図： パネルと電線の交点

課題
パネルの横方向と縦方向の枚数が与えられたとき、パネルの継ぎ目と電線の交点の数を求めるプログラ
ムを作成せよ。ただし、パネルの継ぎ目の太さと電線の太さは考えないものとする。

入力
入力は以下の形式で与えられる。
x y
１行に、パネルの横方向の枚数x(1≦x≦1000)とパネルの縦方向の枚数y(1≦y≦1000)が整数で与えられる。

出力パネルの継ぎ目と電線の交点の数を１行に出力する。

入出力例
入力例１4 4

出力例１5入力例２4 6

出力例２9問題６

トランポリン（１１点）

複数台のトランポリンが、１０ｍ間隔で直線上に設置されています。それぞれのトランポリンについて、水平方向に跳ぶことができる最大距離が決まっています。左端のトランポリンから始めて、跳ぶことができる範囲にあるトランポリンに跳び移っていきます。これを繰り返して、まずは右端のトランポリンまで行ってから、左端のトランポリンに戻りたいと思います。この間、一度もトランポリンから降りずに往復することができるでしょうか。

課題
各トランポリンで水平方向に跳ぶことができる最大距離が与えられたとき、左端と右端の間を往復できるかを報告するプログラムを作成せよ。ただし、トランポリンは大きさのない点とみなす。

入力
入力は以下の形式で与えられる。
N
d1
d2:
dN
１行目にトランポリンの台数(2≦N≦3×105)が与えられる。続くN行に、左からi番目のトランポリンで跳ぶことができる最大距離di(1≦di≦106)が、メートル単位の整数で与えられる。

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

出力
左端と右端の間を往復できるなら「yes」、できないなら「no」と１行に出力する。

入出力例
入力例１4205101出力例１no入力例２310510出力例２no入力例３42030120出力例３yes

問題７

積み荷の配置（１１点）

会津海上運送会社に、新たな積み荷の輸送依頼が舞い込んだ。今回依頼された荷物は、すべて同じ大きさで、横幅が２ｍ、縦幅が２ｍである。貨物室は長方形で、横幅が４ｍで固定されているが、縦幅はさまざまである。また、荷物は横と縦それぞれ１ｍを単位とした区画の境界に合わせて置く必要があり（５０ｃｍずらしたりなどはできない）、傾けて置いたり、重ねて置いたりすることはできない。また、荷物が置けない区画もある。
縦幅が５ｍの貨物室の例

荷物の置き方の例禁止された置き方の例

横幅４ｍ

横幅４ｍ

横幅４ｍ

①
縦幅５ｍ縦幅５ｍ

縦幅５ｍ②① 区画の境界に合わせて配置す

荷物が置ける区画
荷物荷物が置けない区画る必要があるため×② 傾けて置けないため×

現在使える船の貨物室に荷物をできるだけ積んで輸送したいが、最大でいくつ積めるかを知りたい。

課題
貨物室の縦の長さと、その中で荷物が置けない区画が与えられたとき、最大でいくつの荷物が積めるかを報告するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
H N
x1 y1
x2 y2
:
xN yN
１行目にメートル単位の貨物室の縦の長さH(2≦H≦104)と、荷物が置けない区画の数N(0≦N≦4×104)が与えられる。続くN行に、荷物が置けない区画の位置が与えられる。xi(0≦xi≦3)とyi(0≦yi≦H-1)はそれぞれ横方向と縦方向の値を表す整数である。ただし、左下隅の区画の位置をx=0,y=0とする。同じ位置が２回以上現れることはない。

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

出力最大でいくつの荷物が積めるかを１行に出力する。

入出力例
入力例１5 30 1
1 23 3

出力例１2

入力例１は問題文中の左端の図の状態を表す。
入力例２6 40 2
1 3
3 40 5

出力例２4

問題８ダンジョン（１１点）

Ｂ君は人気のゲーム「ダンジョン」で遊んでいる。ゲームは、W×H 個のマス目状に区切られた長方形の盤面上で行われる。マスの位置を表すために、各マスには列番号と行番号が割り当てられている。列番号が x、行番号が y のマスは(x, y)で表される。左上隅がマス(0, 0)、右下隅がマス(W-1, H-1)である。
Ｂ君はキャラクターのボムボム君を動かして、ゲームのクリアを目指す。ボムボム君は、最初スタート地点のマス（0, 0）にいる。盤面上にいる全ての敵を倒すとゲームクリアとなる。敵が動くことはない
が、ボムボム君は、以下の２種類の行動を何度でもとることができる。


上下左右の方向へ１マス動く。ただし、盤面の外に出てはいけない。



爆弾を使用し、自分がいるマスと列番号が同じマスにいる敵と、行番号が同じマスにいる敵を一掃する。

ボムボム君は 1 マス動くためにコスト１を消費する。爆弾の使用回数に制限はなく、爆弾を使用するコストは発生しない。また、ボムボム君は爆弾の影響を受けることはなく、敵がいるマスにも移動することができる。

課題
盤面の大きさと敵の情報が与えられたとき、ボムボム君が全ての敵を倒すための最小のコストを出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
W H N
x1 y1x2 y2:
xN yN
１行目に盤面の左右方向のマスの数 W(1≦W≦105)、上下方向のマスの数 H(1≦H≦105)、敵の数 N(1≦N≦105)が与えられる。
続く N 行に、i 番目の敵がいるマスの列番号 xi(0≦xi≦W-1)と行番号 yi(0≦yi≦H-1)が与えられる。同じマスに複数の敵がいることはない。

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

出力最小のコストを１行に出力する。

入出力例
入力例１5 4 40 3
1 12 22 3

出力例１2

入力例２6 6 52 15 23 3
1 41 5

出力例２4入力例３8 8 46 0
7 00 60 7

出力例３0

問題９

人気のユーザ名（１４点）

最近ワカマツ国で流行の「グチッター」は、「ぼやき」を投稿するサービスです。閲覧数を稼ぎたいまさるくんは、どうすれば人気が出るかを調べてみました。どうやらユーザ名の文字列が辞書順で前にある人ほど人気があるようです。まさるくんはすでにユーザ名を登録していますが、一定の回数までであれば、登録したユーザ名の隣接する２文字の順番を交換することができるようです。

課題
文字列と交換回数の上限が与えられたとき、与えられた上限以内で文字列内の隣接する２文字の順番を交換してできる新しい文字列の中から、辞書順で最小になるものを報告するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
sk
１行目にユーザ名の文字列sが与えられる。２行目に交換回数の上限k(0≦k≦109)が与えられる。文字列は、英小文字だけから成る、長さが1以上2×105以下の文字列である。

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

出力
辞書順で最小の文字列を１行に出力する。

入出力例
入力例１pckoshien3

出力例１ckopshien

入力例２pckoshien10

出力例２cekophsin

問題１０ 道路網改修（１４点）

観光で有名な会津国には、それぞれ 0 から N-1 までの番号が割り当てられた N 個の都市があり、２つの都市を結ぶ一方通行の M 本の道路で道路網が形成されている。
会津国では、都市を結ぶすべての道路沿いに桜並木がある。観光客に桜を楽しんでもらえるように、すべての道路を巡ることができるような道路網に改修したい。そのため、以下の条件を満たすように２つの都市を直接結ぶ道路を何本か増設することにした。


増設する道路は、一方通行のものに限る。
任意の都市から出発したとき、増設したものも含めて国内のすべての道路を１度以上通って出発した都市に戻ることができる。

会津国の観光推進担当者であるあなたは、プログラムを作成して道路建設計画を立てることになった。

課題
会津国の都市と道路の情報が与えられたとき、増設しなければならない道路の数の最小値を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N M
s1 t1
s2 t2
:
sM tM
１行目に都市の数 N(1≦N≦104)、道路の数 M(0≦M≦105)が与えられる。続く M 行に、i 番目の道路が結ぶ始点と終点の都市の番号 si,ti(0≦si,ti≦N-1)が与えられる(si≠ti)。ただし、同じ道路は２回以上与えられない。

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

出力増設する道路の数の最小値を１行に出力する。

入出力例
入力例１6 70 22 11 02 34 34 55 4

出力例１2

入力例２6 90 22 11 02 34 34 55 45 23 4

出力例２0

問題１１ ネットワークの課金システム（１７点）

それぞれ 0 から N-1 までの番号が割り当てられた N 台のマシンが、合計 N-1 本の双方向に通信できるケーブルで接続され、ネットワークを形成している。どの２つのマシンも、いくつかのケーブルをたどって双方向に通信を行うことができる。このネットワークでは、マシンが更新されると、通信量の増大に備えるために、そのマシンに直接接続されているすべてのケーブルをより太いものに交換する。
２つのマシンの間の通信料金は、その間を経由するすべてのケーブルの通信料金の総和になる。ただし、このネットワークはユニークな課金システムで運営されており、太さが K の倍数であるようなケーブルは、そのケーブルの分の通信料金が無料になる。それ以外のケーブルは、太さと同じ通信料金がかかる。
あなたの仕事は、このネットワークの料金計算システムを開発することである。

課題
ネットワークの形状とＱ個の命令が与えられたとき、それぞれの命令を処理するプログラムを作成せよ。
ただし、命令は以下の２種類である。
 マシン x に直接接続されている全てのケーブルの太さを d だけ増加させる。
 マシン s とマシン t の間の通信料金を報告する。

入力
入力は以下の形式で与えられる。
N K
a1 b1 c1
a2 b2 c2:
aN-1 bN-1 cN-1
Q
query1
query2:
queryQ
１行目に、マシンの総数N(2≦N≦105)と、通信料金が無料になる太さを決める数K(1≦K≦105)が与えられる。続くN-1行に、２つのマシンを直接つなぐケーブルの情報が与えられる。aiとbi(0≦ai＜bi≦N-1) はi番目のケーブルがつなぐ２つのマシンの番号を表し、ci(1≦ci≦105)はそのケーブルの初期状態での太さを表す。ただし、どの２つのマシンについても、それらを直接つなぐケーブルは１本以下とする。続く１行に、命令の数Q(1≦Q≦105)が与えられる。続くQ行にi番目の命令queryiが与えられる。各queryiは、以下のいずれかの形式で与えられる。

add x dまたはsend s t
add x d は、マシン x(0≦x≦N-1)に直接接続されているすべてのケーブルの太さを d(1≦d≦105)だけ増加させる。
send s t は、マシン s(0≦s≦N-1)とマシン t(0≦t≦N-1)の間の通信料金を報告する。ただし、s≠t である。
入力には必ず１つ以上の send 命令が含まれる。

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

出力
各 send 命令について、マシン s とマシン t の間の通信料金を、それぞれ１行に出力する。

入出力例
入力例
6 30 1 10 2 1
0 3 12 4 1
2 5 13send 1 4add 2 2
send 1 4

出力例31