解題區/解題區 - UVa

UVA 12763 - Dicey Dice

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有兩個玩家 A, B，盤面上有三個骰子，先手先挑一個骰子出來，後手再從剩餘兩個骰子中挑一個。接著兩個人會分別骰出點數，骰出最大的那個玩家獲勝，如果骰出一樣點數則平手

給予先手玩家，和三個六面骰子，請問獲勝機率高的玩家為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
3
A
1 1 1 1 1 1
2 3 2 4 5 3
6 6 6 6 6 6
A
4 3 7 9 2 5
8 1 4 6 9 2
6 5 1 8 3 7
B
1 2 3 4 4 4
1 2 3 4 4 4
1 2 3 4 4 4

Sample Output

1
2
3
A
B
fair

Solution

先手必然是最大化自己的獲勝機會下，最小化對方的獲勝機會。而後手則是在剩餘兩個骰子的時候，挑選獲勝機會最高的那個骰子。

因此這一題窮舉先手拿哪一個骰子，模擬後手選剩餘哪個骰子獲勝機會最高，最大化先手的獲勝機會下、最小化後手獲勝機會。

題目描述相當少，就當作是兩個完美玩家吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    char s[10];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s);
        int player = s[0] - 'A';
        int dice[3][6];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 6; j++) {
                scanf("%d", &dice[i][j]);
            }
        }
        double rmx = 0, rmx2 = 1;
        for (int i = 0; i < 3; i++) { // A player pick
            double mx = 1, mx2 = 0;
            for (int j = 0; j < 3; j++) { // B player pick
                if (i == j)	continue;
                int pa = 0, pb = 0;
                for (int p = 0; p < 6; p++) {
                    for (int q = 0; q < 6; q++) {
                        pa += dice[i][p] > dice[j][q];
                        pb += dice[i][p] < dice[j][q];
                    }
                }
                
                if (mx > pa / 36.0 || (mx == pa / 36.0 && mx2 < pb/36.0)) {
                    mx = pa /36.0;
                    mx2 = pb / 36.0;
                }
            }
            if (rmx < mx || (rmx == mx && rmx2 > mx2)) {
                rmx = mx;
                rmx2 = mx2;
            }
        }
        if (rmx > rmx2)
            printf("%c\n", player + 'A');
        else if (rmx < rmx2)
            printf("%c\n", 1 - player + 'A');
        else
            printf("fair\n");
//			printf("%lf %lf\n", rmx, rmx2);
    }
    return 0;
}
/*
3
A
1 1 1 1 1 1
2 3 2 4 5 3
6 6 6 6 6 6
A
4 3 7 9 2 5
8 1 4 6 9 2
6 5 1 8 3 7
B
1 2 3 4 4 4
1 2 3 4 4 4
1 2 3 4 4 4
*/