 # SMOKE - Editorial

Setter: Utkarsh Gupta
Tester: Abhinav Sharma
Editorialist: Kanhaiya Mohan

Simple

None

# PROBLEM:

There are two types of vehicles in Chefland.

• Bus has a capacity of 100 people.
• Car has a capacity of 4 people.

There are N people who want to travel. You know that a single bus emits X units of smoke while a single car emits Y units of smoke.

You want to arrange some buses and cars to carry all these N people such that total smoke emitted is minimised. Output the minimised smoke value.

# EXPLANATION:

Consider a batch of 100 people.

If we arrange buses for them, we would require only 1 bus and the total smoke emitted would be X units.

On the other hand, if all of them travel by car, we would need \frac{100}{4} = 25 cars. The total smoke emitted by cars would be 25 \cdot Y units.

It is optimal to use a bus for all these people only if X \leq 25 \cdot Y. Else, we use a car.

The total smoke emitted for the commute of these 100 people is min(X, 25 \cdot Y).

Note that for this batch 100 people, it is never optimal to use both the vehicles.

Why?

Let us assume we use 1 bus and C cars (C>0) for these 100 people. Note that using more than one bus would never be optimal as 1 bus has a capacity of 100 people.

Now, the total smoke emitted would be X + C\cdot Y. Since X + C\cdot Y >X, it is better to use only the bus instead of both bus and car.

We divide all the people into batches of 100 and calculate the answer for each batch.

For the remaining N' people (N'<100), we require either 1 bus or C = ceil(\frac{N'}{4}) cars. Minimum smoke emitted for the commute of these N' people is min(X, C \cdot Y).

The total answer would be the sum of answers of all batches of 100 people and the answer for the batch of remaining people (which is less than 100).

# TIME COMPLEXITY:

If we calculate the answer for each batch of 100 people separately, the complexity would be O(\frac{N}{100}).

However since the answer for each batch of 100 people would be the same, we can calculate the answer in O(1) for each test case.

The time complexity is O(1) per test case.

# SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;

while(t--){
int n;
cin>>n;
int x, y;
cin>>x>>y;

int smoke = 0;
while(n>=100){
int busSmoke = x;
int carSmoke = 25*y;
smoke += min(busSmoke, carSmoke);
n -= 100;
}

if(n>0){
int cars = ceil(n/4.0);
int carSmoke = cars * y;
int busSmoke = x;
smoke += min(busSmoke, carSmoke);
}

cout<<smoke<<endl;
}
return 0;
}

Tester's Solution
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T=1;
cin >> T;
while(T--){
int n,x,y;
cin>>n>>x>>y;

int ans = 10*x;
rep(i,10){
ans = min(ans, i*x+((max(0,n-100*i)+3)/4)*y);
}

cout<<ans<<el;
}
return 0;
}

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;

while(t--){
int n;
cin>>n;
int x, y;
cin>>x>>y;

int smoke = 0;

//for batches of 100
int buses = n/100;
int cars = buses * 25;
int busSmoke = buses * x;
int carSmoke = cars * y;

smoke = min(busSmoke, carSmoke);

n = n%100;

//for all people left
if(n>0){
int cars = ceil(n/4.0);
int carSmoke = cars * y;
int busSmoke = x;
smoke += min(busSmoke, carSmoke);
}

cout<<smoke<<endl;
}
return 0;
}

6 Likes

https://www.codechef.com/viewsolution/58544163
this is my solution link in c.
my code failed on some test cases, someone please help me to know why that code is not right.

You have not considered other 2 cases
i) considering only cars
ii) considering only buses
For example:
N=1000 X=1000 Y=1
It is optimal to use only cars

4 Likes
int mini(int n,int x, int y)
{
if(n<1)
return 0;
if(n==1)
return min(x,y);

int p= x * ceil((double)n/100);
int q= y * ceil((double)n/4);
if(p < q)
return x + mini(n-100,x,y);
else
return y + mini(n-4,x,y);
}


I’m wondering, Is this possible to do this question using LDA (Linear Diophantine Equation), It will be helpful for me if you share your solution based on this approach!

why this is not accepted ???
https://www.codechef.com/viewsolution/58566132

https://www.codechef.com/viewsolution/58542789

what am i missing? Its displaying WA

#include <bits/stdc++.h>
using namespace std;

int main() {
using ll = long long int;
ll t;
cin>>t;
while(t--){
ll n,i,j, x,y;
cin>>n>>x>>y;
ll carnum = n/4;
ll carpoll = carnum*y;
ll carrem = carnum%4;
ll busnum = n/100;
ll busspoll = busnum*x;
ll num1 = busnum+(n%100 > 0 ? 1 : 0);
ll num2 = carnum+(n%4 > 0 ? 1 : 0);
ll num3 = ((n%100)/4)+((n%100)%4 > 0 ? 1 : 0);
ll num4 = ((n%4) > 0 ? 1 : 0);
ll ans = min({(num1*x), busspoll+(num3*y), num2*y, carpoll+(num4*x)});
cout<<ans<<"\n";
}
return 0;
}


I don’t think it’s possible as in a linear diophantine equation ax + by = c , a, b and c are given integers and x, y are unknown integers but in the problem, we have a,b and we need to find the x,y and minimum value of c.

import math
for gagroz in range(int(input())):
n , x , y = map(int , input().split())
ans=0
if x//100 < y//4:
ans+= n//100 * x
if n%100 !=0:
ans+= min(x , math.ceil((n%100)/4)*y)
else :
ans += math.ceil(n/4)*y

print(ans)


can u tell me whats wrong in my soln

if x//100 < y//4:

here float division have to used instead of integer div
Incase if x is 199 and y is 4 then both x//100 and y//4 will be 1.

Could someone explain why my code is not working?
It has passed 3 test cases.
https://www.codechef.com/viewsolution/58597226

I’m new to programming, can someone help me with this code. I don’t know what’s wrong in it, It’s lengthy but my logic is correct, output is also coming right but on submitting it’s showing wrong. #include<stdio.h>

int main (void)
{
int t;
scanf("%d", &t);

while(t--)
{
int n,x,y;
scanf("%d" "%d" "%d", &n, &x, &y);
int sum=0;

if(x<y)
{
if(n<=100)
{
sum=x;
}

else
{
int sum1=0, sum2=0, sum3=0;
int a=n/4;
int b=n%4;
if(b>0)
{
a++;
sum1=a*y;
}
int c=n/100;
int d=n%100;
if(d>0)
{
c++;
sum2=c*x;
}
int e=n/100;
int f=n%100;
int g=f/4;
int h=f%4;
if(h>0)
{
g++;
sum3=e*x+h*y;
}
if(sum1<sum2&&sum1<sum3)
{
sum=sum1;
}
else if(sum2<sum1&&sum2<sum3)
{
sum=sum2;
}
else
{
sum=sum3;
}
}
printf("%d\n", sum);
}
else if(x>y)
{
if(n<=4)
{
sum=y;
}
else if(4<n&&n<=100)
{
int sum1=0;
int sum2= x;
int a=n/4;
int b=n%4;
if(b>0)
{
a++;
sum1= a*y;

if(sum1<sum2)
{
sum=sum1;
}
else
{
sum=sum2;
}
}

}
else
{
int sum1=0, sum2=0, sum3=0;
int a=n/4;
int b=n%4;
if(b>0)
{
a++;
sum1=a*y;
}
int c=n/100;
int d=n%100;
int e=d/4;
int f=d%4;
if(f>0)
{
e++;
sum2=c*x+e*y;
}
int g=n/4;
int h=n%4;
int i=h/100;
int j=h%100;
if(j>0)
{
i++;
sum3=g*y+i*x;
}
if(sum1<sum2&&sum1<sum3)
{
sum=sum1;
}
else if(sum2<sum1&&sum2<sum3)
{
sum=sum2;
}
else
{
sum=sum3;
}
}
printf("%d\n", sum);
}
else
{
int a=n/100;
int b=n%100;
if(b>0)
{
a++;
sum=a*x;
}
printf("%d\n", sum);
}
}
return 0;


}

i got it now. thanks for the help

Try this testcase
1
150 100 25
Output should be 200 (2 buses)
But here the code output is 425

1 Like

Why is this wrong?
https://www.codechef.com/viewsolution/58646653

Try some dry run in your code

1 Like

1
1000 1000 100
Check for this input
Output should be 10000

1 Like

Oh ok, I got it… My bad
Thank You.

I am unable to find error in my logic. My code is passing some of testcases and rest are giving ‘WA’. Please someone help me to find out what’s wrong in my logic.

#include <bits/stdc++.h>
using namespace std;
int mini = INT_MAX ;

int smoke (int i , int n , int sum , int bus , int car , vector& dp ){
if(i>=n ){
return sum ;
}
if(dp[i]!=-1) {
return dp[i] ;
}
int l = smoke(i+4 , n , sum+car , bus , car,dp );
int r = smoke(i+100 , n , sum + bus , bus ,car , dp);
return dp[i]=(min(l,r));
}
int main() {