lightoj1151

Title:

• There are 100 squares, starting from 1, each random walk 1-6. There are n cells that will be sent to other cells in one direction, tp[i] means from I to tp[i].  
• There will be no transfers for 1 and 100, and no two transfers for a grid. Ask for the expected value of 100 chromons, and pay attention not to go beyond 100.

Title Solution

• dp[i] indicates the desired number of times from I to 100
• If there is a gate, dp[i] = dp[v[i]]
• If there is no gate: dp[i] = 1/6 * ∑ (dp[i+j] + 1)(j from 1 to k) + 1/6 * ∑ (dp[i] + 1)(j from k+1 to 6), where k = min(100-i,6)
• After simplification, k * dp[i] -∑ dp[i+j] = 6 (j from 1 to k)
• Simultaneous equations
• k * dp[i] - ∑dp[i+j] = 6 (j from 1 to k)
• dp[i] = dp[v[i]]
• Gauss elimination for dp[1]

Code

#include <bits/stdc++.h>
using namespace std;
int const N = 100 + 10;
int n,v[N];
double a[N][N];
void SwapRow(double a[][N],int n,int p,int q){
    for(int i=p;i<=n+1;i++)
        swap(a[p][i],a[q][i]);
}
void SelectColE(double a[][N],int n){
    for(int i=1;i<=n-1;i++){
        int MaxRowE = i;
        for(int j=i;j<=n;j++)
            if(fabs(a[j][i]) > fabs(a[MaxRowE][i]))  MaxRowE = j;
        if(i != MaxRowE)    SwapRow(a,n,i,MaxRowE);
        for(int j=i+1;j<=n;j++){
            double temp = a[j][i] / a[i][i];
            for(int k=i;k<=n+1;k++)
                a[j][k] -= a[i][k] * temp;
        }
    }
}
void Back_Substitution(double a[][N],int n){
    for(int i=n;i>=1;i--)
    {
        for(int j=i+1;j<=n;j++)
            a[i][n+1] -=a[i][j] * a[j][n+1];
        a[i][n+1] /=a[i][i];
    }
}
void Gauss_Elimination(double a[][N],int n){
    SelectColE(a,n);
    Back_Substitution(a,n);
}
int main(){
	int T,caser = 0;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		memset(v,0,sizeof(v));
		for(int i=1;i<=n;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			v[x] = y;
		}
		memset(a,0,sizeof(a));
		a[100][100] = 1;   //E[100] = 0; all plus coefficient initialization
		for(int i=1;i<100;i++){
			if(v[i]){   //If a jump occurs
				a[i][i] = 1;
				a[i][v[i]] = -1;
			}else{  //If you don't jump
				int k = min(6,100 - i);
				a[i][i] = k;
				for(int j=1;j<=k;j++)
					a[i][i+j] = -1;
				a[i][101] = 6;
			}
		}
	    Gauss_Elimination(a,100);
		printf("Case %d: %.6lf\n",++caser,a[1][101]);
	}
	return 0;
}