 < Back to forum

### Taxi problem(Codeforces)

I am getting a TLE in the problem- Taxi

Following is my code:

``` #include

using namespace std;

int main()

{ int n,c,i,j,p;

cin>>n; int car[n],g[n];

``````for (i=0;i<n;i++)
cin>>g[i];
sort(g,g+n, greater<int>());
c=0;
car=g;
for (i=1;i<n;i++)
{
p=0;
for (j=0;j<=c;j++)
{
if (4-car[j]>=g[i])
{
car[j]+=g[i];
p=1;
break;
}
}
if (p==0)
{
c++;
car[c]=g[i];
}
}
cout<<c+1;
return 0;
``````

} ``` Hope u help, Thanks!!!

Asked by: Anonymous on Dec. 15, 2020, 11:38 a.m. Last updated on Dec. 15, 2020, 11:47 a.m.

# include

using namespace std;

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

``````int ele;
unordered_map<int, int> m;
for(int i = 0; i < n; i++) {
cin >> ele;
m[ele]++;
}

int ans = m;
ans += min(m, m);
int val = min(m, m);
m -= val;
m -= val;
if(m > 0)
ans += m;
ans += (m / 2);
m %= 2;
ans += m / 4;
m %= 4;

if(m > 0 || m > 0){
if(m == 1 && m == 3)
ans += 2;
else
ans += 1;
}
cout << ans << "\n";
return 0;
``````

}

Another way to do it.. try it if you want..

Preview

##### Enter your comment details below:

Preview

The reason behind TLE is, that you are iterating over every previous car, (even if that car is already filled). But what I think is, you have missed a crucial point.

The car has a maximum capacity of 4. You want every car(if possible) to be completely filled, in order to use minimum cars. Take an example, you have 3 person, already in the car, so, you need just 1 more person. And, if you have 2 person in the car, you either need 2 more person (in a single group), or 2 groups of single person each.

So, what if you had the count of, "what is the number of groups with x students in it". Here 1<=x<=4. You can easily manipulate this data, to "pair up" groups of x students with groups of 4-x students to make a car seating.

Try to think on this approach now, and ask again, if there is a query. 😃

mahawarvishal10 last updated on Dec. 15, 2020, noon

Yaa, I did similar.

Supposing G1-(1 member team), G2-(2 member team), G3-(3 member team), G4-(4 member team).

Now I seated each G4 group in separate cars (max. capacity is 4). Each G3 group in separate cars for the time being. Then 2 different G2 teams where seated together in a car. Now the G1 members were seated with G3 member's car having vacancy 1, with G2 member's car (if they have vacant capacity 2) and the rest G1 teams if any amongst themselves.

Its my code:

# include

using namespace std;

int main()

{

``````long long int n,c1,c2,c3,c4,g,car,i;
cin>>n;
c1=c2=c3=c4=0;
for (i=0;i<n;i++)
{
cin>>g;
if (g==1)
c1++;
else if (g==2)
c2++;
else if (g==3)
c3++;
else if (g==4)
c4++;
}
car=c4+c3+(c2/2)+(c2%2);
c1=c1-c3;
if (c1>0 && c2%2==1)
{
c1=c1-2;
}
if (c1>0)
{
if (c1%4==0)
c1=c1/4;
else c1=(c1/4)+1;
}
if (c1<0)
c1=0;
car+=c1;
cout<<car;
return 0;
``````

}

Thanks for the suggestion!!!

akshaydgp2015 last updated on Dec. 15, 2020, 8:01 p.m.

##### Instruction to write good question
1. 1. Write a title that summarizes the specific problem
2. 2. Pretend you're talking to a busy colleague
3. 3. Spelling, grammar and punctuation are important!