STAG - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest

Author: Arihant Jain
Tester: Aniket Sood, Arihant Jain
Editorialist: Aniket Sood

DIFFICULTY:

EASY

PREREQUISITES:

Greedy, Implementation, maths

PROBLEM:

Steve has to kill hydra, and he does with a gun but with a condition. He has to hit him n bullets but he can fire 1 or 2 bullets in each move and he also wants the number of moves to be an integer multiple of k otherwise gun will explode.

QUICK EXPLANATION:

As each move is either one or two bullets so we find the necessary moves to make up the sum of bullets to n, by doing so we now just have to find how the moves with 2 bullets can be split into 2 moves of 1 bullet each.

EXPLANATION:

  1. So the very first case will be to remove the cases with n less than m by returning answer -1, because the first integer multiple will be the number m itself and the maximum moves which we can make is n itself by taking all the ones in the moves (1,1,1,....,n) which will never add up to an integer multiple of m thus -1.
  2. Now we will calculate the minimum number of moves that add up to n by taking 2 all the times(if n is even and a last one if n is odd) which will be d = ceil(n/2). Now if m is greater than or equal to d then the answer will be m itself because we can always arrange the (n/2) 2's and split some of the 2s into 1s to get the answer to m.
  3. If m less than d then we have to make the moves to a multiple of m greater than itself but less than n, which will be ceil(d/m) * m, and if this is greater than n then -1.

Time Complexity: O(T*1)
T = no of testcases

SOLUTIONS:

Tester's Solution 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
    //#ifndef ONLINE_JUDGE
    //	freopen("input.txt","r", stdin);
    //	freopen("output.txt","w",stdout);
    //#endif
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m,t;
    cin>>t;
    while(t--){
    cin >> n >> m;
    if (n < m)
    {
        cout << -1<<"\n";
    }
    else
    {
        int d = (n + 1) / 2;
        if (m >= d)
        {
            cout << m<<"\n";
        }
        else
        {
            int x = (d + m - 1) / m;
            if (x * m <= n)
            {
                cout << x * m<<"\n";
            }
            else
            {
                cout << -1<<"\n";
            }
        }
    }
    }
}