HackerRank Geometry – Baby Step, Giant Step

Challenge: Baby Step, Giant Step

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464724516

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/baby-step-giant-step/problem

Cerinta

You are standing at point $(0, 0)$ on an infinite plane. In one step, you can move from some point $(x_{f}, y_{f})$ to any point $(x_{t}, y_{t})$ *as long as* the [Euclidean distance](https://en.wikipedia.org/wiki/Euclidean_distance), $\sqrt{(x_{f}-x_{t})^2+(y_{f}-y_{t})^2}$, between the two points is either $a$ or $b$. In other words, each step you take must be exactly $a$ or $b$ in length.

You are given $q$ queries in the form of $a$, $b$, and $d$. For each query, print the minimum number of steps it takes to get from point $(0, 0)$ to point $(d, 0)$ on a new line.

Input Format

The first line contains an integer, $q$, denoting the number of queries you must process.	
Each of the $q$ subsequent lines contains three space-separated integers describing the respective values of $a$, $b$, and $d$ for a query.

Output Format

For each query, print the minimum number of steps necessary to get to point $(d, 0)$ on a new line.

Constraints

- $1 \le q \le 10^5$
- $1 \le a < b \le 10^9$
- $0 \le d \le 10^9$

Cod sursa

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

int solve(int a, int b, int d) {
if(d == 0) return 0;
  if(d == b || d == a) return 1;
  if(d < 2 * b) return 2;
  return d/b + (d%b==0?0:1);
}
int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string q_temp;
    getline(cin, q_temp);

    int q = stoi(ltrim(rtrim(q_temp)));

    for (int q_itr = 0; q_itr < q; q_itr++) {
        string first_multiple_input_temp;
        getline(cin, first_multiple_input_temp);

        vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));

        int a = stoi(first_multiple_input[0]);

        int b = stoi(first_multiple_input[1]);

        int d = stoi(first_multiple_input[2]);

        int result = solve(a, b, d);

        fout << result << "\n";
    }

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}