CABRIDE - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef’s family has N members, and they need to reach the airport.
A cab ride for X people costs \max(200, 100\cdot X).
A cab can hold at most 4 people.

Find the minimum cost for all N people to reach the airport.

EXPLANATION:

Let’s look at the costs for sending X people in a cab.

  • X = 1: the cost is \max(200, 100) = 200.
  • X = 2: the cost is \max(200, 200) = 200.
  • X = 3: the cost is \max(200, 300) = 300.
  • X = 4: the cost is \max(200, 400) = 400.

In general, note that other than X = 1, the cost is just 100\cdot X.

This essentially means that sending a person via cab has a cost of 200 if they’re alone, and a cost of 100 if they’re with someone else.

Since we want to minimize the overall cost, clearly it’s ideal to ensure that nobody travels alone in a cab - this will ensure that each person has an effective cost of 100.

Now,

  • If N = 1, there’s only one person.
    We have no choice but to use a single cab, for a cost of 200.
  • If N \gt 1, it’s always possible to ensure that each person has a cost of 100.
    One way of doing this is: if N is odd, first send three people in one cab.
    This leaves an even number of people, so we can just send them in pairs.

So, if N = 1 the answer is 200, and in all other cases the answer is 100\cdot N.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    if n == 1: print(200)
    else: print(100*n)