Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 700 点
問題文
青木君は、一次元の世界で迷子になった高橋君を探そうとしています。 はじめ、青木君は座標 0、高橋君は座標 x にいることがわかっており、 それ以降、高橋君がどこにいるかを青木君は知ることが出来ません。
時間はターンで区切ることができ、1 ターンごとに以下の行動が同時に行われます。
- 青木君は、今いる座標を a とすると、a-1、a、a+1 の 3 箇所から移動先を選んで移動することが出来る。
- 高橋君は、今いる座標を b とすると、p パーセントの確率で b-1 に移動し、100-p パーセントの確率で b+1 に移動する。
青木君と高橋君が同じ座標にたどり着いた時、青木君は高橋君を見つけることが出来ます。 青木君と高橋君がすれ違ってしまった場合、青木君は高橋君を見つけることが出来ません。
青木君は高橋君を見つけるまでのターン数の期待値を最小化したいです。そのときの期待値を求めてください。
制約
- 1 ≦ x ≦ 1,000,000,000
- 1 ≦ p ≦ 100
- x, p は整数である。
部分点
- 200 点分のデータセットでは、 p=100 が成り立つ。
- 300 点分のデータセットでは、 x ≦ 10 が成り立つ。
入力
入力は以下の形式で標準入力から与えられる。
x p
出力
求める期待値を 1 行で出力せよ。 絶対誤差または相対誤差が 10^{-6} 以下ならば正解となる。
入力例 1
3 100
出力例 1
2.0000000
高橋君は必ず -1 移動するので、青木君は、1 ターン目で座標 1 に移動し、 2 ターン目でその場に留まることで、高橋君を 2 ターンで見つけることが出来ます。
入力例 2
6 40
出力例 2
7.5000000
入力例 3
101 80
出力例 3
63.7500000
Score : 700 points
Problem Statement
Aoki is in search of Takahashi, who is missing in a one-dimentional world. Initially, the coordinate of Aoki is 0, and the coordinate of Takahashi is known to be x, but his coordinate afterwards cannot be known to Aoki.
Time is divided into turns. In each turn, Aoki and Takahashi take the following actions simultaneously:
-
Let the current coordinate of Aoki be a, then Aoki moves to a coordinate he selects from a-1, a and a+1.
-
Let the current coordinate of Takahashi be b, then Takahashi moves to the coordinate b-1 with probability of p percent, and moves to the coordinate b+1 with probability of 100-p percent.
When the coordinates of Aoki and Takahashi coincide, Aoki can find Takahashi. When they pass by each other, Aoki cannot find Takahashi.
Aoki wants to minimize the expected number of turns taken until he finds Takahashi. Find the minimum possible expected number of turns.
Constraints
- 1 ≦ x ≦ 1,000,000,000
- 1 ≦ p ≦ 100
- x and p are integers.
Partial Scores
- In the test set worth 200 points, p=100.
- In the test set worth 300 points, x ≦ 10.
Input
The input is given from Standard Input in the following format:
x p
Output
Print the minimum possible expected number of turns. The output is considered correct if the absolute or relative error is at most 10^{-6}.
Sample Input 1
3 100
Sample Output 1
2.0000000
Takahashi always moves by -1. Thus, by moving to the coordinate 1 in the 1-st turn and staying at that position in the 2-nd turn, Aoki can find Takahashi in 2 turns.
Sample Input 2
6 40
Sample Output 2
7.5000000
Sample Input 3
101 80
Sample Output 3
63.7500000
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1200 点
問題文
高橋君は魔法使いです。高橋君は魔法をかけることで、M 項からなる数列 (a_1,a_2,...,a_M) を、s_i を a_1～a_i の和とした数列 (s_1,s_2,...,s_M) に変えることができます。
ある日、高橋君は M 項からなる数列を N 個もらい、順番に A_1,A_2,...,A_N と名付けました。さらに、高橋君は魔法をかけることで、辞書順で比較した際に A_1 < A_2 < ... < A_N となるようにしようと思いました。 高橋君が一つの数列を選んでそれに魔法をかける操作を 1 回の魔法とします。このとき、高橋君が目標を達成するために必要な魔法の最小回数を求めてください。
ただし、M 項からなる 2 つの数列 a = (a_1,a_2,...,a_M) , b = (b_1,b_2,...,b_M) が辞書順で a < b であるとは、ある i (1 ≦ i ≦ M) で a_j = b_j (1 ≦ j < i) かつ a_i < b_i が成り立つことを指します。
制約
- 1 ≦ N ≦ 10^3
- 1 ≦ M ≦ 10^3
- A_i の j 項目を A_{(i,j)} としたとき、 1 ≦ A_{(i,j)} ≦ 10^9
部分点
- 200 点分のテストケースでは、10^4 回以下の回数で目標を達成し、かつ、どの項も 10^9 以下となるようにすることができる。
- 別の 800 点分のテストケースでは、A_{(i,j)} ≦ 80 が成立する。
入力
入力は以下の形式で標準入力から与えられる。
N M
A_{(1,1)} A_{(1,2)} ... A_{(1,M)}
A_{(2,1)} A_{(2,2)} ... A_{(2,M)}
:
A_{(N,1)} A_{(N,2)} ... A_{(N,M)}
出力
高橋君がかける魔法の最小回数を出力せよ。ただし、高橋君が目標を達成できないならば、代わりに -1 を出力せよ。
入力例1
3 3 2 3 1 2 1 2 2 6 3
出力例1
1
A_2 に対して 1 回魔法をかけることで、A_2 = (2 , 3 , 5) となり、高橋君は目標を達成できます。
入力例2
3 3 3 2 10 10 5 4 9 1 9
出力例2
-1
この場合、何回魔法をかけても高橋君は目標を達成できません。
入力例3
5 5 2 6 5 6 9 2 6 4 9 10 2 6 8 6 7 2 1 7 3 8 2 1 4 8 3
出力例3
11
Score : 1200 points
Problem Statement
Takahashi is a magician. He can cast a spell on an integer sequence (a_1,a_2,...,a_M) with M terms, to turn it into another sequence (s_1,s_2,...,s_M), where s_i is the sum of the first i terms in the original sequence.
One day, he received N integer sequences, each with M terms, and named those sequences A_1,A_2,...,A_N. He will try to cast the spell on those sequences so that A_1 < A_2 < ... < A_N will hold, where sequences are compared lexicographically. Let the action of casting the spell on a selected sequence be one cast of the spell. Find the minimum number of casts of the spell he needs to perform in order to achieve his objective.
Here, for two sequences a = (a_1,a_2,...,a_M), b = (b_1,b_2,...,b_M) with M terms each, a < b holds lexicographically if and only if there exists i (1 ≦ i ≦ M) such that a_j = b_j (1 ≦ j < i) and a_i < b_i.
Constraints
- 1 ≦ N ≦ 10^3
- 1 ≦ M ≦ 10^3
- Let the j-th term in A_i be A_{(i,j)}, then 1 ≦ A_{(i,j)} ≦ 10^9.
Partial Scores
- In the test set worth 200 points, Takahashi can achieve his objective by at most 10^4 casts of the spell, while keeping the values of all terms at most 10^9.
- In the test set worth another 800 points, A_{(i,j)} ≦ 80.
Input
The input is given from Standard Input in the following format:
N M
A_{(1,1)} A_{(1,2)} … A_{(1,M)}
A_{(2,1)} A_{(2,2)} … A_{(2,M)}
:
A_{(N,1)} A_{(N,2)} … A_{(N,M)}
Output
Print the minimum number of casts of the spell Takahashi needs to perform. If he cannot achieve his objective, print -1 instead.
Sample Input 1
3 3 2 3 1 2 1 2 2 6 3
Sample Output 1
1
Takahashi can achieve his objective by casting the spell on A_2 once to turn it into (2 , 3 , 5).
Sample Input 2
3 3 3 2 10 10 5 4 9 1 9
Sample Output 2
-1
In this case, Takahashi cannot achieve his objective by casting the spell any number of times.
Sample Input 3
5 5 2 6 5 6 9 2 6 4 9 10 2 6 8 6 7 2 1 7 3 8 2 1 4 8 3
Sample Output 3
11