Circle
Time Limit: 2000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
You have been given a circle from 0 to n - 1. If you are currently at x, you will move to (x - 1) mod n or (x + 1) mod n with equal probability. Now we want to know the expected number of steps you need to reach x from 0.
输入
The first line contains one integer T — the number of test cases.
Each of the next T lines contains two integers n, x (0 ≤ x < n ≤ 1000) as we mention above.
输出
For each test case. Print a single float number — the expected number of steps you need to reach x from 0. The figure is accurate to 4 decimal places.
示例输入
3 3 2 5 4 10 5
示例输出
2.0000 4.0000 25.0000
提示
来源
2014年山东省第五届ACM大学生程序设计竞赛
示例程序
用高消水过去的，设dp[i]表示在位置ｉ时到达ｘ的期望步数
dp[i] = 0.5*(dp[(i + 1)%n] + 1) + 0.5 * (dp[(i - 1) % n] + 1) ;
注意(i - 1) % n 可能是负的，要加个ｎ然后取模
把方程整理下
2 * dp[i] - dp[(i + 1) % n] - dp[(i - 1) % n] = 2;
然后对０－（ｎ－１）每个点建立方程
/*************************************************************************
> File Name: sdut2878.cpp
> Author: ALex
> Mail: 405045132@qq.com
> Created Time: 2014年12月29日 星期一 22时00分21秒
************************************************************************/
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
const double eps = 1e-12;
double mat[N][N], x[N];
bool free_x[N];
int n, e;
int Gauss()
{
int free_index, free_num;
int max_r, k, col, var, equ;
var = equ = n;
memset (free_x, 1, sizeof(free_x));
memset (x, 0, sizeof(x));
for (k = col = 0; k < equ && col < var; ++k, ++col)
{
max_r = k;
for (int i = k + 1; i < equ; ++i)
{
if (fabs(mat[i][col]) - fabs(mat[max_r][col]) > eps)
{
max_r = i;
}
}
if (max_r != k)
{
for (int j = k; j < var + 1; ++j)
{
swap(mat[max_r][j], mat[k][j]);
}
}
if (fabs(mat[k][col]) <= eps)
{
--k;
continue;
}
for (int i = k + 1; i < equ; ++i)
{
if (fabs(mat[i][col]) <= eps)
{
continue;
}
double tmp = mat[i][col] / mat[k][col];
for (int j = col; j < var + 1; ++j)
{
mat[i][j] -= mat[k][j] * tmp;
}
}
}
for (int i = k; i < equ; ++i)
{
if (fabs(mat[i][var]) > eps)
{
return 0;
}
}
if (k < var)
{
for (int i = k - 1; i >= 0; --i)
{
free_num = 0;
for (int j = 0; j < var; ++j)
{
if (fabs(mat[i][j]) > eps && free_x[j])
{
free_num++;
free_index = j;
}
}
if (free_num > 1)
{
continue;
}
double tmp = mat[i][var];
for (int j = 0; j < var; ++j)
{
if (j != free_index && fabs(mat[i][j]) > eps)
{
tmp -= mat[i][j] * x[j];
}
}
free_x[free_index] = 0;
x[free_index] = tmp / mat[i][free_index];
}
return var - k;
}
for (int i = var - 1; i >= 0; --i)
{
double tmp = mat[i][var];
for (int j = i + 1; j < var; ++j)
{
if (fabs(mat[i][j]) > eps)
{
tmp -= x[j] * mat[i][j];
}
}
x[i] = tmp / mat[i][i];
}
return 1;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &e);
memset (mat, 0, sizeof(mat));
for (int i = 0; i < n; ++i)
{
if (i == e)
{
mat[i][i] = 1;
mat[i][n] = 0;
}
else
{
mat[i][i] = 2;
mat[i][(i + 1) % n] = -1;
int t = (i - 1) % n;
if (t < 0)
{
t = (t + n) % n;
}
mat[i][t] = -1;
mat[i][n] = 2;
}
}
Gauss();
printf("%.4f\n", x[0]);
}
return 0;
}