Chef and demonetization problem

I don’t know why i got WA, it passes the possible test cases as much as i know
https://ide.geeksforgeeks.org/fDTvxwBHtc

Problem 1
https://www.codechef.com/LTIME85B/problems/CHFMOT18

1
28 10
answer should be 3 but u are giving 6
you can use any even number in range 0…n

1 Like
#include <iostream>
#define ll long long
using namespace std;
int main(){
    int t; cin >> t;
    while(t--){
        ll s; cin >> s;
        ll n; cin >> n;
        ll l2=0,total=0;
        if(s%2==0){
            int l = s/n;
            int total1 = s-(l*n);
            if(total1!=0) cout << l+1 << "\n";
            else cout << l << "\n";
        }else{
            total = s/n;
            l2 = s-(total*n);
            if(l2!=1) total+=l2/(l2-1);
            else l2=2;
            std::cout << total+1 << "\n";
        }
    }
}

My code might help

1 Like

But why 3 ?

thanks

you can use coins of 10 10 8

1 Like

You could use two 10 and one 8

1 Like

confused!

Well if you are trying to minimize the coins used you have to use the maximum number of even valued coins possible everytime and if it is odd just add 1 coz we can use it.

1 Like

#include
using namespace std;

int main(){
int t;
cin>>t;
while(t–){
int s, n;
cin>>s>>n;
int ans = 0;
if(n==1){
cout<<s<<"\n";
continue;
}
while(s>1){
ans += (s/n);
s %= n;
n -= 2;
}
if(s>0){
ans++;
}
cout<<ans<<"\n";
}
return 0;
}

I don’t know why my code is giving TLE. It is passing all potential test cases.

1 Like

The worst case number is 10^9 so you can’t use brute force .

1 Like