MINCOINS - Editorial

prakhar_87 · March 18, 2022, 3:54pm

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Manan Grover
Editorialist: Prakhar Kochar

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef has infinite coins in denominations of rupees 5 and rupees 10.

Find the minimum number of coins Chef needs, to pay exactly X rupees. If it is impossible to pay X rupees in denominations of rupees 5 and 10 only, print −1.

QUICK EXPLANATION:

If X is divisible by 10, minimum coins required are \frac{X}{10}
If X is divisible by 5 and not by 10, minimum coins required are \lfloor \frac{X}{10} \rfloor + 1
If X is not divisible by 5 it is impossible to pay exactly X rupees, therefore output -1

EXPLANATION:

Given that Chef has infinite coins in denominations of rupees 5 and rupees 10.

Chef needs to pay exactly X rupees using above denominations.

Suppose Chef selects A coins of 5 and B coins of 10 to pay exactly X rupees. The equation that will follow is 5 \cdot A + 10 \cdot B = X.

The above equation can also be written as A + 2 \cdot B = \frac{X}{5} .

Observation 1
Chef can pay exactly X rupees only if X is divisible by 5 because A + 2 \cdot B will always be a positive integer. If X is not divisible by 5, output -1

Observation 2
In order to minimize the number of coins used, we needs to maximize the value of B (number of 10 rupees coins used) and minimize the value of A (number of 5 rupees coins used). Following cases are possible

X is divisible by 10

Maximum 10 rupees coins used = B_{max} = \frac{X}{10}
Minimum 5 rupees coins used = A_{min} = 0
Total minimum coins used = B_{max} + A_{min} = \frac{X}{10}

X is divisible by 5 but not divisible by 10

Maximum 10 rupees coins used = B_{max} = \lfloor \frac{X}{10} \rfloor
Minimum 5 rupees coins used = A_{min} = 1
Total minimum coins used = B_{max} + A_{min} = \lfloor \frac{X}{10} \rfloor + 1

X is not divisible by 5

Not possible to pay exactly X rupees (Observation 1), therefore output -1

\lfloor N \rfloor is floor(N) which represents the largest integer less than or equal to N.

Examples

X = 20; (1^{st} case is followed)
B_{max} = \frac{20}{10}; A_{min} = 0; B_{max} + A_{min} = \frac{20}{10} = 2
X = 15; (2^{nd} case is followed)
B_{max} = \lfloor \frac{15}{10} \rfloor; A_{min} = 1; B_{max} + A_{min} = \lfloor \frac{15}{10} \rfloor + 1 = 2
X = 97; (3^{rd} case is followed)
Not possible to pay exactly 97 rupees, therefore output -1

TIME COMPLEXITY:

O(1) for each test case.

SOLUTION:

Setter's Solution

//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
void solve()
{
    int x=readInt(1,1000,'\n');
    if(x%5!=0)
        cout<<-1<<'\n';
    else
        cout<<(x+5)/10<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=readInt(1,1000,'\n');
    //cin>>T;
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Tester's Solution

 #include <bits/stdc++.h>
using namespace std;

long long readInt(long long l, long long r, char endd) {
    long long x = 0;
    int cnt = 0;
    int fi = -1;
    bool is_neg = false;
    while (true) {
        char g = getchar();
        if (g == '-') {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if ('0' <= g && g <= '9') {
            x *= 10;
            x += g - '0';
            if (cnt == 0) {
                fi = g - '0';
            }
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
 
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if (g == endd) {
            assert(cnt > 0);
            if (is_neg) {
                x = -x;
            }
            assert(l <= x && x <= r);
            return x;
        }
        else {
            assert(false);
        }
    }
}
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  int t;
  t = readInt(1, 1000, '\n');
  while(t--){
    int x;
    x = readInt(1, 1000, '\n');
    if(x % 5){
      cout<<-1<<"\n";
    }else{
      cout<<((x / 5) + 1) / 2<<"\n";
    }
  }
  return 0;
}

Editorialist's Solution

/*prakhar_87*/
#include <bits/stdc++.h>
using namespace std;

#define int long long int
#define inf INT_MAX
#define mod 998244353

void f() {
    int x; cin >> x;
    if (x % 5 != 0) cout << "-1\n";
    else {
        if (x % 10 == 0) cout << x / 10 << "\n";
        else if (x % 5 == 0) cout << (x / 10) + 1 << "\n";
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) f();
}

tarun2790 · February 13, 2024, 1:03pm

To solve this problem, we can use a greedy approach. Since we want to minimize the number of coins used, we should prioritize using coins of higher denominations whenever possible.

Here’s the algorithm:

If the total amount is not divisible by 5, it’s impossible to form the sum using only coins of denominations 5 and 10. Return -1.
Initialize a variable to count the number of coins.
While the total amount is greater than or equal to 10, subtract 10 from the total amount and increment the count of coins used.
After step 3, if the remaining amount is not zero and it’s not divisible by 5, it’s impossible to form the sum using only coins of denominations 5 and 10. Return -1.
Count the number of coins of denomination 5 needed to form the remaining amount.
Return the total count of coins.

Here’s the Python code implementing the above algorithm:

def min_coins_needed(X):
    if X % 5 != 0:
        return -1
    
    count = 0
    
    # Use as many 10 rupee coins as possible
    while X >= 10:
        X -= 10
        count += 1
    
    # If there's still some amount left
    if X % 5 != 0:
        return -1
    
    # Count the number of 5 rupee coins needed
    count += X // 5
    
    return count

# Example usage
X = 28
print("Minimum number of coins needed:", min_coins_needed(X))  # Output: 6

This algorithm runs in constant time because it performs a fixed number of operations regardless of the input value.

rammuchhal26 · May 10, 2024, 11:15am

#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
    int T,X;
    cin>>T;
    
    while(T-->0){
        cin>>X;
        if(X%5 == 0){
           int coinsOf10 = X/10 ;
           int coinsOf5 = ((X - (coinsOf10*10))/5);
           cout<<coinsOf10+coinsOf5<<endl;
        }
        else cout<<-1<<endl;
    }
}

shadow_willow · August 2, 2024, 4:00am

this is my solution of [MINCOINS - Editorial]

MINCOINS - Editorial

include <bits/stdc++.h>

using namespace std;

int main() {
// your code goes here

int t;
cin >> t;
while (t--) {

    int x;
    cin >> x;

    if (x % 5 == 0) {
        int a = x / 10;
        int b = x / 5;
        if (x % 2 == 0) {

            cout << min(a, b) << endl;

        }
        else {
                cout<<min(a,b)+1<<endl;
        }


    }
    else {
        cout << -1 << endl;
    }
}

return 0;

}