A - 成績判定
あなたはある試験の採点者です。
この試験ではいくつかの科目が存在し、その科目のうち、既定の数の科目に合格すると、試験に合格できます。
この試験では合格人数が初めからきめられているため、科目の合格点を採点結果を見て調整しなければなりません。
調整は面倒なので、採点結果を入力すると合格点を表示するプログラムを作ることにしました。また、科目ごとに調整するのは面倒なので、すべておなじです。
合格人数が最低合格人数以上になる、最大の合格点を出力してください。
ある科目で合格するとは、獲得した点数が、合格点以上になることとします。
入力は以下の形式で与えられる。
入力中は各変数はすべて整数である。また、以下の制約を満たす。
調整した点数を整数1行で出力してください
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
入力
A B C D E_{(0,0)} ・・・・E_{(0,A-1)} ・ ・ ・ ・ E_{(C-1,0)} ・・・・E_{(C-1,A-1)}科目数A、 合格に必要な科目数B、 人数C、 最低合格人数D、 また得点の表E_{(i,j)} E_{(i,j)}はi番目の人の、j番目の科目についての得点である。
制約
- 2≦A,C≦10
- 1≦B≦A
- 1≦D≦C
- 0≦E_{(i,j)}≦100
出力
入力例 1
4 3 3 2 10 15 25 30 5 20 20 30 40 100 100 100
出力例 1
20
B - 元素の系統名
原子番号を与える.それに対応する「元素の系統名(げんそのけいとうめい)」を出力せよ.
「元素の系統名」とは、原子番号の各位を、以下の表にしたがって綴ったものである。
また、一文字目は大文字で表記する。
あなたの仕事は元素番号が117番以降の3桁の元素の名前をつけることである。
*印が付いている表記について 注意が必要である
"bi"または"tri"が"ium"と連結する場合は連続する"ii"は"i"と表記する。"enn"が"nil"または"nilium"と連結する場合は連続する"(e)nn"は"(e)n"と表記する
入力は以下の形式で与えられる。
入力中は各変数はすべて整数である。また、以下の制約を満たす。
元素の系統名(げんそのけいとうめい)を一行で出力してください
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
数字 | 綴り(1の位以外) | 綴り(1の位) |
0 | nil | nilium |
1 | un | unium |
2 | bi | bium * |
3 | tri | trium * |
4 | quad | quadium |
5 | pent | pentium |
6 | hex | hexium |
7 | sept | septium |
8 | oct | octium |
9 | enn * | ennium |
入力
NNは原子番号である。
制約
- 117≦N≦999
出力
入力例 1
145
出力例 1
Unquadpentium
入力例 2
902
出力例 2
Ennilbium
Source Name
元素の系統名(wikipedia)
C - 案内所
あなたが街を歩いていると、通りすがりの人が、目的地がわからないので教えてほしいと頼んできました。
答えていると、周りには目的地がわからない人がたくさんいるようですが、周りの人たちはとてもうるさいので、他の人が聞いた質問とその答えは全く聞いていないようです。
何度も同じ問いかけがくるのであなたはうんざりしてしまいました。なかにはこの街にない目的地を聞いてくる人もいます。
周りの人に目的地の住所を教えてあげるプログラムを作成してください。目的地が存在しない場合は"NA"と出力してください。
入力は以下の形式で与えられる。
入力は以下の制約を満たす。
入力は以下の制約を満たす。
各q_iについて、s_{(x,y)}=q_iを満たすx,yを、空白区切りで一行に出力してください。
目的地が存在しない場合は"NA"と出力してください。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
入力
N M Q s_{(1,1)} s_{(1,2)} … s_{(1,M)} s_{(2,1)} s_{(2,2)} … s_{(2,M)} ・ ・ s_{(N,1)} s_{(N,2)} … s_{(N,M)} q_{1} ・ ・ q_{Q}N*Mのマップがあり、マップの要素はS(i,j)で表されます。 また、q(i)はそれぞれの問いかけです
制約 1
- 1≦N,M≦100
- 1≦Q≦100 s_{(i,j)}について、アルファベットの大文字、または'*'。また、アルファベットの大文字は各文字1回以下しか出現しない。 q_iについて、アルファベットの大文字
制約 2
- 1≦N,M≦1000
- 1≦Q≦3000 s_{(i,j)}について、アルファベットの大文字、または'*'。また、アルファベットの大文字は各文字1回以下しか出現しない。 q_iについて、アルファベットの大文字
出力
入力例 1
3 7 3 ***A*** **B**** ******C A B C
出力例 1
1 4 2 3 3 7
入力例 2
3 7 3 ***A*** **B**** ******C D Z Y
出力例 2
NA NA NA
-
この人たちは別の町を目指していたようです。
D - 切符分割
QU鉄道は、N個の駅とM個の路線を持つ鉄道会社である。
それぞれの駅には、0からN-1までの一意な駅番号が割り当てられている。
各路線は異なる2つの駅を結んでおり、どちらの方向の移動にも使うことができる。
また、QU鉄道では運賃表を使用しており、距離に応じて段階的に運賃が変わるようになっている。
ある駅Aから別の駅Bまでの切符の料金は、駅Aから駅Bまでの最短距離を元に、運賃表から決定する。
例えば、次のような路線図と運賃表を考えよう。
この例において、駅0から駅6までの運賃を考えよう。
駅0から駅6までの距離は合計で41kmであるから、 運賃表より、駅0から駅6までの切符は740円となる。
QU鉄道では、区間の異なる複数の切符を使って、ある駅から別の駅へ移動することもできる。
これを切符分割と呼ぶことにする。
例えば、次の2つの切符を持っていれば、駅0から駅6まで移動することができる。
このように、QU鉄道では、切符分割により運賃が安くなる場合が存在する。
さらに、次のように3枚の切符を使って、駅0から駅6まで移動する場合を考える。
倹約家の胡桃さんは、このような切符分割をうまく使うことで、交通費を節約しようと考えた。
胡桃さんは、駅Sから駅Gへ行きたいが、もし可能であれば、切符分割により運賃を安く済ませたい。
しかしながら、切符を何枚も買うのは、胡桃さんにとって面倒である。
そこで胡桃さんは、最大2枚の切符を使って、駅Sから駅Gへ移動しようと考えた。
したがって、上記の例において、胡桃さんが駅0から駅6まで移動する場合には、710円が必要となる。
あなたの仕事は、胡桃さんが駅Sから駅Gへ移動するために必要な交通費の最小値を求めることである。
入力は以下の形式で与えられる。
入力中の各変数はすべて整数である。また、以下の制約を満たす。
切符を最大2枚購入するときの、駅Sから駅Gへの運賃の合計の最小値を、1行に出力せよ。出力の末尾には改行を入れなければならない。
以下の3つの制約を満たすテストケースに正答すると、20点を得ることができる。
以下の2つの制約を満たすテストケースに正答すると、20点を得ることができる。
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
それぞれの駅には、0からN-1までの一意な駅番号が割り当てられている。
各路線は異なる2つの駅を結んでおり、どちらの方向の移動にも使うことができる。
また、QU鉄道では運賃表を使用しており、距離に応じて段階的に運賃が変わるようになっている。
ある駅Aから別の駅Bまでの切符の料金は、駅Aから駅Bまでの最短距離を元に、運賃表から決定する。
例えば、次のような路線図と運賃表を考えよう。
距離 | 運賃 |
---|---|
1 km - 6 km | 180 円 |
7 km - 15 km | 230 円 |
16 km - 25 km | 400 円 |
26 km - 40 km | 530 円 |
41 km - 60 km | 740 円 |
61 km以上 | 820 円 |
この例において、駅0から駅6までの運賃を考えよう。
駅0から駅6までの距離は合計で41kmであるから、 運賃表より、駅0から駅6までの切符は740円となる。
QU鉄道では、区間の異なる複数の切符を使って、ある駅から別の駅へ移動することもできる。
これを切符分割と呼ぶことにする。
例えば、次の2つの切符を持っていれば、駅0から駅6まで移動することができる。
- 駅0から駅1までの切符: 6km、180円
- 駅1から駅6までの切符: 35km、530円
このように、QU鉄道では、切符分割により運賃が安くなる場合が存在する。
さらに、次のように3枚の切符を使って、駅0から駅6まで移動する場合を考える。
- 駅0から駅2までの切符: 13km、230円
- 駅2から駅4までの切符: 14km、230円
- 駅4から駅6までの切符: 14km、230円
倹約家の胡桃さんは、このような切符分割をうまく使うことで、交通費を節約しようと考えた。
胡桃さんは、駅Sから駅Gへ行きたいが、もし可能であれば、切符分割により運賃を安く済ませたい。
しかしながら、切符を何枚も買うのは、胡桃さんにとって面倒である。
そこで胡桃さんは、最大2枚の切符を使って、駅Sから駅Gへ移動しようと考えた。
したがって、上記の例において、胡桃さんが駅0から駅6まで移動する場合には、710円が必要となる。
あなたの仕事は、胡桃さんが駅Sから駅Gへ移動するために必要な交通費の最小値を求めることである。
入力
N M K S G a_0 b_0 d_0 a_1 b_1 d_1 : a_{M-1} b_{M-1} d_{M-1} x_0 f_0 x_1 f_1 : x_{K-1} f_{K-1}
- 1行目には、駅の数N、路線の数M、運賃表のサイズKが与えられる。
- 2行目には、出発駅の番号S、到着駅の番号Gが与えられる。
- 3行目からM+2行目には、路線の情報が与えられる。各行は、駅a_iとb_iを結ぶ、距離d_iの路線が存在することを表す。
- M+3行目からM+K+2行目には、運賃表の情報が与えられる。任意のj\ (0≦j<K)および距離l\ (l≧1)について、x_j≦l<x_{j+1}を満たすならば、距離lに対する運賃がf_jであることを表す。ただし、x_Kは無限大であると仮定する。
制約
- 2≦N≦30000
- 1≦M≦60000
- 1≦K≦100
- 0≦S<N
- 0≦G<N
- S≠G
- 任意の0≦i<Mに対し、0≦a_i<N,\ 0≦b_i<N,\ a_i≠b_i
- 任意の0≦i<j<Mに対し、\{a_i,b_i\}≠\{a_j,b_j\}
- 任意の0≦i<Mに対し、1≦d_i≦10^4
- 1=x_0<x_1<...<x_{K-1}≦10^9
- 1≦f_0<f_1<...<f_{K-1}≦10^9
- 駅Sから駅Gへの経路が存在する
出力
部分点 1
- 2≦N≦100
- 1≦M≦200
- 切符分割により交通費が安くなることはない。 すなわち、駅Sから駅Gまでの切符1枚のみを購入するのが最適となる。
部分点 2
- 2≦N≦100
- 1≦M≦200
入力例 1
7 6 6 0 6 0 1 6 1 2 7 2 3 6 3 4 8 4 5 5 5 6 9 1 180 7 230 16 400 26 530 41 740 61 820
出力例 1
710
- 問題文中に示した通りである。
入力例 2
7 6 6 4 1 0 1 6 1 2 7 2 3 6 3 4 8 4 5 5 5 6 9 1 180 7 230 16 400 26 530 41 740 61 820
出力例 2
400
- 入力例1と路線および運賃表は同じであるが、出発駅および到着駅が異なる。この場合は、駅4から1までの切符をそのまま買ったほうが良い。
入力例 3
5 5 4 0 4 0 1 2 1 2 3 2 4 5 1 3 8 3 4 6 1 100 4 200 9 400 16 600
出力例 3
300
- ある駅から別の駅への経路は、複数存在することもある。
入力例 4
2 1 2 0 1 0 1 3 1 100 3 210
出力例 3
210
E - 捕獲
QU動物園の飼育員である胡桃さんの元に、一匹の猿が檻から脱走したという連絡が入った。
捕獲のプロである胡桃さんは、その猿を捕まえることにした。
猿は時刻t=0において座標(x_0,y_0)におり、また、x軸方向にv_x(m/s)、y軸方向にv_y(m/s)の速度で直進している。
すなわち、時刻t\ (t≧0)において、猿のいる座標は(x_0+v_xt,\ y_0+v_yt)である。
一方、胡桃さんは時刻t=0において原点におり、また、胡桃さんは任意の方向にv_h(m/s)の速さで走ることができる。
胡桃さんは捕獲のプロであるから、猿の捕獲は一瞬で完了する。すなわち、胡桃さんと猿が同一の座標に存在した時点で、捕獲が完了するとみなしてよい。
あなたの仕事は、胡桃さんが猿を捕獲できる時刻の最小値を求めることである。
なお、QU動物園は無限に広く、かつ、障害物はないものとする。
したがって、猿は無限に直進し続けることができ、また、胡桃さんは平面上を自由に動くことができる。
入力は以下の形式で与えられる。
入力中の各変数はすべて整数である。また、以下の制約を満たす。
胡桃さんがどのように走っても猿を捕獲することができないならば、"IMPOSSIBLE"と出力せよ。
胡桃さんが猿を捕獲することができるならば、その時刻の最小値を出力せよ。出力と真の値との絶対誤差・相対誤差の少なくともいずれか一方が、10^{-6}以下でなければならない。
いずれの場合も、出力は1行であり、出力の末尾には改行を入れなければならない。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
捕獲のプロである胡桃さんは、その猿を捕まえることにした。
猿は時刻t=0において座標(x_0,y_0)におり、また、x軸方向にv_x(m/s)、y軸方向にv_y(m/s)の速度で直進している。
すなわち、時刻t\ (t≧0)において、猿のいる座標は(x_0+v_xt,\ y_0+v_yt)である。
一方、胡桃さんは時刻t=0において原点におり、また、胡桃さんは任意の方向にv_h(m/s)の速さで走ることができる。
胡桃さんは捕獲のプロであるから、猿の捕獲は一瞬で完了する。すなわち、胡桃さんと猿が同一の座標に存在した時点で、捕獲が完了するとみなしてよい。
あなたの仕事は、胡桃さんが猿を捕獲できる時刻の最小値を求めることである。
なお、QU動物園は無限に広く、かつ、障害物はないものとする。
したがって、猿は無限に直進し続けることができ、また、胡桃さんは平面上を自由に動くことができる。
入力
x_0 y_0 v_x v_y v_h
制約
- -100≦x_0≦100
- -100≦y_0≦100
- -100≦v_x≦100
- -100≦v_y≦100
- 1≦v_h≦100
- v_hが±10^{-9}変化しても、 元の値との絶対誤差・相対誤差の少なくともいずれか一方は2×10^{-7}以下であり、 また、捕獲可能性が変化することもない。
出力
胡桃さんが猿を捕獲することができるならば、その時刻の最小値を出力せよ。出力と真の値との絶対誤差・相対誤差の少なくともいずれか一方が、10^{-6}以下でなければならない。
いずれの場合も、出力は1行であり、出力の末尾には改行を入れなければならない。
入力例 1
3 0 -2 0 4
出力例 1
0.5
- 座標(2,0)で猿を捕獲することができる。
入力例 2
3 0 2 0 1
出力例 2
IMPOSSIBLE
- 胡桃さんがどれだけ走っても、猿に追い付くことはできない。
入力例 3
2 1 2 3 4
出力例 3
5
F - 設備移転
あなたの通っている大学は、大学の設備を移転しようとしている。
それぞれの設備などが移転するのにかかる時間が与えられる。
大学にはN個の設備が存在します。
時間Tまでに移動できる設備の組み合わせのパターン数を1000000009で割ったあまりを求めてください。
ただしそれぞれのパターンは設備は少なくともM個移動しなければならないという制約を満たしてください。
入力は以下の形式で与えられる。
入力中は各変数はすべて整数である。また、以下の制約を満たす。
パターン数を1000000009で割ったあまりを整数1行で出力してください
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
入力
N T M D_0 ・・・・ D_{N-1}D_iはi番目の設備が移動するのにかかる時間です。
制約
- 1≦N≦100
- 1≦T≦10000
- 0≦M≦N
- 1≦D_i≦100
出力
部分点
M=0であるいくつかのテストケースに正答すると、 60点を得ることができる。入力例 1
3 100 1 1 2 3
出力例 1
7
入力例 2
10 3 2 1 1 1 1 1 1 1 1 1 1
出力例 2
165
G - 立ち入り禁止区域
あなたは警官である
あなたの担当する地区では、区画がいくつかの種類で分類されており、すべての区画は長方形であり、軸と平行である。
ある日、テロの予告が来た。
テロは生活区画のみを対象としている。
爆弾の爆発の影響のある範囲は円形である。
同僚の警察官は優秀なので、すべての爆弾の設置場所と爆発の威力はわかっている。
しかし、時間が足りないので、爆弾を解除することはできない。
市民を逃がすために立ち入り禁止区域を設定する。
立ち入り禁止区域は爆弾の爆破範囲と重なっている生活区域を含む一つの領域とする。
爆弾の威力は多少ぶれる可能性があるため、爆弾の爆破範囲と生活区域が接している場合も、その生活区域は立ち入り禁止区域に含まれなければならない。
あなたの仕事は、立ち入り禁止区域を表示するための機材を用意することである。
爆弾は全て同時に爆発することがわかっており、立ち入り禁止区域を表示する機材は使い捨てのため、機材が爆発に巻き込まれて壊れてしまっても、問題ない。
機材は外周の長さによって使う数がきまっているため、外周の長さを最小にしたい。
立ち入り禁止区域の外周の長さが最小になる時の、外周の長さを求めよ。
入力は以下の形式で与えられる。
N 、 区画の数 M 、
爆弾の位置( Cx ,Cy )、と爆破半径Cr
また、各生活区画について、左下の頂点(Bx , By )と、左右の長さBw 、上下の長さBh があたえられる。
入力中は各変数はすべて整数である。また、以下の制約を満たす。
以下の制約を満たすケースに正答すると、80点を得ることができる。
立ち入り禁止区域の外周の長さlを一行で出力してください
出力の絶対誤差は10^{-3}以下にしてください。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
入力
N M Cx_0 Cy_0 Cr_0 ・ ・ Cx_{N-1} Cy_{N-1} Cr_{N-1} Bx_0 By_0 Bw_0 Bh_0 ・ ・ Bx_{M-1} By_{M-1} Bw_{M-1} Bh_{M-1}街について、左右をx軸、上下をy軸として、上と右を正の方向として表記する。 爆弾の数
制約
- 1≦N≦100
- 1≦M≦100
- -10000≦Cx_i,Cy_i,Bx_i,By_i≦10000
- 1≦Cr_i,Bh_i,Bw_i≦1000
部分点
- N=1
- M=1
- -100≦Cx_i,Cy_i,Bx_i,By_i≦100
- 1≦Cr_i,Bh_i,Bw_i≦100
出力
入力例 1
1 1 1 1 1 2 0 2 2
出力例 1
8
入力例 2
1 2 2 3 2 2 0 2 2 1 3 1 1
出力例 2
11.9907
入力例 3
1 2 1 3 1 0 0 3 2 1 5 2 2
出力例 3
10
H - お風呂は気持ちいい
この世界では魔法使いは、魔導石から魔力をもらって魔法をつかい、M人の魔法使いが存在します。
魔力は人から人へと渡すことができますが、人同士で相性があり、受け渡しの得手不得手もあるので、渡せる量は決まっています。
魔導石からは無制限に魔力が湧き出てくるので、魔導石の近くならばどんな魔法でも使うことができ、いくらでも魔力を得ることができます。
また、魔法使いは魔力を蓄積することはできません。
アスナさんは、お風呂に入りたいのですが、お風呂を沸かすためには魔力が必要です。
あいにく残念なことに、アスナさんの家は魔導石からは離れています。
他の人は気前よく魔力をくれるので、他の人に魔力を経由してもらうことにしましたが、どのぐらい魔力が得られるのかがわかりません。
経由できるルートと、使いたい魔法に必要な魔力が与えられるので、お風呂を沸かせるならば"Yes"そうでないならば"No"と出力してください。
N個のルートと、魔法使いの人数M、お風呂を沸かすのに必要な魔力P、魔導石に近いところにいる魔法使いの人数G、及び、魔導石に近いところにいる魔法使いのリストと、魔法使いの間の魔力の受け渡しのルートのリストが与えられます。
魔法使いはそれぞれ番号が割り振られており、アスナさんの番号は0です。
また、各魔法使いxについて,xが渡せる魔力の総量は,xが受け取った魔力の総量以下です。
入力は以下の形式で与えられます。
入力中は各変数はすべて整数である。また、以下の制約を満たす。
上記の制約に、
from_i - 1 = to_i
を加えたテストケースいくつかに正答すると40点を獲得できる。
アスナさんが受け取れる魔力が、お風呂を沸かすのに必要な魔力以上ならば"Yes"、そうでないならば"No"と一行で出力してください。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
入力
N M P G L_0 ・・・ L_{G-1} from_0 to_0 cap_0 ・ ・ ・ ・ from_{N-1} to_{N-1} cap_{N-1}L_0 ・・・ L_{G-1}は、それぞれ魔導石に近いところにいる魔法使いの番号です。 from_i、to_i、 cap_iは、それぞれ、from_i番の魔法使いが、to_i番の魔法使いに渡せる魔力が、最大でcap_iであることを示します。
制約
- 1≦N≦500
- 1≦M≦100
- 0≦G≦10
- 0≦P≦1000
- 0≦from_i,to_i<M
- 1≦cap_i≦1000
- i≠jの時、L_i ≠ L_jである。 また全てのiについてL_i≠0である。
- 全てのiについて、from_i≠to_iである。
- 任意の0≦i<j<Nに対し、(from_i,to_i)≠(from_j,to_j)
部分点
出力
入力例 1
1 2 100 1 1 1 0 200
出力例 1
Yes
入力例 2
1 3 100 1 1 2 1 200
出力例 2
No
入力例 3
4 5 100 2 3 4 1 0 200 2 1 50 3 2 100 4 2 100
出力例 3
No