Skip to main content

Intuit

Intuit OA-4 2023

Problem Description

A company team wants to plan a group outing to a nearby location, Hilltown. All company taxis are stationed at the office. Each taxi must pick up employees from their homes, take them to Hilltown, drop them off, return them to their homes, and finally report back to the office.

The cost of each taxi trip is calculated as a base fare of Rs X plus Rs Y per kilometer traveled. Each taxi can only carry consecutive employees in the trip. This means if employee i and employee j are in the same taxi, and i < j, all employees between i and j must also be in the same taxi. A taxi can carry any number of people and will retrace the same path for the return journey.

Your task is to help the manager minimize the cost of the outing by optimizing the taxi routes.

Input Format

  • The first line contains three integers N, X, and Y, where:
    • N represents the number of employees,
    • X represents the base fare of the taxi, and
    • Y represents the additional charge per kilometer.
  • The next (N+2) lines each contain (N+2) integers, representing the distance matrix A (of size N+2 × N+2).
    • A[i][j] gives the minimum distance between location i and location j, where:
      • i = 0 represents the office,
      • i = 1 to N represents employees (from 1 to N), and
      • i = N+1 represents Hilltown.

Output Format

Print the minimum cost required for transportation.

Constraints

  • 1 ≤ N ≤ 15
  • 0 ≤ X ≤ 100000
  • 0 ≤ Y ≤ 1000

Example

Input:

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

Output:

3500

Explanation:

Since there is only one taxi, it must accommodate all the employees (1, 2, 3). These are the possible routes the taxi could take (with index 0 representing the office and index 4 representing Hilltown):

  • Route: Office → 1 → 2 → 3 → Hilltown
    • Total distance = 2 × (A[0][1] + A[1][2] + A[2][3] + A[3][4])
    • = 2 × (5 + 10 + 6 + 9) = 60 km
  • Route: Office → 1 → 3 → 2 → Hilltown
    • Total distance = 2 × (A[0][1] + A[1][3] + A[3][2] + A[2][4])
    • = 2 × (5 + 5 + 6 + 9) = 50 km
  • Route: Office → 2 → 1 → 3 → Hilltown
    • Total distance = 2 × (A[0][2] + A[2][1] + A[1][3] + A[3][4])
    • = 2 × (8 + 10 + 5 + 7) = 60 km
  • Route: Office → 2 → 3 → 1 → Hilltown
    • Total distance = 2 × (A[0][2] + A[2][3] + A[3][1] + A[1][4])
    • = 2 × (8 + 6 + 5 + 6) = 50 km

The minimum distance is 50 km.
The minimum cost = 50 km × Rs 50/km + Rs 1000 (base fare) = Rs 3500.