PROBLEM LINK:
Author: Raja Vardhan Reddy
Tester: Felipe Mota
Editorialist: Rajarshi Basu
DIFFICULTY:
Cakewalk
PREREQUISITES:
Implementation
PROBLEM:
There exists 3 denominations, Rs 5, Rs 10 and Rs 15. Each ice-cream costs Rs 5. There are N customers. Each customer has a certain denomination with him. He buys an ice-cream from Chef only if Chef can give him change. Chef initially has no money. Can all the customers buy their ice-cream?
EXPLANATION:
Simulate the process!
Keep two counters, cnt_5 and cnt_{10}, both initially 0. When a customer comes, see if you can provide change using the two counters.
The best strategy here is to give a change of Rs 10 whenever possible, and if not possible, then give Rs 5. In some sense, Rs 5 is a more “flexible denomination” than Rs 10 – you can form both Rs 5 and 10 denominations from Rs 5, but you cannot give a change of Rs 5 if you only have Rs 10 denominations. Hence, you want to save them (i:e Rs 5) as much as possible.
If you can’t give the change using Rs 10 and Rs 5 then exit, if you can then continue processing the next customer. Don’t forget to increase the counter for whichever denomination you get after the transaction.
NOTE: We dont need a counter for Rs 15 since we cannot use it as change ever.
SOLUTIONS:
Setter's Code
//raja1999
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//std::ios::sync_with_stdio(false);
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t,t1;
cin>>t;
t1=t;
while(t--){
int n,c=0,c1=0,c2=0,i,x,a[1005];
cin>>n;
rep(i,n){
cin>>a[i];
}
rep(i,n){
x=a[i];
if(x==5){
c++;
}
else if(x==10){
if(c==0){
break;
}
else{
c--;
}
c1++;
}
else{
if(c1==0 &&c<=1){
break;
}
else if(c1!=0){
c1-=1;
}
else if(c>=2){
c-=2;
}
}
}
if(i==n){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
return 0;
}
Tester's Code
t = int(raw_input())
while t > 0:
n = int(raw_input())
q5, q10 = 0, 0
is_ok = True
coins = map(int, raw_input().split())
for coin in coins:
if coin == 5:
q5 += 1
elif coin == 10:
q10 += 1
if q5 > 0:
q5 -= 1
else:
is_ok = False
else:
if q10 > 0:
q10 -= 1
elif q5 >= 2:
q5 -= 2
else:
is_ok = False
print "YES" if is_ok else "NO"
t -= 1
Please give me suggestions if anything is unclear so that I can improve. Thanks