Problem A: Marbles
Setter: ankit_907
Tester: aarya10, ronkar
Difficulty:
CAKEWALK.
Question:
Sang-woo and Abdul Ali are teammates. Sang-woo has marbles each of worth a \textit{won} and Abdul has marbles each of worth b \textit{won}.
\textit{won} is the currency of South Korea.
Their task is to buy a piggy bank, whose cost can be any even number greater than or equal to X.
Find the minimum number of marbles required to buy it.
NOTE: They dont have to minimise the total cost.
Quick Explanation:
Since, we have to only minimise the number of marbles in total, the optimal approach should be to use as many marbles having a greater value as possible. But since we require an even value at the end, we would have to handle a few edge cases like using one smaller valued marble instead of 2 larger valued marbles, to get a value \geq X
Detailed Explanation:
Since we have to get an even value \geq X, we can have X=X+1 if its odd.
Without loss of generality, let us assume a \geq b - since we can swap the values at our comfort.
We would first try to make the largest value \leq X, using only marbles worth a. Let’s name this value as val, and the number of marbles required to get ths value be marbles. A few cases arise:
- Case 1: (val==X) - We print the value of marbles since our goal is achieved.
-
Case 2: ((val \%2==1) || (a\%2==0)) - If the value we have now is an odd number, or if the value of a was even, we can use another a valued marble to make val \geq X.
Note: val being odd implies that a was odd, and a being even implies val was even.
In both the cases the final number of marbles required would be marbles+1 - Case 3: ((val\%2==0)\&\&(X-val\leq b)) - This is the only case when we would have to use a marble worth b. Since val is even ( odd val has already been considered in the previous case), if b is even and sufficient enough to touch X, we can use b comfortably. Hence, the total mables in use would also be marbles+1.
- In all other cases, we can be assured that the answer is marbles+2. Since we can use 2 marbles worth a to get past X, with an even value.
Time Complexity:
\> O(1) per testcase.
Setter's Code
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long
#define lld long double
#define vc vector<ll>
#define pb push_back
#define all(a) a.begin(),a.end()
const ll MOD=(1e9 +7);
typedef pair<ll,ll>pairs;
ll power(ll a, ll b){ll res=1;a=a%MOD;while(b>0){if(b&1){res=(res*a)%MOD;b--;}a=(a*a)%MOD;b>>=1;}
return res;}
int main() {
// your code goes here
std::ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
ll t,n,i,j,k,c,f;
cin>>t;
for(int tc=1;tc<=t;tc++){
ll a,b,X;
cin>>a>>b>>X;
if(X&1)X++;
if(a<b)
swap(a,b);
ll marbles=X/a;
ll val=marbles*a;
if(val==X)
cout<<marbles<<"\n";
else{
if((val&1)||a%2==0)
cout<<marbles+1<<"\n";
else if((b%2==0)&&(X-val<=b))
cout<<marbles+1<<"\n";
else cout<<marbles+2<<"\n";
}
}
return 0;
}
Tester's Code
// I solemnly swear that I am upto no good //
#include <bits/stdc++.h>
using namespace std;
#define sub freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);
#define ll long long
#define ull unsigned long long
#define ld long double
#define ttime {cerr << '\n'<<"Time (in s): " << double(clock() - clk) * 1.0 / CLOCKS_PER_SEC << '\n';}
#define helpUs template<typename T = ll , typename U = ll>
#define helpMe template<typename T = ll>
#define pb push_back
#define sz(x) (int)((x).size())
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define all(x) (x).begin(),(x).end()
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define pr(x) cout << #x " = " << (x) << "\n"
#define mp make_pair
#define ff first
#define ss second
#define YY cout<<"Yes"<<endl
#define NN cout<<"No"<<endl
#define ppc __builtin_popcount
#define ppcll __builtin_popcountll
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key and find_by_order
const long long INF=1e18;
const long long N=200005;
const long long mod=1000000007; // 998244353, 2971215073, 1000050131, 433494437
#define endl "\n"
#define int ll
typedef pair<ll,ll> pairll;
typedef map<ll,ll> mapll;
typedef map<char,ll> mapch;
typedef vector<ll> vll;
mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
helpUs class comp{public:bool operator()(T a, U b){return a>b;}};
helpUs istream& operator>>(istream& aa, pair<T,U> &p){aa>>p.ff>>p.ss;return aa;}
helpMe ostream& operator<<(ostream& ja, vector<T> &v){for(auto it:v)ja<<it<<" ";return ja;}
helpMe istream& operator>>(istream& aa, vector<T> &v){for(auto &it:v)cin>>it;return aa;}
helpUs ostream& operator<<(ostream& ja, pair<T,U> &p){ja<<p.ff<<" "<<p.ss;return ja;}
ll n,k,tt=1;
void solve(){
string s,t;
// cin>>s;
// n=s.size()
ll a,b,x;
cin>>a>>b>>x;
if(a<b)
swap(a,b);
assert(x<=1000000000000 and x>=1);
assert(min(a,b)>=1 and max(a,b)<=1000000000);
ll cnt1=(x+a-1)/a;
if((cnt1*a)%2==0){
cout<<cnt1<<endl;
}
else{
ll y=(cnt1-1)*a + b;
if(y>=x and y%2==0){
cout<<cnt1<<endl;
}
else{
cout<<cnt1+1<<endl;
}
}
}
signed main(){
fast;
ll t=1;
#ifndef ONLINE_JUDGE
sub;
#endif
// clock_t clk = clock();
// pre();
cin>>t;
assert(t>0 and t<=100000);
while(t--)
solve();
// ttime;
return 0;
}
// Mischief Managed //
Hope you enjoyed solving the question !
Do feel free to share your feedbacks, discussing the question in the comments.
You can also head over to our forum AskREC in case of any ambiguites
Thank You !