PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Tester: Satyam, Utkarsh Gupta
Editorialist: Devendra Singh
DIFFICULTY:
To be calculated
PREREQUISITES:
None
PROBLEM:
There are N items in a shop. You know that price of i^{th} item is A_i. You want to buy all the N items.
There is also a discount coupon which costs X Rs and reduces Y Rs from every item (If price of any item is \leq Y, then it becomes free).
Determine whether he should buy the discount coupon or Not.
Chef will buy discount coupon if and only if Total price he pays after buying the discount coupon is strictly less than the price he pays without buying discount coupon.
EXPLANATION:
Let sum1 represent the sum of all N items in the shop. Let sum2 represent the cost of all the items reduced by Y (If price of any item is \leq Y, it’s cost becomes 0).
\therefore sum2= \sum_{i=1}^{N} max(0, cost\: of\: i^{th}\: item-Y)
A discount coupon costs X Rs. Chef should buy a discount coupon if sum2+X< sum1 otherwise he should not buy a coupon.
TIME COMPLEXITY:
O(N) or 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 n=readInt(1,100,' ');
int X=readInt(1,100000,' ');
int Y=readInt(1,100000,'\n');
int A[n+1]={0};
int withoutdisc=0,withdisc=X;
for(int i=1;i<=n;i++)
{
if(i==n)
A[i]=readInt(1,100000,'\n');
else
A[i]=readInt(1,100000,' ');
withoutdisc+=A[i];
withdisc+=(max(A[i]-Y,0));
}
if(withdisc<withoutdisc)
cout<<"COUPON\n";
else
cout<<"NO COUPON\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');
while(T--)
solve();
assert(getchar()==-1);
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n, sum1 = 0, sum2 = 0, x, y;
cin >> n >> x >> y;
vll v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i], sum1 += v[i];
sum2 += max(0, v[i] - y);
}
if (sum1 > sum2 + x)
cout << "COUPON\n";
else
cout << "NO COUPON\n";
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}