Time Limit: 2 sec / Memory Limit: 256 MB
問題文
文字列 S と、非負整数 A, B, C, D が与えられます。
S の、A, B, C, D 文字目の後ろにダブルクオーテーション"を挿入した文字列を出力してください。
ただし、0 文字目の後ろというのは、文字列の先頭を指すこととします。
入力
入力は以下の形式で標準入力から与えられる。
S A B C D
- 1 行目には文字列 S(3 ≦ |S| ≦ 100) が与えられる。
- 2 行目には、非負整数 A, B, C, D(0 ≦ A < B < C < D ≦ |S|) が空白区切りで与えられる。
- |S| とは、S の長さである。
- S はすべて英字とアンダーバー(
_)からなる。
出力
ダブルクオーテーション"を挿入した文字列を出力する。
入力例1
MinnnahaNakayoshi 0 6 8 17
出力例1
"Minnna"ha"Nakayoshi"
入力例2
Niwawo_Kakemeguru_Chokudai 11 17 18 26
出力例2
Niwawo_Kake"meguru"_"Chokudai"
入力例3
___ 0 1 2 3
出力例3
"_"_"_"
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋ノルム君の可能性は無限大です。高橋ノルムという名前の人物はこの世界にたくさんいます。
2 次元平面上に N 人の高橋ノルム君がいます。i(1≦i≦N) 人目の高橋ノルム君は座標 (x_i,y_i) にいます。 各高橋ノルム君には正整数定数 c_i が割り当てられており、i 人目の高橋ノルム君がある点 (X,Y) に移動するためには c_i*max(\|x_i-X|,\|y_i-Y\|) の時間がかかります。
あなたの仕事は、全ての高橋ノルム君が一点に集まるために必要な最小の時間を求めることです。 ここで、一点に集まるために必要な最小の時間とは最も遅くその点に到着する高橋君の移動にかかった時間とします。
高橋ノルム君は一斉に動き出し、お互いに干渉せず動くものとします。
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 c_1 x_2 y_2 c_2 : x_N y_N c_N
- 1 行目には、高橋ノルム君の数を表す整数 N (2≦N≦1,000) が与えられる。
- 2 行目からの N 行のうち i (1≦i≦N) 行目には、i 人目の高橋君の二次元平面上の位置と定数を表す 3 つの整数 x_i,y_i,c_i (-10^5≦x_i,y_i≦10^5,1≦c_i≦1,000) が空白区切りで与えられる。
- 同じ座標に複数の高橋ノルム君がいることもあります。
部分点
この問題には部分点が設定されている。
- 任意の i(1≦i≦N) について、c_i=1 を満たすデータセットに正解した場合は、30 点が与えられる。
- 追加制約のないデータセットに正解した場合は、上記とは別に 70 点が与えられる。
出力
全ての高橋ノルム君が一点に集まるために必要な最小の時間を出力せよ。 絶対誤差または相対誤差が 10^{−4} 以下ならば正解となる。 出力の末尾には改行を入れること。
入力例 1
2 0 0 1 10 10 1
出力例 1
5.000000000000000
集合位置を (5,5) にすれば、5秒で2人ともその点に移動することができ、これが最小である。
入力例 2
2 0 0 1 10 10 2
出力例 2
6.666666666666667
入力例 3
10 -27 -67 10 59 13 10 14 -15 9 -29 -84 7 -75 -2 2 -12 -74 5 77 31 9 40 64 8 -81 32 1 81 26 5
出力例 3
582.222222222222222
入力例 4
8 -81739 73917 446 42230 30484 911 79354 -50126 200 33440 -47087 651 -73 84114 905 79222 -53608 713 65194 -46284 685 81145 40933 47
出力例 4
54924095.383189122374461
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は大会の上位入賞の特典として旅行に行ったときに、「ぬりまーす」という絵の具を買いました。
また、高橋君の手元には N 頂点の有向グラフがあり、グラフの各頂点は 頂点 1, 頂点 2, ..., 頂点 N と表されます。
高橋君は色を塗るのが大好きなので、その「ぬりまーす」を使い、手元の有向グラフの頂点に色を塗って遊ぼうと思っています。 ただし、適当に色を塗っても面白くないので、いくつかの頂点の間に以下のような制約がある条件下で色を塗ります。
- タイプ1: ある頂点 x に色を塗るとき、既に頂点 y に色が塗られてなければならない。
- タイプ2: ある頂点 u に色を塗るとき、既に頂点 v に色が塗られていてはいけない。
タイプ1の制約の個数は A 個で、タイプ2の制約の個数は B 個です。
最初はどの頂点にも色は塗られていません。 あなたの仕事は、適切な順番でグラフの頂点に色を塗り、最終的に色が塗られている最大の頂点数を求めることです。
入力
入力は以下の形式で標準入力から与えられる。
N A x_1 y_1 x_2 y_2 : x_A y_A B u_1 v_1 u_2 v_2 : u_B v_B
- 1 行目には、グラフの頂点の数を表す整数 N (1≦N≦100) が与えられる。
- 2 行目には、タイプ1の制約の個数を表す整数 A (0≦A≦100) が与えられる。
- 3 行目からの A 行には、タイプ1の制約の情報が与えられる。そのうち i (1≦i≦A) 行目には、「ある頂点 x_i に色を塗るとき、既に頂点 y_i に色が塗られてなければならない。」という制約を表す 2 つの整数 x_i,y_i(1≦x_i,y_i≦N,x_i≠y_i) が空白区切りで与えられる。
- 3+A 行目には、タイプ2の制約の個数を表す整数 B (0≦B≦10) が与えられる。
- 3+A+1 行目からの B 行には、タイプ2の制約の情報が与えられる。そのうち i (1≦i≦B) 行目には、「ある頂点 u_i に色を塗るとき、既に頂点 v_i に色が塗られていてはいけない。」という制約を表す 2 つの整数 u_i,v_i(1≦u_i,v_i≦N,u_i≠v_i) が空白区切りで与えられる。
- その制約の下では決して塗ることができない頂点が発生するような制約の組み合わせが与えられる可能性がある。また、複数同じ制約が与えられる可能性もある。
出力
最終的に色が塗られる頂点数の最大値を出力せよ。出力の末尾には改行を入れること。
入力例 1
3 2 1 2 2 3 1 3 1
出力例 1
3
頂点3→頂点2→頂点1の順に色を塗れば良いです。
入力例 2
3 2 1 2 2 3 1 1 3
出力例 2
2
この制約下では、頂点1を塗ることはできません。
入力例 3
3 3 1 2 2 3 3 1 0
出力例 3
0
この制約の下では、どの頂点にも色を塗ることはできません。
入力例 4
9 7 1 2 1 3 5 4 8 5 9 8 6 1 7 1 2 1 4 4 1
出力例 4
6
入力例 5
100 0 0
出力例 5
100
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は旅行先で、「すわっぷしまーす」という不思議な完全二分木を観光しました。
「すわっぷしまーす」は、高さが N+1 で葉の個数が 2^N の完全二分木です。そして、葉には左から順に 1, 2, 3, ..., 2^N と数が書かれています。
また、葉以外の頂点について、上から i 段目 (1 ≦ i ≦ N)、左から j 番目 (1 ≦ j ≦ 2^{i-1}) ならば位置 2^{i-1} + (j-1) となるように位置というものを定義します。
さらに、{\rm swap}(x) というものを定義します。これは、位置 x となる頂点を求め、左右の部分木を入れ替えるという動作です。
「すわっぷしまーす」は、以下の 2 種類のクエリを処理できます。
タイプ1: k(1 ≦ k ≦ 2^N) が与えられるので、左から k 番目の葉に書かれた数を求める。
タイプ2: a, b(1 ≦ a ≦ b ≦ 2^N - 1) が与えられるので、{\rm swap}(a), {\rm swap}(a+1), {\rm swap}(a+2), ..., {\rm swap}(b) と、この順番で実行する。
高橋君は、旅行から帰った後、自分でも「すわっぷしまーす」を作りたくなりました。しかしなかなか難しいので、あなたが代わりに作ることになりました。
具体的には、N と、Q 個のクエリが与えられるので、それを処理できるような「すわっぷしまーす」を作ってください。
入力
入力は以下の形式で標準入力から与えられる。
N Q t_1 a_1 b_1 t_2 a_2 b_2 : t_Q a_Q b_Q
- 1 行目には整数 N(1 ≦ N ≦ 17), Q(1 ≦ Q ≦ 200,000) が空白区切りで与えられる。
- 2 行目から Q 行には、クエリの内容が与えられる。そのうち i 行目には、3 つの整数 t_i, a_i, b_i が空白区切りで与えられる。
- t_i = 1 の時、タイプ1のクエリである。 a_i が問題文中の k を表し、b_i は必ず 0 である。
- t_i = 2 の時、タイプ2のクエリである。 a_i, b_i はそれぞれ問題文中の a, b を表す。
出力
タイプ1のクエリが来る度に、求めた値を出力する。出力する度に改行を入れる事。
入力例1
3 10 2 5 5 1 1 0 1 2 0 1 3 0 1 4 0 2 1 3 1 2 0 1 3 0 1 5 0 1 6 0
出力例1
1 2 4 3 8 5 4 3
このサンプルでは、2回タイプ2のクエリが来ます。
1回目のタイプ2のクエリの後は下図のようになっています。
2回目のタイプ2のクエリの後は下図のようになっています。
