Facebook Hacker Cup Test Round Almost


For two integers a and c, we define a and a third integer b to be almost factors of c by choosing the minimal b that minimizes |ab-c|. Your task will be to determine b given a and c.

Input
Your input file will consist of a single integer N, the number of test cases in the file, followed by N pairs of integers a and c. All tokens in the input will be separated by some whitespace.

Output
Your output should consist of N newline-separated integers, each one representing b for the corresponding pair (a, c) in the input.

Constraints
5 ≤ N ≤ 20
1 ≤ a, c ≤ 1010

———————————————

#define _CRT_SECURE_NO_WARNINGS
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cfloat>
#include <ctime>
#include <climits>
using namespace std;

typedef long long int64;
typedef unsigned long long uint64;

template<typename T> int size(const T& c) { return int(c.size()); }
template<typename T> T abs(T x) { return x < 0 ? -x : x; }
template<typename T> T sqr(T x) { return x*x; }
template<typename T> bool remin(T& x, const T& y) { if (x <= y) return false; x = y; return true; }
template<typename T> bool remax(T& x, const T& y) { if (x >= y) return false; x = y; return true; }

#define FOR(i, a, b) for (int i(a), _b(b); i <= _b; ++i)
#define FORD(i, a, b) for (int i(a), _b(b); i >= _b; –i)
#define REP(i, n) for (int i(0), _n(n); i < _n; ++i)
#define REPD(i, n) for (int i((n) – 1); i >= 0; –i)

int main() {
freopen(“input.txt”, “rt”, stdin);
freopen(“output.txt”, “wt”, stdout);

int t;
scanf(“%d”, &t);
while (t –> 0) {
int64 a, c;
scanf(“%lld%lld”, &a, &c);
int64 b = c/a;
if (abs((b+1)*a-c) < abs(b*a-c)) ++b;
printf(“%lld\n”, b);
}
}


Leave a Reply

Your email address will not be published. Required fields are marked *