解題區/解題區 - UVa

UVa 11910 - Closest Fractions

contents

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

Problem

對於每一個浮點數，找到一個最靠近的分數，分子分母限制在 [1, 1000] 的整數。

Sample Input

1
2
3
3.141592654
66.66666666
333.3333333

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
Input : 3.141592654
    1 : 3.141592920 =  355 / 113
    2 : 3.141630901 =  732 / 233
    3 : 3.141552511 =  688 / 219
Input : 66.66666666
    1 : 66.66666667 =  200 / 3
    2 : 66.64285714 =  933 / 14
    3 : 66.69230769 =  867 / 13
Input : 333.3333333
    1 : 333.3333333 = 1000 / 3
    2 : 333.5000000 =  667 / 2
    3 : 333.0000000 =  333 / 1

Solution

預先將所有分數建表，然後每一次二分搜索。

最麻煩在於輸出要保證長度 10 位，細讀 printf() 後，發現頂多限制小數點後的位數、小數點前的位數，如果要同時限制還是要自己來。

最後使用 %*.*f，* 號部分要自己帶入參數。如果用 substring 會造成四捨五入的地方消失而拿到 WA。

原本想不建表，直接用鄰近搜索，誤差害死人。

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
#include <stdio.h>
#include <math.h>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
class Frac {
    public:
    int x, y;
    Frac(int a = 0, int b = 0):
        x(a), y(b) {}
    double toDouble() const {
        return (double) x/y;
    }
    bool operator<(const Frac &a) const {
        return toDouble() < a.toDouble();
    }
} D[1048576];
double DD[1048576];
double cmpv;
bool cmp(Frac a, Frac b) {
    return fabs(a.toDouble() - cmpv) < fabs(b.toDouble() - cmpv);
}
int f(double v) {
    if (v >= 1000)	return 4;
    if (v >= 100)	return 3;
    if (v >= 10)	return 2;
    return 1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n = 0;
    for (int y = 1; y <= 1000; y++) {
        for (int x = 1; x <= 1000; x++) {
            if (__gcd(x, y) == 1)
                D[n++] = Frac(x, y);
        }
    }
    sort(D, D + n);
    for (int i = 0; i < n; i++)
        DD[i] = D[i].toDouble();
    char s[32];
    double v;
    while (scanf("%s", s) == 1) {
        printf("Input : %s\n", s);
        sscanf(s, "%lf", &v);
        int pos = lower_bound(DD, DD + n, v) - DD;
        vector<Frac> A;
        for (int i = max(0, pos - 6); i < min(n, pos + 6); i++)
            A.push_back(D[i]);
        cmpv = v;
        sort(A.begin(), A.end(), cmp);
        for (int i = 0, j = 1; i < 3 && i < A.size(); i++, j++)
            printf("    %d : %*.*lf = %4d / %d\n", j, f(A[i].toDouble()), 10 - f(A[i].toDouble()), A[i].toDouble(), A[i].x, A[i].y);
    }
    return 0;
}