#include <bits/stdc++.h>
using namespace std;
const double p_suc = 1.0/4;
const double p_fail = 3.0/2000;
const double p_any = p_suc + p_fail;
vector<double> chain(vector< vector<double> > A, vector<double> b) {
while(accumulate(b.begin()+1, prev(b.end()), 0.0) > 1e-9){
vector<double> c(b.size(), 0.0);
for(int j=0;j<A.size();++j){
for(int i=0;i<b.size();++i){
c[j] += A[j][i] * b[i];
}
}
b = c;
}
return b;
}
double get_failprob(int n){
vector<vector<double> > A(2*n+1, vector<double>(2*n+1, 0.0));
A[0][0] = A[2*n].back() = 1.0;
for(int i=1;i<2*n;++i){
A[i-1][i] = p_fail / p_any;
A[i+1][i] = p_suc / p_any;
}
vector<double> b(2*n+1, 0);
b[n] = 1;
auto ans = chain(A, b);
for(auto &e:ans) cerr << e << " "; cerr << "\n";
return ans[0];
}
signed main()
{
int n = 5;
vector<double> v(n);
for(int i=1;i<n;++i){
v[i] = get_failprob(i);
}
for(int i=1;i<n;++i){
cout << i << " : " << setw(12) << v[i] << " " << 1000*(v[i]) << "\n";
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBkb3VibGUgcF9zdWMgPSAxLjAvNDsKY29uc3QgZG91YmxlIHBfZmFpbCA9IDMuMC8yMDAwOwpjb25zdCBkb3VibGUgcF9hbnkgPSBwX3N1YyArIHBfZmFpbDsKCnZlY3Rvcjxkb3VibGU+IGNoYWluKHZlY3RvcjwgdmVjdG9yPGRvdWJsZT4gPiBBLCB2ZWN0b3I8ZG91YmxlPiBiKSB7CiAgICB3aGlsZShhY2N1bXVsYXRlKGIuYmVnaW4oKSsxLCBwcmV2KGIuZW5kKCkpLCAwLjApID4gMWUtOSl7CiAgICAgICAgdmVjdG9yPGRvdWJsZT4gYyhiLnNpemUoKSwgMC4wKTsKICAgICAgICBmb3IoaW50IGo9MDtqPEEuc2l6ZSgpOysrail7CiAgICAgICAgICAgIGZvcihpbnQgaT0wO2k8Yi5zaXplKCk7KytpKXsKICAgICAgICAgICAgICAgIGNbal0gKz0gQVtqXVtpXSAqIGJbaV07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgYiA9IGM7CiAgICB9CiAgICByZXR1cm4gYjsKfQoKZG91YmxlIGdldF9mYWlscHJvYihpbnQgbil7CiAgICB2ZWN0b3I8dmVjdG9yPGRvdWJsZT4gPiBBKDIqbisxLCB2ZWN0b3I8ZG91YmxlPigyKm4rMSwgMC4wKSk7CiAgICBBWzBdWzBdID0gQVsyKm5dLmJhY2soKSA9IDEuMDsKICAgIGZvcihpbnQgaT0xO2k8MipuOysraSl7CiAgICAgICAgQVtpLTFdW2ldID0gcF9mYWlsIC8gcF9hbnk7CiAgICAgICAgQVtpKzFdW2ldID0gcF9zdWMgLyBwX2FueTsKICAgIH0KICAgIHZlY3Rvcjxkb3VibGU+IGIoMipuKzEsIDApOwogICAgYltuXSA9IDE7CiAgICBhdXRvIGFucyA9IGNoYWluKEEsIGIpOwoKICAgIGZvcihhdXRvICZlOmFucykgY2VyciA8PCBlIDw8ICIgIjsgY2VyciA8PCAiXG4iOwoKICAgIHJldHVybiBhbnNbMF07Cn0KCnNpZ25lZCBtYWluKCkKewogICAgaW50IG4gPSA1OwogICAgdmVjdG9yPGRvdWJsZT4gdihuKTsKICAgIGZvcihpbnQgaT0xO2k8bjsrK2kpewogICAgICAgIHZbaV0gPSBnZXRfZmFpbHByb2IoaSk7CiAgICB9CiAgICBmb3IoaW50IGk9MTtpPG47KytpKXsKICAgICAgICBjb3V0IDw8IGkgPDwgIiA6ICIgPDwgc2V0dygxMikgPDwgIHZbaV0gPDwgIiAiIDw8IDEwMDAqKHZbaV0pIDw8ICJcbiI7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=