How can we show that the optimal integer point is always within distance two of an intersection? During the contest I checked the 4 closest integer points of each intersection (so the floors, ceilings), and gave up when that didn’t work.
I’m not sure if I can show the proof rigorously. When I meant a distance of 2 I meant manhattan distance “at most 2”. I think it works because of the plane-like shape of the objective function in three dimensions.
As for why distance “2” works, I think it it’s because the intersections are integers and I guessed that if you graphed these lines, you’d have some point within that range that falls inside the “constraint polygon”.
you solved it like a pro!!
1 Like
Nice problem. In the setter’s solution in the line :
long long useC = min(canC, req) ;
Is min() required ?. I think it can be directly assigned to canC.
1 Like
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press “Run” button to compile and execute it.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long int n,e,h,a,b,c,MaxItem,sum;
vector<long long int> v1;
long long int t;
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>n>>e>>h>>a>>b>>c;
if(e%2 !=0 && h%3 !=0)
sum = e/2 + h/3 + 1;
else
{
sum = e/2 + h/3;
}
int minItem = min(e,h);
if(e == minItem)
{
MaxItem = max(min(e,h)+(h-e)/3,sum);
}
else if( h==minItem)
{
MaxItem = max(min(e,h)+(e-h)/2,sum);
}
if(n > MaxItem)
{
cout<<-1<<endl;
}
else
{
//only omellete
long long int cost1 =1000000;
if(e/2 >= n)
{
cost1 = n*a;
}
//only shake
long long int cost2 =1000000;
if(h/3 >= n)
{
cost2 = n*b;
}
// only cake
long long int cakes = min(e,h);
long long int cost7 =100000;
if(cakes >=n)
{
cost7 = n * c;
}
// milk shake and omlette
long long int omlette = e/2;
long long int shake = h/3;
long long int cost3 =1000000;
long long int cost4 =1000000;
if(omlette + shake >=n)
{
if(a > b && (n-(h/3))>=0)
{
cost3 = (n-(h/3)) * a + (h/3) * b;
}
else if(a <= b && (n-(e/2))>=0)
{
cost3 = (n-(e/2)) * b + (e/2) * a;
}
}
// omellete and cake
long long int cost5 =1000000;
for(int j=1 ;j<=min(e,h);j++)
{
if((e-j)/2 >= (n-j) && (n-j)>=0)
{
cost5 = min(j*c+(n-j)*a,cost5);
//cout<<cost5<<endl;
}
}
long long int cost8 = 1000000;
for(int j=1;j<=min(e,h);j++)
{
if((e-j)/2 + (h-j)/3 >= (n-j) && (n-j)>=0)
{
if(a > b && (n-j-((h-j)/3)) && h-j>=0)
{
cost8 = min(cost8,j*c+(n-j-((h-j)/3))*a+((h-j)/3)*b);
//cout<<cost8<<" "<<j<<" "<<(n-j-((h-j)/3))<<" "<<((h-j)/3)<<endl;
}
if(b >=a && (n-j-((e-j)/2)) && (e-j)>=0)
{
cost8 = min(cost8,j*c+(n-j-((e-j)/2))*b+((e-j)/2) *a);
//cout<<cost8<<" "<<j<<" "<<(n-j-((e-j)/2))<<" "<<((e-j)/2)<<endl;
}
}
else
{
if((e-j)%2 !=0 && (h-j)%3 != 0)
{
if((e-j)/2 + (h-j)/3 + 1 >= (n-j) && (n-j)>=0)
{
if(a > b && (h-j)>=0 && (n-j-((h-j)/3))>=0)
{
cost8 = min(cost8,(j+1)*c+(n-j-((h-j)/3))*a+((h-j)/3) *b);
}
if(b >= a && (n-j-((e-j)/2)) && (e-j)>=0)
{
cost8 = min(cost8,(j+1)*c+(n-j-((e-j)/2))*b+((e-j)/2) *a);
}
}
}
}
}
v1.push_back(cost1);
v1.push_back(cost2);
v1.push_back(cost3);
v1.push_back(cost4);
v1.push_back(cost5);
//v1.push_back(cost6);
v1.push_back(cost7);
v1.push_back(cost8);
sort(v1.begin(),v1.end());
//cout<<cost1<<" "<<cost2<<" "<<cost3<<" "<<" "<<cost4<<" "<<cost5<<" "<<cost6<<" "<<" "<<cost7<<" "<<cost8<<endl;
//cout<<mp[c]<<" "<<mp[o]<<" "<<mp[m]<<endl;
//cout<<a<<" "<<" "<<b<<" "<<c<<endl;
for(int k=0;k<v1.size();k++)
{
if(v1[k] != 1000000)
{
cout<<v1[k]<<endl;
break;
}
}
cost1=1000000;
cost2=1000000;
cost3=1000000;
cost4=1000000;
cost5=1000000;
//cost6=1000000;
cost7=1000000;
cost8=1000000;
v1.clear();
}
}
}
can anyone please help where I am geting wrong.I have tried every possible arrangement…
You are really smart brother 
1 Like
yeah, same question
Yes, if I understand correctly, it is required. If possible we want to take canC, but if N is such that we don’t need to serve that many meals, we just serve as many as required.
This one is all about some basic permutation.
Which element to perform it on is the important part.
As both Om (Omelette) and Mk (Milkshake) are dependent on Ck (Cake), it makes sense to perform the permutation with respect to Ck.
At every step in the permutation, I ran a weird variation of binary search to find the optimal solution.
A great Problem Statement for Div. 3.
My Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
int t;
cin>>t;
while(t--){
ll n,e,h,a,b,c;
cin>>n>>e>>h>>a>>b>>c;
ll cake=min(e,h);
ll omlette=(e-cake)/2;
ll milkshake=(h-cake)/3;
ll cost=INT_MAX;
if(cake+omlette+milkshake<n){
cout<<-1<<endl;
continue;
}
for(ll i=0;i<cake;i++){
if(a>b){
milkshake=min(n-i,(h-i)/3);
if((n-i-milkshake)>(e-i)/2){
continue;
}
omlette=n-i-milkshake;
cost=min(omlette*a+milkshake*b+i*c,cost);
}
else{
omlette=min(n-i,(e-i)/2);
if((n-i-omlette)>(h-i)/3){
continue;
}
milkshake=n-i-omlette;
cost=min(omlette*a+milkshake*b+i*c,cost);
}
}
cout<<cost<<endl;
}
return 0;
}
This is my code and its pass test cases but its showing WA during submission
Your code is failing in this test-case :
1
3 5 2 3 2 1
Expected O/P :
5
Your O/P :
7
What if the cost of cake is more than omelette and chocolate milkshake? For example if the input is :
1
4 5 4 2 3 4
The Expected output is : (22+13+14)=11
But, when we fix the cake, the answer will be 44=16