問題１

椅子の総数

（３点）

選手のみなさん、パソコン甲子園にようこそ。パソコン甲子園の本選は会津大学で行われ、会場内では１つの机に１チームが割り当てられます。パソコン甲子園は１チーム２人なので、チーム数×２脚の椅子が必要です。大学では、他にも様々なイベントの会場設営で机と椅子を準備する機会がありますが、必要な机と椅子の数も様々です。そこで、あるイベントに対して準備する机の数と、机１つあたりに必要な椅子の数が与えられたとき、必要な椅子の総数を計算するプログラムを作成してください。

入力
入力は以下の形式で与えられる。
d c
入力は１行であり、必要な机の数d(1≦d≦100)と机１つあたりに必要な椅子の数c(1≦c≦10)を表す整数が与えられる。

出力
イベントにおいて必要な椅子の総数を１行に出力する。

入出力例
入力例１

出力例１20 240

入力例２

出力例２1 11

問題２

お財布メタボ診断（４点）

４月に消費税が８％になってから、お財布が硬貨でパンパンになっていませんか。同じ金額を持ち歩くなら硬貨の枚数を少なくしたいですよね。硬貨の合計が１０００円以上なら、硬貨をお札に両替して、お財布のメタボ状態を解消できます。
お財布の中の硬貨の枚数が種類ごとに与えられたとき、硬貨をお札に両替できるかどうかを判定するプ
ログラムを作成してください。

入力
入力は以下の形式で与えられる。
c1 c5 c10 c50 c100 c500
入力は１行からなる。c1、c5、c10、c50、c100、c500(0≦c1, c5, c10, c50, c100, c500≦50)は、それぞれ、1円、5円、10円、50円、100円、500円硬貨の枚数を表す。

出力
硬貨をお札に両替できるなら 1 を、そうでなければ 0 を１行に出力する。

入出力例
入力例１3 1 4 0 4 1
入力例２2 1 4 3 2 3
入力例３21 5 9 3 1 1
入力例４2 4 3 3 3 1
入力例５50 50 50 4 0 0

出力例１0
出力例２1
出力例３0
出力例４1
出力例５1

問題３

残り物には福がある（４点）

K 個の石から、P 人が順番に１つずつ石を取るゲームがあります。P 人目が石を取った時点で、まだ石が残っていれば、また１人目から順番に１つずつ石を取っていきます。このゲームでは、最後の石を取った人が勝ちとなります。K と P が与えられたとき、何人目が勝つか判定するプログラムを作成してください。

入力
入力は以下の形式で与えられる。
NK1 P1K2 P2:KN PN
１行目にはゲームを行う回数N(1≦N≦100)が与えられる。続くN行に、i回目のゲームにおける石の個数Ki(2≦Ki≦1000)と、ゲームに参加する人数Pi(2≦Pi≦1000)が与えられる。

出力それぞれのゲームについて、何人目が勝つかを１行に出力する。

入出力例
入力例
310 32 10
4 2

出力例122問題４路線バスの時刻表（５点）

バスマニアの健次郎君は、Ａ市内のバスをよく利用しています。ある日ふと、健次郎君の家の前のバス停から出発するすべてのバスを写真に収めることを思い立ちました。このバス停には飯盛山行きと鶴ケ城行きの２つのバス路線が通ります。各路線の時刻表は手に入れましたが、１つの時刻表としてまとめた方がバス停で写真が撮りやすくなります。
健次郎君を助けるために、２つの路線の時刻表を、０時０分を基準として出発時刻が早い順に１つの時刻表としてまとめるプログラムを作成してください。

入力
入力は以下の形式で与えられる。
N h1 m1 h2 m2 … hN mN
M k1 g1 k2 g2 … kM gM
１行目に、飯盛山行きのバスの数を表す整数N(1≦N≦100)と、それに続いて飯盛山行きのバス出発時刻が早い順に与えられる。出発時刻は整数hi(0≦hi≦23)とmi(0≦mi≦59)からなり、hi時mi分にi番目のバスが出発することを表す。２行目に、鶴ケ城行きのバスの数を表す整数M(1≦M≦100)と、それに続いて鶴ケ城行きのバス出発時刻が早い順に与えられる。出発時刻は整数ki(0≦ki≦23)とgi(0≦gi≦59)からなり、ki時gi分にi番目のバスが出発することを表す。
同じ路線には、同じ時刻に出発するバスはないものとする。

出力
２つの路線の時刻表を、０時０分を基準として出発時刻が早い順に１つにまとめた時刻表を１行に出力する。ただし、同じ時刻に複数のバスが出発するときは１つだけを出力する。出発時刻の時と分を:で区切る。分が１桁のときは左に０をひとつ加えて２桁で出力する。時刻と時刻の間は空白 1 つで区切る。

入出力例
入力例１2 9 8 15 59
1 8 27
入力例２2 0 0 21 0
3 7 30 21 0 23 7

出力例１8:27 9:08 15:59

出力例２0:00 7:30 21:00 23:07

問題５

鉄道路線 II（８点）

わたしの住む街には、図のようなN個の駅からなる円環状の鉄道路線があります。この路線の各駅には 0から N-1 までの番号が順番に割り当てられていて、隣の駅まで100 円で移動することができます。移動はどちらの方向にでも可能です。
わたしはこの路線上のいくつかの駅で買い物をしたいと思っています。
そこで、プログラムを作成して移動費を計算することにしました。
ある駅を始点として、買い物をするすべての駅を訪問する最小の費用（円）を求めるプログラムを作成してください。ただし、同じ駅を何度訪問しても良く、どのような順番で駅を訪問しても構いません。

入力
入力は以下の形式で与えられる。
N M pd1d2:dM
1行目に駅の数N(2≦N≦100000)、買い物をする駅の数M(1≦M≦10000 かつ M＜N)、出発する駅の番号p(0≦p≦N-1)が与えられる。続くM行に買い物をする駅の番号di(0≦di≦N-1)が与えられる。ただし、diは全て異なり、pもまたどのdiとも異なるものとする。

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

出力最小の費用を１行に出力する。

入出力例
入力例１5 4 01234
入力例２7 2 162

出力例１400

出力例２400問題６フロッピーキューブ（１０点）

フロッピーキューブをプログラミングで解いてみましょう。フロッピーキューブは図のように表面に色のついた９個の立方体から構成されている立体パズルで、キューブの列を回転させることによって、６つの各面の色をそろえます。

数手後

フロッピーキューブに対しては下図のような４種類の操作を行うことができ、一回の操作で、端にある３つの隣接したキューブを１８０度回転することができます。わかりやすいように、図では、上面に＋(赤色)、下面に＊(緑色)、右前面に□(黄色)、左前面に●(青色)、右奥面に○(水色)、左奥面に■(紫色)の記号が付いている状態を初期状態としています。

フロッピーキューブの初期状態が与えられるので、パズルを解くために必要な最小の操作回数を求めるプログラムを作成してください。

入力入力は以下の形式で与えられる。
Npuzzle1
puzzle2:puzzleN
１行目のN(1≦N≦30)は操作回数を計算したいパズルの数である。続くN行に各フロッピーキューブの初期状態puzzleiが与えられる。puzzleiは以下の形式で与えられる。
p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 p12 p13 p14 p15 p16 p17 p18 p19 p20 p21 p22 p23 p24 p25 p26 p27 p28 p29 p30
各フロッピーキューブの情報は30個の整数 pi(1≦pi≦6)からなる。piは、下図のようにフロッピーキューブの各面に番号iを振ったときの、そのキューブの面の色を表す。

パズルは、多くとも８回の操作で解くことができると仮定してよい。

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

出力
パズルごとに、最小の操作回数を１行に出力する。

入出力例
入力例
41 1 1 1 1 1 1 1 1 2 2 2 4 4 4 6 6 6 5 5 5 3
3 3 3 3 3 3 3 3
3 3 3 1 1 1 1 1 1 2 2 2 4 4 6 4 6 6 5 5 5 33 3 3 3 3 1 1 1
3 3 3 1 1 3 1 1 1 2 2 5 6 4 4 4 6 6 2 5 5 3
3 3 1 3 3 1 1 1
1 3 1 3 1 3 3 1 3 2 2 2 6 4 4 6 6 4 5 5 5 1
3 1 1 3 1 3 1 3

出力例
0127

※ 入力例で、各フロッピーキューブの初期状態におけるキューブの面の色を表す数列は、表示の都合上２行に見えるが、実際は１行である。

問題７バトンリレーゲーム（１２点）

アカベ高校では、毎年全校生徒が参加するゲームを行っています。まず、校庭に N 人の全校生徒が円形に並びます。図のように、各生徒は 0 から N-1までの番号が書かれたゼッケンを付けています。ゲームではバトンを１本使い、最初はゼッケン 0 番の生徒がバトンを持っています。
そこから、以下の手順を M 回繰り返します。まず、現時点でバトンを持っている生徒が適当な正の整数 a を宣言します。
a が偶数のときは時計回り、奇数のときは反時計回りに隣の生徒にバトンを渡していき、a 番目にバトンを受け取った生徒が脱落します。脱落した生徒は、時計回りで隣の生徒にバトンを渡し、円から抜けます。
ゲームが終わった後に円に残った生徒は、放課後の掃除が１年間免除されます。しかし、ここ数年は生徒数が増えたため、全校生徒を集めるのが難しくなってきています。そこで、競技プログラミング部のあなたは、シミュレーションで掃除が免除される生徒を求めるプログラムを作成するよう頼まれました。
指定した生徒が掃除を免除されているかどうかを質問したとき、それに答えるプログラムを作成してください。

入力入力は以下の形式で与えられる。
N M Q
a1 a2 … aM
q1 q2 … qQ
入力は３行であり、１行目に生徒の人数N(10≦N≦200000)、繰り返し回数M(5≦M＜N)、生徒が掃除を免除されるかどうかを問い合わせる質問の個数Q(1≦Q≦1000)が与えられる。続く１行に、i回目の繰り返しで最初にバトンを持っている生徒が宣言する整数ai(1≦ai≦100)が与えられる。続く１行に、質問としてゼッケン番号qi(0≦qi＜N)が与えられる。

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

出力
質問ごとに、ゼッケン番号 qi の生徒が掃除を免除されるかどうかを i 行目に出力する。掃除が免除されるなら 1 を、されないなら 0 を出力する。

入出力例
入力例
10 5 32 6 5 18 3
3 0 5

出力例
101

問題 ８

天体観測（１６点）

ある晴れた夜の帰り道、空を見上げるとそこには無数の星。強く輝く星々、かすかに見える星々、いろいろな明るさの星々が夜空を彩っています。
あなたはふと思いました。この星空に自分の星座があったらどんなに素敵だろうと。そこであなたはひとつの基準を決め、部屋の窓から見える星々を適当につなげて自分の星座を作ることにしました。その基準とは、「どの２つの星を選んでも、それらの明るさの差がある定数d以下になるような星のグループを作り、その中で一番大きいものを自分の星座にしよう！」というものです。例えば、図のような窓から見える夜空を考えてみましょう（外側の長方形は窓枠です）。

この夜空には、明るさがそれぞれ1，12, 2，4，1，8, 3，5，4の９つの星がありますが、d=2とすると例えば以下のような３つの星座A, B, Cができます。

大きさが12の星座A大きさが10の星座B大きさが16の星座C星座の大きさを次のように決めることにしました。ある星座の星をすべて含むような、窓枠に平行な辺からなる長方形のうち、面積が最も小さいものを選びます。この長方形の面積をその星座の大きさとします。例えば、上の夜空では星座A, B, Cの大きさはそれぞれ12, 10, 16になるので、星座Cが最も大きい星座となります。
N個の星の位置と明るさ、および整数dが与えられたとき、一番大きい星座の面積を求めるプログラムを作成してください。星の位置は窓枠の左下隅を原点とした座標で与えられ、軸は図のような向きとします。星座を構成する星が１つの場合や、星々が軸に平行な直線上にある場合は、その星座の面積は0となることに注意してください。

入力
入力は以下の形式で与えられる。
N d
x1 y1 b1x2 y2 b2:xN yN bN
1行目に星の数 N(1≦N≦200000)と整数d(0≦d≦109)が与えられる。続くN行に、i 番目の星の座標を表す整数xi(0≦xi≦2000000)とyi(0≦yi≦2000000)、明るさを表す整数bi(0≦bi≦109)が与えられる。入力
される星の座標はすべて異なる。

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

出力一番大きい星座の面積を１行に出力する。

入出力例
入力例
9 21 1 1
1 5 122 3 23 2 44 4 1
5 1 3
5 3 86 5 57 2 4

出力例
16問題９ 力持ち（１８点）

力持ちたちが集う力持ち学園がありました。力持ち学園の運動会では、力持ちたちが隊列を組んで行進します。
力持ちたちは常に自分たちの力を誇示したい一方で、彼らの大半は自分で歩きたくありません。そこで彼らの一部が一番下になり、その上に大勢の人を縦一列に持ちあげて歩くことで、実際に歩く人数を減らそうと考えました。
はじめに、N 人の力持ちは地面の上に横一列に並んでいて、それぞれ左側から１,２,３,…,N と通し番号で呼ばれています。通し番号 i の力持ちの体重は wi で最大 ci の重量まで持つことができます。
力持ちは、以下の条件をすべて満たすときだけ、隣に立っている左右どちらかの力持ちを持ちあげることができます。


自分の上下には力持ちはいない。つまり、誰かに持ち上げられてもいないし、誰かを持ちあげてもいない。



隣の力持ちの体重が、自分が持つことのできる最大の重量以下である。ただし、隣の力持ちが既に誰かを持ち上げているなら、縦に積み上がった力持ちたちの体重の合計が、自分が持つことのできる最大の重量以下でなければならない。

例えば、右のような３人の力持ちの隊列を考えてみましょう。
下図のように、２の力持ちが持つことのできる重さが w3 以上のとき、２の力持ちは３の力持ちを持ちあげることができます。続いて、１の力持ちが持つことのできる重さが w2 + w3 以上のとき、１の力持ちは２の力持ちを持ちあげることができます。

また、下図のように３の力持ちが２の力持ちを持ちあげた場合は、１の力持ちの隣が、２の力持ちを持った３の力持ちになるので、１の力持ちは３の力持ちを持ちあげることができます。

２の力持ちが、下の図のように１と３の力持ちを両方持つことはできません。

力持ち学園の専属プログラマーとして、一番下で歩くことになる最小の人数を求めてください。

入力
入力は以下の形式で与えられる。
N
c1 w1
c2 w2
:
cN wN
1行目に力持ちの人数 N(1≦N≦1000)が与えられる。続くN行にi番目の力持ちが持てる重量の最大値ci(1≦ci≦100000)と体重wi(1≦wi≦100000)が与えられる。

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

出力最小の人数を１行に出力する。

入出力例
入力例１3150 120
100 5080 100
入力例２850 100
20 2030 2090 50
140 3030 6059 12010 10

出力例１1

出力例２3

問題 １０学食（２０点）

今日はＺ大学のオープンキャンパスです。毎年この日の昼休みには、大勢の高校生たちが学食に列をつくります。そこでＺ大学の事務局は、行列の長さが最大でどのくらいの距離になるかを予測することにしました。
事前調査の結果で、以下のことが分かっています。
行列にはそれぞれ1からNまでの番号が振られたN人が並びます。



C 個の高校生のペア(ai,bi)それぞれについて、以下の２種類の制約があります：

１つ目の制約は順序に関するもので以下のいずれかです：

aiはbiよりも先、または同じ位置に並ばなくてはならない

aiはbiよりも後、または同じ位置に並ばなくてはならない

aiはbiより先でも、同じ位置でも、後でもよい

２つ目の制約は距離に関するもので以下のいずれかです：
aiとbiはdiメートル以上離れなければならない

aiとbiはdiメートル以内に並ばなければならない

また、先頭から同じ距離の場所に複数の人が並ぶことができ、行列の先頭には常に番号1の人が並ぶことが分かっています。
与えられたC個の制約をすべて満たす行列について、先頭から最後尾までの距離が最大となるような並び方をした場合の距離を求めるプログラムを作成してください。ただし、どこまでも離れることができる場合は“inf”と、制約を満たす並び方が不可能な場合は“-1”と出力してください。

入力
入力は以下の形式で与えられる。
N C
constraint1
constraint2:
constraintC
1 行目に行列に並ぶ高校生の人数 N(2≦N≦100)と制約の数 C(0≦C≦200)が与えられる。続く C 行に各制
約 constrainti が次の形式で与えられる。
aioibisidi
制約には空白は含まれない。ai,oi,bi,si,di の意味を以下に示す。
ai と bi(1≦ai,bi≦N かつ ai≠bi)は高校生の番号、di は距離(0≦d≦10000)を表す整数である。

oi は順序の制約を指定する<=、>=、*のいずれかの文字列であり、<=の場合「ai は bi よりも先、または同じ位置に並ばなくてはならない」、>=の場合「ai は bi よりも後、または同じ位置に並ばなくてはならない」、*の場合「ai は bi より先でも、同じ位置でも、後でもよい」ことを意味する。ただし oi が*となる制約は７個以上与えられることはない。

si は距離の制約を指定する+または–の文字であり、+の場合「ai と bi は di メートル以上離れなければならない」、-の場合「ai と bi は di メートル以内に並ばなければならない」ことを意味する。

ただし、あるペアに対して複数の制約が与えられることはないものとする。

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

出力
先頭から最後尾までの距離を１行に出力する。

入出力例
入力例１3 2
1<=2-12<=3-2
入力例２3 3
1<=2-1
2<=3-2
1<=3+4
入力例３3 2
1<=2-2
2*3+1

出力例１3

出力例２-1

出力例３inf