解題區/解題區 - UVa

UVa 982 - Cube

contents

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

Problem

有一天醒來，發現自己身處一個方體房間，六個面上都有門可以通往其他房間，不幸地是這裏沒有食物，若不趕緊走出去就會死在這裡。

搜索途中遇到其他人，他們說有些房間藏著陷阱，一碰到就會致死。為了逃離這裡，發現每個房間的角落都有一個數字，這個數字隱藏著出口的方向，指引著下一個要打開的門，但即使這樣，仍然不知道門後的房間是否有致死陷阱。

若房間的數字為 N 時，下一個門的座標為

  • x = (N 出現幾次偶數位數) / (N 的總位數)
  • y = (N 出現幾次質數位數) / (N 的總位數)
  • z = (N 出現幾次小於 5 的奇數位數) / (N 的總位數)
  • 化簡分數，保證測資只會產生 0, 1/2, 1 三種情況
  • 得到 (x, y, z)。接著，再計算一個向量 (vx, vy, vz)
    • vx = N 的第一位數 / N 的第二位數
    • vy = N 的第三位數 / N 的第四位數
    • vz = N 的第五位數 / N 的第六位數
  • 內積 (x, y, z)(vx, vy, vz) = x * vx + y * vy + z * vz 化簡若發生分子為合數 (非質數非 1 的數)，則保證下一個房間是安全的。

例如給定數字

1
2
3
4
5
6
7
8
9
10
11
N = 24556789
x = |[2, 4, 6, 8]| / |[2, 4, 5, 5, 6, 7, 8, 9]| = 1/2
y = |[2, 5, 5, 7]| / |[2, 4, 5, 5, 6, 7, 8, 9]| = 1/2
z = |[]| / |[2, 4, 5, 5, 6, 7, 8, 9]| = 0
vx = 2 / 4 = 1 / 2
vy = 5 / 5 = 1
vz = 6 / 7
x * vx + y * vy + vz = 3 / 4, 3 is prime, FATAL
1
2
3
4
5
6
7
8
9
10
11
N = 74974652
x = |[4, 4, 6, 2]| / |[7, 4, 9, 7, 4, 6, 5, 2]| = 1/2
y = |[7, 7, 5, 2]| / |[7, 4, 9, 7, 4, 6, 5, 2]| = 1/2
z = |[]| / |[7, 4, 9, 7, 4, 6, 5, 2]| = 0
vx = 7 / 4
vy = 9 / 7
vz = 4 / 6 = 2 / 3
x * vx + y * vy + vz = 7 / 8 + 9 / 14 = 85 / 56, 85 is not prime, SAFE.

Sample Input

1
2
24556789
74974652

Sample Output

1
2
3
4
1/2 1/2 0
FATAL
1/2 1/2 0
SAFE

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
#include <assert.h>
using namespace std;
struct Frac {
    long long x, y;
    Frac(long long a = 0, long long b = 1) {
        x = a, y = b;
        normal();
    }
    void normal() {
        if (y < 0)  x = -x, y = -y;
        long long g = llgcd(x, y);
        x /= g, y /= g;
        if (y < 0)  x = -x, y = -y;
    }
    long long llgcd(long long x, long long y) const {
    	if (x == 0)	return y;
    	if (y == 0)	return x;
        long long t;
        while (x%y)
            t = x, x = y, y = t % y;
        return y;
    }
    Frac operator-(const Frac &a) const {
        long long va = 0, vb = a.y / llgcd(y, a.y) * y;
        va = vb / y * x - vb / a.y * a.x;
        return Frac(va, vb);
    }
    Frac operator+(const Frac &a) const {
        long long va = 0, vb = a.y / llgcd(y, a.y) * y;
        va = vb / y * x + vb / a.y * a.x;
        return Frac(va, vb);
    }
    Frac operator*(const Frac a) const {
        long long g1 = llgcd(x, a.y), g2 = llgcd(a.x, y);
        long long va = 0, vb = 0;
        va = (x / g1) * (a.x / g2);
        vb = (y / g2) * (a.y / g1);
        return Frac(va, vb);
    }
    Frac operator/(const Frac a) const {
        long long g1 = llgcd(y, a.y), g2 = llgcd(x, a.x);
        long long va = 0, vb = 0;
        va = (a.y / g1) * (x / g2);
        vb = (y / g1) * (a.x / g2);
        return Frac(va, vb);
    }
    bool operator==(const Frac &a) const {
        return x - a.x == 0 && y - a.y == 0;
    }
    bool operator<(const Frac &a) const {
        return x * a.y < a.x * y;
    }
    void print() {
        if (y == 1)
            printf("%lld", x);
        else
            printf("%lld/%lld", x, y);
    }
};
Frac getX(char s[]) {
    int a = 0, b = 0;
    for (int i = 0; s[i]; i++) {
        a += (s[i] - '0')%2 == 0;
        b ++;
    }
    return Frac(a, b);
}
Frac getY(char s[]) {
    int a = 0, b = 0;
    for (int i = 0; s[i]; i++) {
        int d = s[i] - '0';
        if (d == 2 || d == 3 || d == 5 || d == 7)
            a++;
        b ++;
    }
    return Frac(a, b);
}
Frac getZ(char s[]) {
    int a = 0, b = 0;
    for (int i = 0; s[i]; i++) {
        int d = s[i] - '0';
        if (d < 5 && d%2 == 1)
            a++;
        b ++;
    }
    return Frac(a, b);
}
int getTestXYZ(char s[], Frac &x, Frac &y, Frac &z) {
    int n = (int) strlen(s);
    if (s[1%n] == '0' || s[3%n] == '0' || s[5%n] == '0')
        return 0;
    x = Frac(s[0%n] - '0', s[1%n] - '0');
    y = Frac(s[2%n] - '0', s[3%n] - '0');
    z = Frac(s[4%n] - '0', s[5%n] - '0');
    return 1;
}
int isprime(int x) {
    if (x == 1)
        return 0;
    for (int i = 2; i * i <= x; i++)
        if (x%i == 0)
            return 0;
    return 1;
}
int main() {
    char s[64];
    while (scanf("%s", s) == 1) {
        Frac x = getX(s), y = getY(s), z = getZ(s);
        Frac rx, ry, rz;
        x.print(), printf(" ");
        y.print(), printf(" ");
        z.print(), printf("\n");
        
        assert(x == Frac(0, 1) || x == Frac(1, 2) || x == Frac(1, 1));
        assert(y == Frac(0, 1) || y == Frac(1, 2) || y == Frac(1, 1));
        assert(z == Frac(0, 1) || z == Frac(1, 2) || z == Frac(1, 1));
        int f = getTestXYZ(s, rx, ry, rz);
        if (!f) {
        	assert(false);
        	continue;
        }
//        rx.print(), printf(" ");
//        ry.print(), printf(" ");
//        rz.print(), printf("\n");
        
        Frac dot = rx * x + ry * y + rz * z;
        if (!isprime((int)dot.x) && dot.x != 1) {
            puts("SAFE");
        } else {
            puts("FATAL");
        }
//        dot.print();
//        puts("");
    }
    return 0;
}
/*
 18540
 385
 1222 
 123456
 1234
 24556789
 74974652
*/