問題１ワード（３点）

コンピュータで扱われるデータの最小単位をビット(bit)と呼び、複数のビットをまとめて表した情報量をワード(word)と呼びます。現在、多くのコンピュータでは１ワードを３２ビットとして処理しています。

課題
１ワードを３２ビットで表すコンピュータについて、ワード単位で与えられたデータ量 W をビット単位で出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
W
入力は１行からなり、データ量W(0≦W≦100)が与えられる。

出力
ビット単位の値を１行に出力する。

入出力例
入力例１

出力例１4128

入力例２

出力例２396問題２

日の出と日の入り（４点）

太陽が現れることを「日の出」、隠れることを「日の入り」と呼びますが、その厳密な時刻は太陽が地平線に対してどのような位置にある時でしょうか。
下の図のように、太陽を円、地平線を直線で表すことにします。このとき、太陽の「日の出」「日の入り」の時刻は、太陽を表す円の上端が地平線を表す直線と一致する瞬間とされています。日の出の時刻を過ぎ、円の上端が直線より上にある時間帯が昼間、円が直線の下へ完全に隠れている時間帯が夜間となります。

課題
ある時刻の地平線から太陽の中心までの高さと、太陽の半径を入力とし、その時刻が「昼間」か、「日の出または日の入り」か、「夜間」かを出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
H R
入力は１行からなり、ある時刻の地平線から太陽の中心までの高さを表す整数 H(-1000≦H≦1000)と半径を表す整数 R(1≦R≦1000)が与えられる。ただし、H は太陽の中心が地平線上にあるときを 0 として、それより上にあるときは正、下にあるときは負とする。

出力昼間のとき「1」、日の出または日の入りのとき「0」、夜間のとき「-1」を１行に出力する。

入出力例
入力例１

出力例１-3 30

入力例２

出力例２3 31

入力例３出力例３-4 3-1

問題３

日本の暦（５点）「西暦」は西洋から輸入された概念ですが、日本には暦上の年を表す方法として「元号」に年を付けて識別する和暦という概念があります。例えば今年は西暦なら２０１６年ですが、和暦なら平成２８年です。どちらもよく使われる年の表現方法ですが、ある年の西暦がわかっていても和暦で何年かわからない、またはその逆の状況を経験したことはありませんか？

課題
西暦で年が与えられたとき和暦の年を、和暦で年が与えられたとき西暦の年を出力するプログラムを作成せよ。ただし、西暦と和暦の対応は、簡単のため以下のようにする。
西暦

和暦

１８６８年から１９１１年

明治元年から明治４４年

１９１２年から１９２５年

大正元年から大正１４年

１９２６年から１９８８年

昭和元年から昭和６３年

１９８９年から２０１６年

平成元年から平成２８年

入力
入力は以下の形式で与えられる。
E Y
入力は１行からなり、E(0≦E≦4)は与えられる暦の種類、Yはその暦での年であり、Eが0のときは西暦Y(1868≦Y≦2016)年、1のときは和暦の明治Y(1≦Y≦44)年、2のときは和暦の大正Y(1≦Y≦14)年、3のときは和暦の昭和Y(1≦Y≦63)年、4のときは和暦の平成Y(1≦Y≦28)年を表す。

出力
西暦ならば和暦に、和暦ならば西暦に変換した結果を、１行に出力する。ただし、西暦を和暦に変換した結果は、明治なら文字「M」、大正なら文字「T」、昭和なら文字「S」、平成なら文字「H」を先頭に付けて出力する。

入出力例
入力例１

出力例１0 2015

H27

入力例２

出力例２0 1912

T1

入力例３

出力例３2 11912

入力例４

出力例４4 282016

問題４

ニュータウン（８点）

会津県では人口増加のためにニュータウンを作ることにしました。そのために、新たに長方形の土地を開拓し、この土地を余すところなく、すべて同じ大きさの正方形からなる区画に区切ることを決めました。この土地の整備には、区画数に比例した費用がかかりますが、県としてはこの費用を最小にしたいと考えています。

課題
新たに開拓した土地の東西方向と南北方向の長さと、１区画当たりの整備費用が与えられたとき、すべての区画を整備したときにかかる、最小の整備費用を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
W H C
入力は１行であり、新たに開拓した土地の東西方向の長さW(1≦W≦1000)と南北方向の長さH(1≦H≦1000)、区画当たりの整備費用C(1≦C≦1000)が整数で与えられる。

出力
土地を整備するために必要な最小の費用を１行に出力する。

入出力例
入力例１出力例１10 20 510２個の正方形で土地を余すところなく区切ることができ、１区画当たりの整備費用が５なので、１０と出力する。
入力例２出力例２27 6 118

１８個の正方形で土地を余すところなく区切ることができ、１区画当たりの整備費用が１なので、１８と出力する。

問題５形状データ処理（８点）

コンピュータグラフィクスでは、三次元の形状を表現する方法として、ポリゴンモデルが使われます。
ポリゴンモデルとは、頂点座標と、それらの頂点のつなぎ方を与えて面を作るモデルです。
一般のポリゴンモデルでは、任意の多角形を扱えますが、今回は三角形からなるポリゴンモデルを考えることにします。任意のポリゴンモデル

頂点 3は三角形を表す面情報の集まりとして表すことができます。
頂点 1

一つの面情報は、３つの頂点を並べて表します。ただし、並び方が異なるだけで同じ３点からなる場合は、同じ面情報を表すことにします。例
えば、右の図の四面体で、頂点１,２,３を繋いでできる面は、頂点２,３,１や、頂点３,２,１などのように表すこともできます。このように、

頂点 4

同じ面情報が複数あると無駄になるので、１つにまとめてしまった方が頂点 2良いでしょう。

課題
面情報が与えられたとき、重複した面を無くすために消さなければならない面情報の個数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N
p11 p12 p13
p21 p22 p23:

pN1 pN2 pN3
１行目に、ポリゴンモデルの面情報の数N(1≦N≦1000)が与えられる。続くN行に、i番目の面を作るために使う頂点の番号pij(1≦pij≦1000)が与えられる。ただし、一つの面について、同じ頂点を２度以上使うことはない（pi1≠pi2かつpi2≠pi3かつpi1≠pi3である）。

出力重複した面を無くすために消さなければならない面情報の個数を１行に出力する。

入出力例
入力例１

出力例１41 3 21 2 4
1 4 32 3 40

入力例２

出力例２61 3 2
1 2 4
1 4 32 3 4
3 2 1
2 3 12

入出力例２では、１つ目と５つ目と６つ目の面は頂点1, 3, 2を使って三角形を作っていて、点の順番が異なるだけなので重複している。つまり、重複した面のうち２つの面を消せば重複した面は無くなる。

問題６

パンケーキの焼き上がり（１０点）

あなたが勤めているパンケーキ屋では、細長い鉄板にパンケーキの生地を横１列に並べて焼きます。パンケーキはへらで何回か裏返せば完成します。何回以上裏返せば完成するかはパンケーキごとに異なります。
へらは大きいので、隣り合ったパンケーキは２枚同時に裏返されてしまいます。このとき、これら２枚の位置は入れ替わりません。ただし、両端だけは、隣のパンケーキといっしょに裏返すだけでなく、１枚だけ裏返すこともできます。すべてのパンケーキを必要な回数以上裏返したら、全部いっぺんに鉄板からおろして完成です。
パンケーキを必要な回数より多く裏返すと固くなってしまうので、あまり多く裏返したくありません。
そこであなたは、すべて完成するまでに、各パンケーキが裏返る回数の総和が最小になるような方法を見つけようと考えました。

課題
鉄板の上のパンケーキの枚数と、完成するまでに何回以上裏返さなければならないかがパンケーキごとに与えられているとき、すべて完成するまでに各パンケーキが裏返る回数（へらを操作する回数ではない）の総和の最小値を計算するプログラムを作成せよ。

入力
入力は複数のデータセットからなる。入力の終わりはゼロ１つの行で示される。各データセットは以下の形式で与えられる。
Np1 p2 … pN
１行目にパンケーキの枚数 N(3≦N≦5000)が与えられる。２行目に各パンケーキが完成するまでに必要な裏返す回数 pi(0≦pi≦3)が与えられる。
データセットの数は 100 を超えない。

出力
すべて完成するまでに各パンケーキが裏返る回数の総和の最小値を１行に出力する。

入出力例
入力例
31 2 130 3 00

出力例
46

入力例一番目のデータセットでは、へらを１回操作して左端と真ん中のパンケーキを裏返すと、２個のパンケーキが１回ずつ裏返るので、この操作で裏返る回数は２回。さらに、へらを１回操作して真ん中と右端のパンケーキを裏返すと、２個のパンケーキが１回ずつ裏返るので、この操作で裏返る回数は２回。以上の総和４回が答えになる。

入力例二番目のデータセットでは、へらを１回操作して左端と真ん中のパンケーキを裏返すと、この操作で裏返る回数は２回。これを３回繰り返したときの、総和の６回が答えになる（真ん中のパンケーキは、両隣のどちらかのパンケーキと一緒に裏返すことしかできないことに注意）。

問題７

イワシロ・イッツァ（１０点）

古代国家イワシロを発見し調査を進めた我々研究者は、ついにイワシロの中心部にある神殿、イワシロ・イッツァを発見した。伝承の通り、イワシロ・イッツァの最深部にはイワシロの神にささげた石版が保管されていた。全ての石版を調べた結果、必ず文章と呪文が一つずつ、合計２つの文字列が書かれていた。各文字列は左から右へ読む。
我々の説に従えば、イワシロでは呪文が文章の中に、何回現れるかが重要な意味を持つ。ただし、呪文に含まれるすべての文字が順番に、文章の中にとびとびで現れるものも１回現れていると考える。例えば、文章が“abab”で、呪文が“ab”であれば、連続でないものも含めて“ab”は“abab”の中に３回現われている（abab, abab, abab の３通り）。

課題文章と呪文が与えられたとき、呪文が文章の中に何回現れるかを出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
tb
１行目に、石版に書かれた文章を表す文字列tが与えられる。２行目に、石版に書かれた呪文を表す文字列bが与えられる。どちらの文字列も英小文字だけから成る、長さが1以上1000以下の文字列である。

出力
呪文が文章の中に何回現れるかを１行に出力する。ただし、出力すべき値は非常に大きくなりうるので、代わりに 1,000,000,007 で割った余りを出力する。

入出力例
入力例１

出力例１ababab3

入力例２

出力例２aaaabaaaabaaaabaaaab
aaaaa

4368

入力例３

出力例３

data
structure0

問題８ 村の道路計画（１４点）

アイヅ国のワカマツ平野に、集落が点在していました。いくつかの集落の間はまっすぐで互いに行き来できる道でつながっていて、ワカマツ平野にあるどの集落の間も道を辿って行き来ができます。それぞれの道には長さに応じた維持費がかかりますが、すべての集落が資金を出し合って道を維持していました。
あるとき、すべての集落が一つの村にまとまることが決まり、村を囲む境界線を引くことになりました。
アイヅ国の決まりでは、村を構成するどの２つの集落を結んだまっすぐな線も、村の外を通ってはいけません（境界線上を通ることは許されます）。さらに、アイヅ国では村を囲む境界線上に道がなければなりません。境界線上に道がない場所には、アイヅ国が新たに道を作ってくれます。
しかし、道の維持費は村が支払うので、村人達は境界線をできるだけ短くしたいと考えています。さらに、村人達はすべての集落の間を行き来できる状態を維持しつつ、境界線上にない道を廃止することで、道の長さの合計を最小にすることにしました。

課題
集落の位置と元々あった道の情報が与えられる。境界線上に道を置き、かつ、すべての集落が行き来できるようにした場合の、道の長さの合計の最小値を計算するプログラムを作成せよ。ただし、集落は大きさのない点、道は幅のない線分とする。

入力
入力は以下の形式で与えられる。
V R
x1 y1x2 y2:
xV yV
s1 t1
s2 t2:sR tR
１行目に集落の数V(3≦V≦100)と道の数R(2≦R≦1000)が与えられる。
続くV行に集落を表す点の情報が与えられる。各行に与えられる２つの整数xi,yi(-1000≦xi,yi≦1000)
は、それぞれi番目の集落のx座標、y座標を表す。
続くR行に元々あった道の情報が与えられる。各行に与えられる２つの整数si,ti(1≦si＜ti≦V)は、i番目の道がsi番目の集落とti番目の集落をつないでいることを表す。
入力は以下の条件を満たす。
i≠jならば、i番目の集落とj番目の集落の座標は異なる。



どの２つの集落についても、それらを直接結ぶ道は高々１つしか現れない。



２つの異なる道が端点以外の点を共有することはない。



３つ以上の集落が同一直線上に並んでいることはない。

出力
条件を満たす道の長さの合計の最小値を１行に実数で出力する。ただし、誤差がプラスマイナス 0.001を超えてはならない。この条件を満たせば小数点以下何桁表示してもよい。

入出力例
入力例 1出力例 15 50 0
1 13 03 20 2
1 22 32 43 4
1 511.4142

入力例 2出力例 27 60 23 02 21 04 12 33 5
1 32 42 33 5
3 7
6 718.2521

問題９プログラミングコンテスト II（１８点）

白虎大学では毎年プログラミングコンテストを開催しています。コンテストは全てのチームの得点が 0の状態から開始し、解答状況に応じて得点が加算されていきます。このコンテストでは、得点の高い順に順位付けが行われます。チームの総数を N としたとき、チームには 1 から N の番号がそれぞれ割り当てられています。得点が同じ場合は番号がより小さい方が上位になります。
白虎大学では、コンテストを盛り上げるために観戦用のランキングシステムを開発しています。開発チームの一員であるあなたは、このシステムの一部であるプログラムの作成を任されています。

課題
与えられた命令に従って、得点の更新と、指定された順位のチームの番号と得点を報告するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N C
command1
command2:
commandC
１行目にチーム数N(2≦N≦100000)と命令の数C(1≦C≦100000)が与えられる。続くC行に、１行ずつ命令が与えられる。各命令は以下の形式で与えられる。
0 t pまたは
1 m
最初の数字が0のとき更新命令、1のとき報告命令を表す。更新命令では指定された番号t(1≦t≦N)のチームに、整数で与えられる得点p(1≦p≦109)を加算する。報告命令では指定された順位m(1≦m≦N)のチームの番号と得点を報告する。ただし、報告命令は少なくとも１回現れるものとする。

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

出力各報告命令に対して、指定された順位のチームの番号と得点を空白区切りで１行に出力する。

入出力例
入力例１

出力例１3 110 2 50 1 50 3 41 11 21 30 3 2
1 10 2 11 21 31 52 53 43 63 61 5

入力例２出力例２5 2
1 11 2

1 02 0

問題１０

ゲームの攻略（２０点）

あなたは所属するプログラミング部の部室から古びたボードゲームを発見しました。面白そうなので遊んでみることにしました。
このゲームは M 個のイベントから成り、時刻 ti にイベント i を攻略しなければいけません。ただし、そのときにあなたの強さは si 以上である必要があり、si 以上にできない場合はゲームオーバーになります。
ゲーム開始時（時刻０）のあなたの強さは０ですが、アイテムを買うことで強さを増加させることができます。ゲーム開始時のあなたの所持金は０ですが、１単位時間あたり１増加します。
ボードにはそれぞれ１から N の番号が付けられた N 個のアイテムが順番に並べられており、アイテム iの値段は vi で、それを購入するとあなたの強さが hi 増加します。アイテムは所持金が十分であれば好きな時刻に好きな数だけ購入することができますが、残っているアイテムの中で番号が小さいものから順に選ばなければなりません。各アイテムは１度購入すると消滅します。
また、同じ時刻に複数のアイテムを連続で買うことができ、このとき隣り合うアイテムの hi の差分の和をボーナスとして得ることができます。例えば、ある時刻にアイテム１,２,３を同時に買った場合、h1 + h2+ h3 に加えて| h1 – h2 | + | h2 – h3 | だけあなたの強さが増加します。
あなたは、全てのイベントを攻略した後の所持金を最大化したいと考えています。

課題
アイテムの情報とイベントの情報を入力とし、すべてのイベントを攻略した後の所持金の最大値を出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N M
v1 h1
v2 h2:
vN hN
t1 s1t2 s2:
tM sM
１行目にアイテムの数 N(1≦N≦3000)とイベントの数 M(1≦M≦1000)が与えられる。続くN行にアイテ
ムiの値段viと強さの増加量hi(1≦vi,hi≦100000)が与えられる。続くM行にイベントiの時刻tiと条件si(1≦ti,si≦100000)が与えられる。ただし、i＜jのとき、ti＜tjとする。入力はすべて整数で与えられる。

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

出力
所持金の最大値を１行に出力する。ただし、攻略することができない場合には「-1」を出力する。

入出力例
入力例１

出力例１5 43 32 1
1 54 2
2 64 18 210 412 172

入力例２

出力例２5 43 32 1
1 54 2
2 64 18 2
10 4
12 30-1