問題１

気温の差（３点）

選手の皆さん、パソコン甲子園にようこそ。イベントに参加するには体調管理が大切です。気温が大きく変動する季節の変わり目には体に負担がかかり、風邪をひきやすいと言われています。一番気を付けなければいけない日は、最高気温と最低気温の差が最も大きい日です。１日の最高気温と最低気温が７日分与えられたとき、それぞれの日について最高気温から最低気温を引いた値を出力するプログラムを作成してください。

入力
入力データは以下の形式で与えられる。
a1 b1
a2 b2:
a7 b7
入力は7行からなり、i行目にはi日目の最高気温a i (-40≦a i ≦40)と最低気温b i (-40≦b i ≦40)を表す整数が与えられる。すべての日において、最高気温a i は必ず最低気温b i 以上となっている。

出力
7 日分の気温の差を 7 行に出力する。

入出力例
入力例
30 1939 2019 1825 2022 2123 1010 -10

出力例11191511320問題２

チケットの売り上げ（４点）

今日は、アイヅ・エンターテインメント社イチオシのアイドルグループ「アカベコ＆コボウシ」のチケット発売日です。チケットには以下の４種類があります。
Ｓ席 6000 円
Ａ席 4000 円
Ｂ席 3000 円
Ｃ席 2000 円
販売責任者のあなたは、ドキドキしながら発売開始を待っています。いよいよ発売開始。売れ行き絶好調です！
発売開始からしばらく経ったところで、それまでの注文をまとめた表を受け取りました。表の各行には、それまでに売れたチケットの種類と枚数が書いてあります。ただし、チケットの種類がＳ，Ａ，Ｂ，Ｃの順に現れるとは限りません。この表の行ごとの売上金額を求めるプログラムを作成してください。

入力
入力データは以下の形式で与えられる。
t1 n1
t2 n2
t3 n3
t4 n4
入力は4行からなる。i行目には、チケットの種類を表す整数t i (1≦t i ≦4)と枚数を表す整数n i (0≦n i ≦10000)が与えられる。チケットの種類を表す整数1, 2, 3, 4は、それぞれＳ席、Ａ席、Ｂ席、Ｃ席を表す。t 1 ,t 2 ,t 3 ,t 4 の値として1から4までの数は必ず１度だけ現れるが、1, 2, 3, 4の順で与えられるとは限らない。

出力
行ごとに売上金額を出力する。

入出力例
入力例 13 10
1 44 12 5

出力例 130000
24000
200020000

入力例 21 12 0
3 14 1

出力例 26000030002000

問題３

入場料金

（５点）

アイヅ温泉には、浴場とプールがあり、浴場を利用するには入浴券を、プールを利用するにはプール券をそれぞれ買う必要があります。これらの券の値段は、日によって変わるかもしれません。また、アイヅ温泉には以下のようなルールがあります。
 券は購入当日１回の利用に限り有効。
「入浴券５枚以上かつプール券２枚以上」でまとめて買うと、すべての券が２割引になる。

温泉好きの貞吉さんとその友人たちは、アイヅ温泉に毎日のように通っています。彼らは皆気まぐれで、日によって使う枚数は異なります。アイヅ温泉には割引ルールがあるため、グループで協力して上手に買えば、合計料金を安く済ますことができるかもしれません。
入浴券とプール券の料金、使用する入浴券の枚数とプール券の枚数が入力として与えられたとき、最も安い合計料金を出力するプログラムを作成してください。ただし、使用する枚数より多く券を買うことで合計料金が安くなるなら、買った券すべてを使わなくともよいものとします。

入力
入力は以下の形式で与えられる。
N
x1 y1 b1 p1
x2 y2 b2 p2:
xN yN bN pN
１行目のN(1≦N≦365)は料金を計算したい日数である。続くN行に、i日目の入浴券の料金x i (100≦x i ≦1000)、プール券の料金y i (100≦y i ≦1000)、使用する入浴券の枚数b i (0≦b i ≦6)、使用するプール券の枚数p i (0≦p i ≦6)が与えられる。入浴券とプール券共に料金は50円刻みである。

出力それぞれの日について最も安い合計料金を１行に出力する。

入出力例
入力例 12100 100 1 11000 500 5 2

出力例 12004800

入力例 25500 500 1 1500 500 5 21000 100 0 61000 100 6 0100 1000 0 0

出力例 210002800
60049600

問題４おそろいの景品（８点）

ジョウ君とヤエさんは仲の良いカップルです。ジョウ君はカプセル玩具自販機(ガチャポン)の景品を集めており、二人で出かけたときも、ガチャポンを見つけると何度かやってみるほどの熱の入りようです。
ヤエさんは楽しそうなジョウ君をそばで見ているだけでしたが、ジョウ君の今度の誕生日プレゼントにガチャポンの景品をひとつあげることにしました。ヤエさんはガチャポン自体にはあまり興味がわきませんでしたが、できればジョウ君とおそろいの景品が欲しいと思っています。
ヤエさんがやってみようと思うガチャポンは、１回のチャレンジで景品がひとつ出ます。品切れのものも含め景品が何種類あるのかと、それぞれの景品がいくつ残っているのかはわかります。しかし、1 回のチャレンジでどの景品が出るかはわかりません。そこで、景品が出る順番にかかわらず、ヤエさんが同じ景品を必ず２つ得るために最低限必要なチャレンジの回数を出力するプログラムを作成してください。

入力
入力は複数のデータセットからなる。入力の終わりはゼロ 1 つの行で示される。各データセットは以下の形式で与えられる。
Nk 1 k 2 ... k N
各データセットは2行であり、1行目に景品が何種類あるかを表す整数N(1≦N≦10000)が与えられる。続
く1行に各景品がいくつ残っているのかを表す整数k i (0≦k i ≦10000)が与えられる。
データセットの数は100を超えない。

出力
データセットごとに、同じ景品を必ず２つ得るために最低限必要なチャレンジの回数を出力する。ただし、不可能な場合は NA と出力する。

入出力例
入力例
出力例
233 2NA320 1 1110000
１つ目のデータセットでは、運良く１種類目か２種類目の景品が連続で出て２回で済む可能性はあるが、同じ種類の景品を必ず２つ得るためには３回チャレンジする必要がある。
２つ目のデータセットでは、２つ以上残っている景品がもともと無いので不可能である。
３つ目のデータセットでは、景品は１種類だけなので２回のチャレンジでその景品が必ず２つ得られる。

問題５

坊主めくりの結末（１０点）

百人一首の札を使った遊戯の１つに、「坊主めくり」というものがあります。絵札だけを使う簡単な遊戯なので広く楽しまれています。きまりには様々な派生型がありますが、ここで考える坊主めくりは N
人の参加者で、以下のようなルールで行います。


６４枚の「男」、１５枚の「坊主」、２１枚の「姫」、計１００枚の札を使う。
絵が見えないように札を裏がえしにしてよく混ぜ、「札山」をつくる。

参加者の一人目から順番に１枚ずつ札山の札を引く。N 人目の次は、また一人目から繰り返す。



引いた札が男なら、引いた人はその札を手に入れる。
引いた札が坊主なら、引いた人はその札を含め、持っている札をすべて「場」に出す。
引いた札が姫なら、引いた人はその札を含め、場にある札をすべて手に入れる。



札山の札がなくなったら終了で、一番多くの札を持っている人の勝ち。

参加者数と札山に積まれた札の順番が与えられたとき、遊戯が終了した時点で各参加者が持っている札数を昇順で並べたものと、場に残っている札数を出力するプログラムを作成してください。

入力
入力は複数のデータセットからなる。入力の終わりはゼロ一つの行で示される。各データセットは以下の形式で与えられる。
Nc 1 c 2 ... c 100
各データセットは2行であり、1行目に参加者数を表す整数N(2≦N≦10)が与えられる。続く1行に札山に積まれた札の並びを表す文字列が与えられる。文字c i はi番目に引かれる札を表しており、Mが男、Sが坊主、Lが姫の札を表す。各文字の間に空白は無い。
データセットの数は100を超えない。

出力
データセットごとに、遊戯が終了した時点での札数の並びを１行に出力する。札数の並びとして、各参加者が持っている札の枚数を昇順に並べだものの後に、場に残っている札の枚数を出力する。各札数の間は空白１つで区切る。行の終わりには空白を出力しない。

入出力例
入力例
2
SSSSSSSSSSSSSSSLLLLLLLLLLLLLLLLLLLLLMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMM
2
SSSSSSSSSSSSSSLLLLLLLLLLLLLLLLLLLLMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMSL

出力例
42 58 00 100 00 0 3 10 59 28

5
MMMMMMSLSLLMMMSMMSLMMMLMMMMLSLLLLMLSMML
MMLLMSSSLMMMMLMLSMLMSMMMMMMMSMMMMMMLMMM
MMSMMMLMMLMMMMMMMMMSSM
0※ 入力例で、各データセットにおける札山に積まれた札を表す文字列は、表示の都合上 3 行に見えるが、実際は 1 行である。

問題６

陣形

（１２点）

プログラマー養成校であるアカベ高校では、チーム戦の競技プログラマーの役割を以下の３タイプに分けています。
Ｃ： コーダー
Ａ： アルゴリズマー
Ｎ：

ナビゲーター

言語を熟知しており、コーディングを行う。
論理的思考が得意であり、アルゴリズムを考える。
読解力に長けており、問題の分析・デバッグをする。

この高校では以下のいずれかの陣形で３人一組のチームを構成しています。
ＣＣＡ：
ＣＣＣ：
ＣＡＮ：

バランスがとれている安定型
スピードを見込めるがリスクの高い速攻型
正確に問題を解く慎重型

競技プログラミング部のコーチであるあなたは、これらの部員をうまく組み合わせ、できるだけ多くのチームを結成できるよう、毎年気を配っています。そこで、コーダーの人数、アルゴリズマーの人数、ナビゲーターの人数が入力として与えられたとき、最大何チーム作れるかを出力するプログラムを作成してください。

入力
入力は 1 つのデータセットからなる。入力データは以下の形式で与えられる。
Qc1 a1 n1
c2 a2 n2：cQ aQ nQ
1行目のQ(0≦Q≦100)はチーム数を求めたい年数である。続くQ行に各年の役割別の人数が与えられる。
各行にはコーダーの人数c i (0≦c i ≦1000)、アルゴリズマーの人数a i (0≦a i ≦1000)、ナビゲーターの人数n i (0≦n i ≦1000)が与えられる。

出力
年ごとに、作成できる最大のチーム数を 1 行に出力する。

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

入出力例
入力例
43 0 01 1 1
9 4 10 1 2

出力例
1140

問題７

プログラミングコンテスト（１６点）

白虎大学では毎年プログラミングコンテストが開催されています。チームの総数を N としたとき、チームには 1 から N のチーム ID がそれぞれ割り当てられています。コンテストは全てのチームの得点が 0 の状態から開始し、L 秒間連続して行われます。
今年のコンテストは、テレビで中継されることになりました。コンテストの間テレビに映るのは、その時点で最も得点の高いチームだけです。ただし、該当するチームが複数いるときは、その中でチーム ID の一番小さいチームが映ります。映すべきチームが変わると、瞬時にカメラが切り替わります。
あなたはコンテストのログを入手しました。ログには、あるチームの得点が変化した時のレコードがすべて含まれています。各レコードは「チーム d がコンテスト開始 t 秒後の時点で x 点獲得した」という形式で与えられています。なお、減点される場合もあるので、現在の得点が 0 より小さくなることもあります。
コンテストのログを入力とし、コンテスト開始から終了までの間にテレビに映った時間が最も長いチー
ムの ID を報告するプログラムを作成してください。

入力
入力は 1 つのデータセットからなる。入力は以下の形式で与えられる。
N R L
d1 t1 x1
d2 t2 x2:
dR tR xR
１行目は３つの整数からなる。N(2≦N≦100000)はチーム数、R(0≦R≦1000000)はログに含まれるレコードの数である。L(1≦L≦1000000)はコンテストの時間（長さ）を表す。続くR行に各レコードの情報が与えられる。各レコードはチームd i (1≦d i ≦N)がコンテスト開始t i (0＜t i ＜L)秒後の時点でx i (-1000≦x i ≦1000)点獲得あるいは減点されたことを示す。ただし、t i , x i は整数であり、t i-1 ≦t i である。

出力
コンテスト開始から終了までの間にテレビに映った時間が最も長いチームの ID を１行に出力する。ただし、最も長いチームが複数あるときは、その中でチーム ID の一番小さいチームを出力する。

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

入出力例
入力例 13 4 600
3 100 5
1 200 102 400 20
3 500 20

出力例 11入力例 23 5 600
3 100 5
1 200 102 300 30
1 400 -8
2 400 -27

出力例 23問題８

勉強会

（２０点）

プログラマー養成校のアカベ高校には、生徒自身で運営するユニークな勉強会があります。プログラマーは新しい技術を常に取り入れることが大切なので、この勉強会を通して自学自習の習慣を身につけることがこの活動のねらいです。
生徒は全部でN人おり、それぞれが入学時のプログラミングコンテストの結果で得られたスコアを持っています。勉強会ではN人の生徒のうち何人かがリーダーになり、各リーダーがそれぞれのグループを運営するとともに、自らの運営するグループに参加します。
リーダー以外の生徒は、自分のスコアよりも低いスコアのリーダーが運営するグループには参加できません。また、0以上のある値rを１つ決め、グループに参加する生徒とリーダーのスコアの差がr以内となるようにしています。つまり、グループのリーダーのスコアがsのとき、自分のスコアがsを超えているか、あるいは s–r 未満ならば、そのグループには参加できません。
あなたは勉強会の実行委員長であり、運営準備のためにシミュレーションを行うことにしました。シミュレーションでは、リーダーが誰もいない状態から始め、以下の操作を何回か繰り返します。
 生徒をリーダーに加える。


生徒をリーダーから外す。
要求時点でのリーダーの組み合わせについて、どのグループにも参加できない生徒がx人以下になるような、最小のrを求める。

このようなシミュレーションを行うプログラムを作成してください。

入力
入力は 1 つのデータセットからなる。入力は以下の形式で与えられる。
N Q
s1s2:
sN
QUERY 1QUERY 2:QUERY Q
1 行目に生徒の数 N(1≦N≦1000000)、処理要求の数(0≦Q≦1000)が与えられる。
続くN行にi番目の生徒のスコアを示す整数s i (0≦s i ≦1,000,000,000)が与えられる。生徒は 1,2,…,Nで番号付けされているものとする。
続くQ行に処理要求QUERY i が与えられる。処理要求は時系列順に与えられる。処理要求はADD, REMOVE,CHECKの 3 種類あり、各QUERY i は以下のいずれかの形式で与えられる。

ADD aまたは
REMOVE aまたは
CHECK xADD a は番号 a(1≦a≦N)の生徒をリーダーに加えることを表す。
REMOVE a は番号 a(1≦a≦N)の生徒をリーダーから外すことを表す。
CHECK x は出力要求を表す。どのグループにも参加できない生徒の数の上限 x(0≦x≦N)が与えられる。
なお、入力は以下の条件を満たすものとする。


どの時点でも、リーダーの人数が 100 人を超えることはない。
その時点でリーダーである生徒をリーダーに加えることはない。



その時点でリーダーでない生徒をリーダーから外すことはない。

出力
時系列順に各出力要求の時点で、どのグループにも参加できない生徒が x 人以下になるような最小の rを 1 行に出力する。ただし、どのような r を選んでも x 人以下にすることが不可能であれば NA と出力する。

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

入出力例
入力例１5 8510873ADD 1
ADD 3
CHECK 0CHECK 1CHECK 2CHECK 3CHECK 4CHECK 5出力例１NA21000

入力例２5 28510

出力例２NANANA873CHECK 0CHECK 1CHECK 2CHECK 3CHECK 4CHECK 5ADD 1CHECK 0CHECK 1CHECK 2CHECK 3CHECK 4CHECK 5REMOVE 1ADD 3CHECK 0CHECK 1CHECK 2CHECK 3CHECK 4CHECK 5ADD 1
CHECK 0CHECK 1CHECK 2CHECK 3CHECK 4CHECK 5

NANA0NA
NANA
200
NA53100
NA21000

問題９

ハッピーエンド問題（２２点）「ハッピーエンド問題」と呼ばれる数学の未解決問題に関連したプログラムを書いてみましょう。平面上に与えられたN個の点から、ちょうどk個の点を結んでできる凸多角形のうち、最も面積の小さいものを見つけるプログラムを作成してください。ただし、N個の点の座標を与えられた後、質問として凸多角形の角の個数kがいくつか与えられます。
（補足：ハッピーエンド問題について）
平面上にどの３点も同じ直線上に乗らないようにN個の点を置きます。そのとき、どのように点を置いても、k個の点をうまく選ぶとk個の角をもつ凸多角形が必ず作れると予想されています。 今のところ、三角形ならばN=3、四角形ならばN=5、五角形ならばN=9、六角形ならばN=17であればよいことが、２００６年までに証明されています。また、三角形以上のすべてのk角形に対して、N=1+2k-2という予想がありますが、いまだ証明されていません。これは１００年にわたり研究が進められている難問です。
この問題には、「ハッピーエンド問題」という素敵な名前がつけられています。ある男女がこの問題を研究しているうちに仲良くなって、ついに結婚したことにちなんで、友人の数学者が名付けたそうです。
ロマンチックですね。

入力
入力は 1 つのデータセットからなる。入力データは以下の形式で与えられる。
N
x1 y1:
xN yNQk1:
kQ
１行目に平面上の点の個数N(3≦N≦40)が与えられる。続くN行に各点の座標が与えられる。各点には1からNまでの番号が、入力される順番に付けられている。x i とy i (-10000≦x i ,y i ≦10000)はi番目の点のそれぞれx座標とy座標を表す整数である。x軸の正方向は右向き, y軸の正方向は上向きに取るものとする。
続く１行に質問の数Q(1≦Q≦N)が与えられる。続くQ行に質問が与えられる。k i (3≦k i ≦N)はi番目の質問である凸多角形の角の個数を表す。
なお、入力は以下の条件を満たすものとする。
 入力される点の座標はすべて異なる。
 どの３点も同じ直線上には乗らない。
 各質問に対して面積最小の凸多角形は１つであり、２番目に小さい凸多角形との面積の差は0.0001以上。

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

出力
質問ごとに、面積が最小の凸多角形の全頂点を 1 行に出力する。凸多角形の頂点で最も下にあるものの中で最も左にある頂点から順に、反時計周りで頂点の番号を出力する。頂点の番号の間は空白 1 つで区切る。行の終わりには空白文字を出力しない。ただし、凸多角形が作れない場合は NA と出力する。

入出力例
入力例 150 03 05 21 40 33345出力例 11 4 5
1 2 4 5
1 2 3 4 5入力例 260 03 05 2
1 40 33 243456出力例 26 3 56 3 4 5
1 2 6 4 5NA