首爾性愛美術館18禁的藝術金豪禮★拿現金最實在!輕忽小中風,當心變殘障破戒!比丘吃葷 連3次...
2012-08-30 22:51:32 人氣(143) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[PTC] 201208D Instant Noodles [馬可夫鏈]

0
收藏
0
推薦

Problem Description
The one who buys and eats a bag of instant noodles everyday is known as a
heavy instant-noodle consumer. A market research organization is studying
the market of the heavy instant-noodle consumer. It is found that pij percent
of the heavy instant-noodle consumer who buys a bag of instant noodles of
brand i today will buy a bag of instant noodles of brand j tomorrow, where
pij > 0 and Pn
j=1 pij = 1 with n the number of brands of instant noodles.
Specifically, if the percentage of this market commanded by brand i is xi
today, then the market share of brand i will become Pn
j=1 pjixj tomorrow.
Given n, and pij , i, j = 1, 2, ..., n, can you rapidly determine which brand
of instant noodles will be the best selling with respect to this market and
calculate the percentage of this market which will be commanded by the
best-selling brand of instant noodles?

Sample Input
3
1:1:0.3
1:2:0.35
1:3:0.35
2:1:0.6
2:2:0.3
2:3:0.1
3:1:0.4
3:2:0.3
3:3:0.3
Sample Output
1 42


我只做了 100 次轉移, 試圖找到 穩定的狀態

[0.3 0.35 0.35]   [1]    [0.30]
[0.6 0.30 0.10] * [0] =  [0.35]
[0.4 0.30 0.30]   [0]    [0.35]


[0.3 0.35 0.35]   [0.30]    [0....]
[0.6 0.30 0.10] * [0.35] =  [0....]
[0.4 0.30 0.30]   [0.35]    [0....]

持續做 100 次


#include <stdio.h>
#include <string.h>
typedef struct {
    double v[501][501];
} Matrix;
Matrix muitaa(Matrix &a, Matrix &b, int n) {
    Matrix c;
    int i, j, k;
    memset(&c, 0, sizeof(c));
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            c.v[1][j] += a.v[i][j] * b.v[1][i];
        }
    }
    return c;
}
Matrix F;
Matrix A;
int main() {
    int n, a, b;
    double v;
    while(scanf("%d", &n) == 1) {
        int m = n*n;
        for(int i = 0; i < m; i++) {
            scanf("%d:%d:%lf", &a, &b, &v);
            F.v[a][b] = v;
        }
        memset(&A, 0, sizeof(A));
        A.v[1][1] = 1;
        for(int i = 0; i < 100; i++) {
            A = muitaa(F, A, n);
        }
        double ans = 0;
        int at = 0;
        for(int i = 1; i <= n; i++)
            if(A.v[1][i] > ans)
                ans = A.v[1][i], at = i;
        printf("%d %d\n", at, (int)(ans*100));
    }
    return 0;
}

PTCD
台長:Morris
人氣(143) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[PTC] 201208A Defect Alarms [模擬]
此分類上一篇:[ITSA] 16th 總解答

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文