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 |abc|. 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 (ac) in the input.

Constraints

5  N – 20
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;
}

Bookmark and Share

3 Responses to “Facebook Hacker Cup – Almost solution (Facebook Hacker Cup Test Round)”

  1. 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

  2. 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?

Leave a Reply

(required)

(required)

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

© 2013 Francesco Laurita' s blog Suffusion theme by Sayontan Sinha