15 months ago

Akhil Rajan • 10

Martin's father goes for a jog every morning. Martin follows him several minutes later. His father starts at a position that is X1 metres away from their home and runs rectilinearly at a constant speed of V1 meters per step for N steps.

Martin is standing at X2 meters away from his home. He wonders how fast he must run at some constant speed of V2 meters per step so as to maximize F, where F equals the number of his father's footsteps that Martin will land on during his run.It is given that the first step that Martin will land on, from his starting position, will have been landed on by his father.

Note that if more than one prospective velocity results in the same number of maximum common steps, output the highest prospective velocity as V2.

Write an algorithm to help Martin calculate F and V2.

INPUT

The first line of the input consists of an integer fatherPos, representing the initial position of Martin's father(X₁).

The second line consists of an integer martinPos, representing the initial position of Martin (X2).

The third line consits of an integer velFather, representing the velocity of father(V₁).

The last line consists of integer steps , representing the no of steps taken by father(N).

OUTPUT

Print the two space-separated integers as the maximum number of common footsteps F and respective speed V2.

CONSTRAINTS

1 <= fatherPos < 10⁵

0 <= martinPos <= fatherPos

1 <= velFather <= 10⁴

1 <= steps <= 10⁴

Example

Input:

3

2

2

20

Output:

21 1

Explanation:

Martin can save a maximum of 21 common footsteps with a velocity of 1 m/steps.

13 months ago

Nimitt Arora • 0

#include <bits/stdc++.h>

using namespace std;

vector<int> commonFootSteps(int fatherPos, int martinPos, int velFather, int steps) {
    vector<int> answer(2, 0);
    vector<int> temp(steps + 1, 0);

    for (int i = 0; i <= steps; i++)
        temp[i] = fatherPos + velFather * i - martinPos;

    for (int i = 0; i <= steps; i++) {
        if (temp[i] <= 0)
            continue;

        int v2 = temp[i];
        int count = 0;

        for (int j = i; j <= steps; j++) {
            if (temp[j] % v2 == 0)
                count++;
        }

        if (answer[0] <= count) {
            answer[0] = count;
            answer[1] = v2;
        }
    }

    return answer;
}

int main() {
    int x1,x2,v,n;
    cin>>x1>>x2>>v>>n;
    vector<int> result = commonFootSteps(x1,x2,v,n);

    for (int i : result)
        cout << i << " ";

    return 0;
}