2012-08-30 22:51:32Morris
[PTC] 201208D Instant Noodles [馬可夫鏈]
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;
}
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;
}