PROBLEM LINK:
Setter: Lavish Gupta
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
SIMPLE
PREREQUISITES:
None
PROBLEM:
There are three categories say C_1, C_2 and C_3. There will be 20 problems from each category appearing in a test. Problems in C_1 takes A minutes to complete and solving the problem gives X points. Problems in C_2 takes B minutes to complete and solving the problem gives Y points. Problems in C_3 takes C minutes to complete and solving the problem gives Z points. The total time of the test is 240 minutes. We need to find the maximum points we can achieve in the test by solving some problems.
QUICK EXPLANATION:
- Since the number of problems for each category is quite small we can solve the problem by directly iterating over the number of problems taken from each category.
EXPLANATION:
The key observation in this problem is the constraints mentioned in the problem statement. Since the number of problems in each category is quite small, the simplest way to solve this problem is by using brute-force.
Let the number of problems taken from C_1, C_2 , C_3 be T_1, T_2 and T_3 respectively. Now the set of chosen problems will be valid if total time required to solve these problems is \leq 240 i.e, T_1 \cdot A+T_2 \cdot B+T_3 \cdot C \lt 240 . The total number of points we can get is T_1 \cdot X+T_2 \cdot Y+T_3 \cdot Z.
Now brute-forcing over all possible values of C_1, C_2 and C_3 from the range [0, 20] gives the time complexity for each test case as O( 21 \cdot 21 \cdot 21 ) which will easily fit in the time limit.
TIME COMPLEXITY:
O(21^3) for each testcase.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tests;
cin >> tests;
while (tests--)
{
int A, B, C, X, Y, Z;
cin >> A >> B >> C >> X >> Y >> Z;
int ans = 0;
for (int take_a = 0; take_a <= 20; take_a++)
{
for (int take_b = 0; take_b <= 20; take_b++)
{
for (int take_c = 0; take_c <= 20; take_c++)
{
int time = take_a * A + take_b * B + take_c * C;
if (time <= 240)
{
ans = max(ans, take_a * X + take_b * Y + take_c * Z);
}
}
}
}
cout << ans << endl;
}
return 0;
}
Setter's solution
#define ll long long
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mp make_pair
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
//#include<bits/stdc++.h>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<utility>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
ll pi = acos(-1) ;
ll z = 1000000007 ;
ll inf = 100000000000000000 ;
ll p1 = 37 ;
ll p2 = 53 ;
ll mod1 = 202976689 ;
ll mod2 = 203034253 ;
ll fact[100] ;
ll gdp(ll a , ll b){return (a - (a%b)) ;}
ll ld(ll a , ll b){if(a < 0) return -1*gdp(abs(a) , b) ; if(a%b == 0) return a ; return (a + (b - a%b)) ;} // least number >=a divisible by b
ll gd(ll a , ll b){if(a < 0) return(-1 * ld(abs(a) , b)) ; return (a - (a%b)) ;} // greatest number <= a divisible by b
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
ll e_gcd(ll a , ll b , ll &x , ll &y){ if(b > a) return e_gcd(b , a , y , x) ; if(b == 0){x = 1 ; y = 0 ; return a ;}
ll x1 , y1 ; e_gcd(b , a%b , x1 , y1) ; x = y1 ; y = (x1 - ((a/b) * y1)) ; return e_gcd(b , a%b , x1 , y1) ;}
ll power(ll a ,ll b , ll p){if(b == 0) return 1 ; ll c = power(a , b/2 , p) ; if(b%2 == 0) return ((c*c)%p) ; else return ((((c*c)%p)*a)%p) ;}
ll inverse(ll a ,ll n){return power(a , n-2 , n) ;}
ll max(ll a , ll b){if(a > b) return a ; return b ;}
ll min(ll a , ll b){if(a < b) return a ; return b ;}
ll left(ll i){return ((2*i)+1) ;}
ll right(ll i){return ((2*i) + 2) ;}
ll ncr(ll n , ll r){if(n < r) return 0 ; return ((((fact[n] * inverse(fact[r] , z)) % z) * inverse(fact[n-r] , z)) % z);}
void swap(ll&a , ll&b){ll c = a ; a = b ; b = c ; return ;}
//ios_base::sync_with_stdio(0);
//cin.tie(0); cout.tie(0);
using namespace std ;
#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>
// ordered_set s ; s.order_of_key(val) no. of elements strictly less than val
// s.find_by_order(i) itertor to ith element (0 indexed)
//__builtin_popcount(n) -> returns number of set bits in n
#define pll pair<ll ,ll>
#define tll tuple<ll ,ll ,ll>
void solve()
{
ll max_t = 240 , max_q = 21 ;
ll a , b , c , x , y , z ;
cin >> a >> b >> c >> x >> y >> z ;
ll score = 0 ;
fo(i , max_q)
{
fo(j , max_q)
{
fo(k , max_q)
{
ll tot_t = (i*a) + (j*b) + (k*c) ;
ll tot_s = (i*x) + (j*y) + (k*z) ;
if(tot_t <= max_t)
{
score = max(score , tot_s) ;
}
}
}
}
cout << score << endl ;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
ll t ;
cin >> t ;
//t = 1 ;
for(ll x = 1 ; x <= t ; x++)
{
solve() ;
//cout << "Case #" << x << ": " << solve() << '\n';
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int a, b, c;
cin>>a>>b>>c;
int x, y, z;
cin>>x>>y>>z;
int ans = 0;
for(int i = 0; i < 21; i++){
for(int j = 0; j < 21; j++){
for(int k = 0; k < 21; k++){
if(i * a + j * b + k * c <= 240){
ans = max(ans, i * x + j * y + k * z);
}
}
}
}
cout<<ans<<"\n";
}
return 0;
}
Please comment below if you have any questions, alternate solutions, or suggestions. 
