Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
関数 f を以下のように定義します。
f(n) = {\rm floor}((n^2 + 4.0) / 8.0)
※ {\rm floor}(x) は与えられた実数 x 以下の最大の整数を返す関数です。
アイバくんは関数 f を整数に何度か適用して遊んでいます。例えば、
f(10) = 13
f(f(10)) = 21
f(f(f(10))) = 55
となります。
アイバくんは急に f(f(f(20))) が必要になりました。
アイバくんの代わりに f(f(f(20))) を求めてください。
入力
この問題では入力は与えられない。
出力
f(f(f(20))) の値を出力せよ。出力の末尾に改行を入れること。
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
天下一魔力発電所は不思議な魔術で電気を生み出すことができる発電所です。
魔力発電に用いる燃料は以下の様な文字列 S です。
S は ( と ) で構成されており、S の文字数は偶数です。
天下一ワープロでこの文字列を対応の取れた文字列に書き換えることで魔力発電に成功します。
対応が取れた文字列とは、以下の文字列です。
()は対応が取れた文字列である。Tが対応が取れた文字列であるとき、(T)も対応が取れた文字列である。T,Uが対応が取れた文字列であるとき、TUも対応が取れた文字列である。
天下一ワープロには以下 4 通りの操作があります。
はじめはカーソルは S の先頭の文字を指します。
- カーソルを右に動かす（カーソルが末尾の文字を指す場合は動かない）
- カーソルを左に動かす（カーソルが先頭の文字を指す場合は動かない）
- カーソルが指す文字が
(のとき、その文字を)に変更する - カーソルが指す文字が
)のとき、その文字を(に変更する
たとえば S が次の文字列の場合、
())(()))
1, 4 と操作を行うことで
(()(()))
という対応が取れた文字列にすることができます。
発電所の責任者であるフデくんは最も少ない操作回数で文字列を対応が取れた文字列に書き換えたいです。
S が与えられるので、対応の取れた文字列に書き換える最も少ない操作回数を求めてください。
制約
- S の文字数 |S| は偶数
- 2 \leq |S| \leq 100
入力
入力は以下の形式で標準入力から与えられる。
S
出力
対応の取れた文字列に書き換える最も少ない操作回数を出力せよ。出力の末尾に改行を入れること。
入力例 1
())(()))
出力例 1
2
問題文中に登場したケースです。
入力例 2
((((
出力例 2
5
1, 1, 3, 1, 3 と操作することで対応のとれた文字列になります。
入力例 3
)))(((
出力例 3
9
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 600 点
問題文
天下一プログラマーコンテスト1999本戦では N 人の参加者が総当り戦を行い、総当り戦の結果と予選の順位によって本戦の順位を付けました。
本戦では、総当り戦で勝った数によって順位を付け、総当り戦で勝った数が同じ場合は、予選の順位が高いほうが上位になるものとしました。
予選順位が同じ参加者はいないものとします。
アンドウくんとハシモトくんは総当り戦の対戦記録を付けていて、各対戦について、それぞれが「XさんがYさんに勝った」と「YさんがXさんに負けた」という 2 つの記録を付けます。
アンドウくんは記録を間違えることはありません。
アンドウくんが「予選順位 i 位の人が予選順位 j 位の人に勝った」と記録している場合 A_{i,j} = 1 であり、そうでない場合 A_{i,j} = 0 です。
しかし、ハシモトくんがある 1 つの記録を正しく付けることができる確率は P = p / q であり、確率 1-P で勝敗を間違えてしまいます。
各記録は独立事象であるものとします。
例えば、ある対戦について、確率 (1-P)^2 で勝敗を逆に記録してしまったり、確率 P(1-P) で両方勝ったと記録してしまったりします。
対戦記録からXさんが総当り戦で勝った数を求めるときは「Xさんが誰かに勝った」という記録がいくつあるかで定めるものとします。
アンドウくんが付けた対戦記録から求められる順位とハシモトくんが付けた対戦記録から求められる順位が一致する確率を求めてください。
制約
- 2 \leq N \leq 30
- 0 \leq p \leq q
- 1 \leq q \leq 10
- A_{i,j} \in \{ 0, 1 \}
- A_{i,i} = 0
- i \neq j ならば A_{i,j} + A_{j,i} = 1
- N, p, q は整数である
入力
入力は以下の形式で標準入力から与えられる。
N p/q
A_{1,1} A_{1,2} … A_{1,N}
A_{2,1} A_{2,2} … A_{2,N}
:
A_{N,1} A_{N,2} … A_{N,N}
出力
順位が一致する確率を小数で出力せよ。出力の末尾に改行を入れること。
絶対誤差あるいは相対誤差が 10^{−8} 以下のとき正答と認められる。
入力例 1
2 2/3 0 1 0 0
出力例 1
0.888888888888889
対戦は 1 回だけで、順位が一致しなくなるのはその対戦の勝敗を逆に記録してしまった場合のみであり、順位が一致する確率は 8/9 となる。
入力例 2
2 4/6 0 0 1 0
出力例 2
0.444444444444444
入力例 3
5 0/1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0
出力例 3
0.000000000000000
入力例 4
5 4/7 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0
出力例 4
0.0130979274004664
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 900 点
問題文
モリタ君はプログラミングコンテストの商品として長さ N の数列 a_1, a_2, ..., a_N を貰いました。
まず、この数列に対し A 個の加算クエリを行います。i 個目の加算クエリは以下のとおりです。
- L_i, R_i, X_i が与えられるので、a_{L_i}, a_{L_i+1}, ..., a_{R_i} それぞれに X_i を足す
そのあと、B 個の調査クエリを行います。この調査クエリの結果を求めるのがあなたの仕事です。i 個目の調査クエリは以下のとおりです。
- S_i, T_i, K_i が与えられるので、S_i 個目の加算クエリを行う直前から、T_i 個目の加算クエリを行った直後までの間での a_{K_i} の最小値を求める
制約
- 1 ≦ N ≦ 10^5
- 1 ≦ A, B ≦ 10^5
- |a_i| ≦ 10^6
- 1 ≦ L_i ≦ R_i ≦ N
- |X_i| ≦ 10^6
- 1 ≦ S_i ≦ T_i ≦ A
- 1 ≦ K_i ≦ N
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N A L_1 R_1 X_1 L_2 R_2 X_2 : L_A R_A X_A B S_1 T_1 K_1 S_2 T_2 K_2 : S_B T_B K_B
出力
B 行出力する。 i 行目には i 個目の調査クエリの結果を出力する。 出力の末尾に改行を入れること。
入力例 1
3 0 1 2 3 1 2 10 1 3 -20 2 3 20 6 1 1 1 1 2 1 3 3 2 1 1 2 1 1 3 1 3 3
出力例 1
0 -10 -9 1 2 -18
数列は以下のように変動します
- [0, 1, 2] : 最初
- [10, 11, 2] : 1つめのクエリの後
- [-10, -9, -18] : 2つめのクエリの後
- [-10, 11, 2] : 3つめのクエリの後
調査クエリの出力は以下のとおりです
- 1つめの調査クエリはmin(0, 10)=0を出力します
- 2つめの調査クエリはmin(0, 10, -10)=-10(21:18修正)を出力します
- 3つめの調査クエリはmin(-9, 11)=-9を出力します
- 4つめの調査クエリはmin(1, 11)=1を出力します
- 5つめの調査クエリはmin(2, 2)=2を出力します
- 6つめの調査クエリはmin(2, 2, -18, 2)=-18を出力します
入力例 2
3 454314 -698320 390858 7 1 3 -916798 1 2 -927828 2 2 537269 1 1 -765412 3 3 -299727 3 3 250850 3 3 526409 7 3 5 3 1 5 1 7 7 1 6 6 1 4 5 3 3 6 3 6 6 2
出力例 2
-825667 -2155724 -2155724 -2155724 -825667 -825667 -2005677
入力例 3
7 74567 -876079 911351 746764 -924924 713268 666931 7 6 7 -318557 5 6 -349441 2 4 -629716 3 7 595329 4 7 174594 5 5 -948318 2 6 -47210 8 2 4 4 1 5 3 3 5 5 1 3 3 4 7 5 1 7 1 5 5 5 6 7 2
出力例 3
117048 281635 -1274365 281635 -1499970 74567 -679036 -1553005
Time Limit: 7 sec / Memory Limit: 256 MB
配点 : 900 点
問題文
タカハシ君は長さ N の数列 a_1, a_2, ..., a_N を持っています。そして以下の動作を何度も行います。
- 数列から、隣り合う 2 つの要素を選ぶ。そしてその 2 つの要素を足して 1 つにする。つまり 2 つの要素を、要素の和を値に持つ 1 つの要素で置き換える。
なお、操作は数列の要素数が M 未満にならない限り好きな回数行えます。
タカハシ君は数列の各要素の絶対値の合計を最小化したいです。あなたの仕事はタカハシ君の代わりに、この最小を求めることです。
制約
- 1 ≦ N ≦ 20,000
- 1 ≦ M ≦ min(100, N)
- |a_i| ≦ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 a_2 ... a_N
出力
1 行に求めた答えを出力してください。 出力の末尾に改行を入れること。
入力例 1
4 2 2 -4 3 -1
出力例 1
2
- 最初は[2, -4, 3, -1]の1つ目と2つ目の要素を選びます。すると[-2, 3, -1]になります。
- 次に[-2, 3, -1]の1つ目と2つ目の要素を選びます。すると[1, -1]になります。
すると求める値は |1| + |-1| = 2 になり、これが最適です。
入力例 2
9 3 0 3 -5 -1 5 0 -3 5 -4
出力例 2
2
- 2つ目と3つ目の要素を選ぶ操作を5回行います。すると[0, -1, 5, -4]になります。
- 次に3つ目と4つ目を選び[0, -1, 1]にします。
すると求める値は |0| + |-1| + |1| = 2 になり、これが最適です。
入力例 3
5 5 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
5000000000