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;
}