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
Sample input:
5 18 24 77 176 34 144 24 426 273 628
Sample output:
1 2 4 18 2
Code (C++):
//============================================================================
// Name : almost.cpp
// Author : Francesco Laurita
// Version : 1.0
// Copyright : Francesco Laurita
// Description :
//============================================================================
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int ntest, a, c, b;
cin >> ntest;
while (ntest--) {
cin >> a;
cin >> c;
b = c / a;
if (abs((b + 1) * a - c) < abs(b * a - c)) {
b++;
}
cout << b << endl;
}
return 0;
}
Hey Francesco,
It’s cool that you put out all these solutions to the HackerCup here. Did you get qualified into the later rounds? If you have the time to write solutions for those rounds, maybe I can point CoderCharts fans on Facebook to here.
Agnes
Hi Agnes!
I’m not been able to qualified at all due to a bug of Chrome. During the qualification
round I was not able to download the input file even if the timeout on
server side started normally.
Several players reported this issues on the FB page and the admins did something
such like giving the opportunity to resubmit the solution but I was
sleeping during this time frame
Do you know if other problems are available somewhere so I can take a look?
BTW, I’m playing right now on Codercharts! Great work!
I’m not sure … I’ve been trying to find if there were people posting their solutions on their blogs or something, but it seems very few did. My husband did take part in the first 2 rounds … but he didn’t get qualified for the 3rd. If you are interested, I can ask if he can still access the problems.
Yeah, I know you’ve joined us … thanks for the support. Hope you enjoy the puzzles written up by my husband. The Facebook problems were not programming-oriented for him. BTW, Google Code Jam is in May, are you in?