Skip to main content

Intuit

Intuit OA 2023 - Team Outing


A team at Intuit wishes to go on a Team Outing. They planned to go to a nearby location, Coorg. All the Intuit cabs are stationed at the Intuit office. The cab(s) need to pick up employees from their respective locations, take them to Coorg, drop them back, and report at the Intuit Office.
The cost of each cab is Rs X as base fare + Y Rs/km. A cab can accommodate only consecutive set of employees, which means if employees i and j are present in the cab and i < j, then all employees from i to j need to be in this cab. Assume a cab can accommodate any number of people and should retrace the same path for returning.
Help the manager to minimize the cost of the team outing.

Input Format

  • The first line contains three spaced integers N X Y, denoting the number of employees, the base fare of the cab, and the additional charge per km, respectively.
  • The next N+2 lines, each with N+2 spaced integers, denote rows of the distance matrix A(N+2 × N+2).
  • A(i,j) in the distance matrix gives the minimum distance between location i and location j, where:
    • i = 0 corresponds to Intuit Office.
    • i = 1 to N corresponds to employees (1 to N).
    • i = N+1 corresponds to Coorg.

Output Format

Print the minimal cost required for transportation.

Constraints

  • (1 <= N <= 15)
  • (0 <= X <= 100000)
  • (0 <= Y <= 1000)

Example

Sample Input:

3 1000 50
0 5 8 9 10
50 10 5 6
8 10 0 6 9
9 5 6 0 7
10 6 8 7 0

Sample Output:

3500

Explanation:

Single Cab:

Since we have only one cab, it needs to accommodate all the employees 1, 2, 3. Following are the possible paths the cab can choose (indices of Intuit and Coorg being 0 and 4, respectively):

  1. Path: Intuit → 1 → 2 → 3 → Coorg
    Total Distance = 2 × (A[0][1] + A[1][2] + A[2][3] + A[3][4])
    = 2 × (5 + 10 + 6 + 9) = 60 km
  2. Path: Intuit → 1 → 3 → 2 → Coorg
    Total Distance = 2 × (A[0][1] + A[1][3] + A[3][2] + A[2][4])
    = 2 × (5 + 5 + 6 + 9) = 50 km
  3. Path: Intuit → 2 → 1 → 3 → Coorg
    Total Distance = 2 × (A[0][2] + A[2][1] + A[1][3] + A[3][4])
    = 2 × (8 + 10 + 5 + 7) = 60 km
  4. Path: Intuit → 2 → 3 → 1 → Coorg
    Total Distance = 2 × (A[0][2] + A[2][3] + A[3][1] + A[1][4])
    = 2 × (8 + 6 + 5 + 6) = 50 km

Minimal distance = 50 km.
Minimal Cost = 50 km × Rs 50/km + Rs 1000 (base fare) = Rs 3500.