CODE FESTIVAL 2016 Elimination Tournament Round 2 (Parallel)

A - 迷子の高橋君 / Takahashi is Missing!


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 700

問題文

青木君は、一次元の世界で迷子になった高橋君を探そうとしています。 はじめ、青木君は座標 0、高橋君は座標 x にいることがわかっており、 それ以降、高橋君がどこにいるかを青木君は知ることが出来ません。

時間はターンで区切ることができ、1 ターンごとに以下の行動が同時に行われます。

  • 青木君は、今いる座標を a とすると、a-1aa+13 箇所から移動先を選んで移動することが出来る。
  • 高橋君は、今いる座標を b とすると、p パーセントの確率で b-1 に移動し、100-p パーセントの確率で b+1 に移動する。

青木君と高橋君が同じ座標にたどり着いた時、青木君は高橋君を見つけることが出来ます。 青木君と高橋君がすれ違ってしまった場合、青木君は高橋君を見つけることが出来ません。

青木君は高橋君を見つけるまでのターン数の期待値を最小化したいです。そのときの期待値を求めてください。

制約

  • 1x1,000,000,000
  • 1p100
  • x, p は整数である。

部分点

  • 200 点分のデータセットでは、 p=100 が成り立つ。
  • 300 点分のデータセットでは、 x10 が成り立つ。

入力

入力は以下の形式で標準入力から与えられる。

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

  • 1x1,000,000,000
  • 1p100
  • x and p are integers.

Partial Scores

  • In the test set worth 200 points, p=100.
  • In the test set worth 300 points, x10.

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

Submit提出する