Algoogle

Algorithm for Programming Contest

PKU 3039 Close Encounter

Category: PKU Tag: implementation

Close Encounter

問題概要


解法


謎探索で通ってしまった.
分母をすべて試す.
分母が決まると入力に一番近くなる分子が出せる.
で, その値が使えるとは限らないので一応前後も確認しておく.
前後10個ずつやったらTLEしたので1個ずつ見たら通った.

コード


(3039.cpp) download
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
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

const int M = 32767;

int num, den, anum, aden;
double diff;

int main(){
    scanf("%d%d", &num, &den);
    diff = 1e9;

    for(int d = 2; d <= M; d++){
        if(d == den) continue;
        int nn = num * d / den;
        for(int n = max(1, nn-1); n <= min(d-1, nn+1); n++){
            if(__gcd(n, d) > 1) continue;
            double di = abs(1. * num / den - 1. * n / d);
            if(di < diff) {
                diff = di;
                anum = n;
                aden = d;
            }
        }
    }
    printf("%d %d\n", anum, aden);
    return 0;
}

Comments