Submit Best Submissions All Submissions

311. Swim in the Red Sea

Problem Statement:
Mohamed Mahmoud Abd El-Wahab (AKA Fegla) the head of the scientific committee in the ACPC, a former ICPC world finalist and a coach for many Arab teams. The coach had many teams participating in the ACPC 2013 in Sharm El-Sheikh. The contestants requested from the coach a break to swim in the Red Sea. The coach agreed but under one condition: he gave the N contestants N problems and said if each one of them solved one problem, they can take a break. Given the time needed for each contestant to solve each problem, help the contestants to assign one problem to each one of them to minimize the time needed for them to achieve the goal requested by the coach. All the contestants will start solving the problems assigned to them at the same time, so the time needed to achieve the coach's goal is the time taken by the slowest contestant to solve his/her problem.

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100). The first line of each test case will be a single integer N, the number of the problems and contestants (1 ≤ N ≤ 10). Followed by a matrix of (N * N) integer numbers where element j in row i is the time (in minutes) needed for contestant i to solve problem j, (1 ≤ cell(i,j) ≤ 103).

Output Format:
For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed by a space then X where X is minimum time needed to solve all the problems.

Sample Input:
1 5 1 2 3 4 5 3 2 1 9 8 9 8 7 6 5 5 4 3 2 1 4 3 2 1 5

Sample Output:
Case 1: 5

- The best assignment of problems to contestants is: 1 3 5 2 4 with times: 1 1 5 4 5. Therefore the minimum time is 5.

Added by: ahmed_aly
Added at: 2014-10-25 09:00:00 UTC
Time Limit: 3 seconds
Partial score: No
Source:ACM Oman Collegiate Programming Contest 2014