2014-07-23

UVa 11605 - Lights inside a 3d Grid

1. Input
2. Output
3. Sample Input
4. Output for Sample Input
5. Solution

You are given a 3D grid, which have dimensions N, M and P. Each of the M x N x P cells has a light. Initially all lights are off. You will have K turns. In each of the K turns,

You will select a cell A randomly from the grid
You will select a cell B randomly from the grid
Toggle the states of all the bulbs bounded by cell A and cell B, ie make all the ON lights OFF and make all the OFF lights ON which are bounded by A and B. To be more clear, consider cell A is (x1, y1, z1) and cell B is (x2, y2, z2). Then you have to toggle all the bulbs in grid cell (x, y, z) where min(x1,x2)<=x<=max(x1,x2) , min(y1,y2)<=y<=max(y1,y2) and min(z1, z2)<=z<=max(z1, z2).

How many bulbs are expected to be ON after K turns?

Note:

A and B can be the same cell.

Input

First line of the input is an integer T(T<101) which denotes the number of test cases. Each of the next T lines represents one test case by 4 integers N, M, P (0 < M, N, P < 101) and K (0<=K<=10000) separated by spaces.

Output

Output one line for each test cases giving the expected number of ON lights. Up to 1E-6 error in your output will be acceptable. Print the case number followed by the output. Look at the sample output for exact format.

Sample Input

1
2
3

2
2 3 4 1
2 3 4 2

Output for Sample Input

1 2	Case 1: 6.3750000000 Case 2: 9.0976562500

Solution

題目描述：

在 N x M x P 的三維空間中，任抓 2 個格子所構成的長方體，將長方體內部的所有格子點進行反轉標記 (一開始全是 OFF)，抓取 K 次得到的 ON 標記格子數期望值為何？

題目解法：

每一個軸的情況可以分開考慮，考慮對於座標 (x, y, z) 被選到的機率 p，則 sigma(p * 1) = 所求的期望值。

1 2	p = dp[N][x] * dp[M][y] * dp[P][z], dp[i][j] 表示在區間 [1, i] 中任挑區間包含 j 的機率為何。

得到 p 之後，計算在 K 次中，得到奇數 ON 的機率為何，這裡藉由矩陣乘法來完成。

[1 - p, p]
[p, 1 - p] = M
         [0  ON]    [final ON  p]
M ^ K *  [1 OFF]  = [final OFF p]

藉由快速取冪次來完成。

#include <stdio.h> 
#include <string.h>
struct Matrix {
    double v[2][2];
    int row, col; // row x col
    Matrix(int n, int m, double a = 0) {
        memset(v, 0, sizeof(v));
        row = n, col = m;
        for(int i = 0; i < row && i < col; i++)
            v[i][i] = a;
    }
    Matrix operator*(const Matrix& x) const {
        Matrix ret(row, x.col);
        for(int i = 0; i < row; i++)
            for(int j = 0; j < x.col; j++)
                for(int k = 0; k < col; k++)
                    ret.v[i][j] += v[i][k] * x.v[k][j];
        return ret;
    }
    Matrix operator^(const int& n) const {
        Matrix ret(row, col, 1), x = *this;
        int y = n;
        while(y) {
            if(y&1)	ret = ret * x;
            y = y>>1, x = x * x;
        }
        return ret;
    }
};
int main() {
    int N, M, P, K;
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d %d", &N, &M, &P, &K);
        double pN[128], pM[128], pP[128];
        for(int i = 1; i <= N; i++)
            pN[i] = (i * (N-i+1) * 2 - 1) / (double)(N * N);			
        for(int i = 1; i <= M; i++)
            pM[i] = (i * (M-i+1) * 2 - 1) / (double)(M * M);
        for(int i = 1; i <= P; i++)
            pP[i] = (i * (P-i+1) * 2 - 1) / (double)(P * P);
        double ret = 0;
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                for(int k = 1; k <= P; k++) {
                    double p = pN[i] * pM[j] * pP[k];
                    Matrix mm(2, 2);
                    mm.v[0][0] = mm.v[1][1] = 1 - p;
                    mm.v[0][1] = mm.v[1][0] = p;
                    Matrix mmk = mm ^ K;
                    ret += mmk.v[0][1];
                }
            }
        }
        printf("Case %d: %.10lf\n", ++cases, ret);
    }
    return 0;
}

Morris' Blog