Code submission mechanism: Include source code (single file .c/.cpp/.py) in your submission ZIP file to Blackboard. Include your PSID and Submission ID from the on-line judge system. Your code must only read from stdin and write to stdout.
We will be compiling and running your submitted code. We may use test cases that are not given to you.
For your convenience, a Linux sandbox environment with starter code can be found sandbox
We are given an integer array numbers
where numbers[i]
is the i-th number. We assign the n
numbers
to k
groups. Each number is assigned to exactly one group. Find the assignment
such that the maximum sum of the groups is minimized.
Return the minimum maximum sum.
The input consists of two lines; the second line is the
numbers
array; the first line has the length of the numbers array
n
and number of groupsk
. Output should be a
single number that is the minimum maximum sum among the groups.
Example 1
Input: 3 3 3 2 3 Output: 3 Explanation: Assigning each number to each worker leads to maximum sum 3. No other assignment can have lower maximum sum.
Example 2
Input: 5 2 1 2 4 7 8 Output: 11 Explanation: Assignment: group 1: 1,2,8, sum: 11 group 2: 4,7, sum: 11 No other assignments can be lower maximum sum.
Given a m * n
matrix, your task is to compute a path
from any element on the 1 st column to any element on the last column
at minimal cost. The path consists of several steps, each step is
moving from column j
to column j+1
in an
adjacent (horizontal or diagonal) row. The first row and the last row
are considered as adjacent rows. The cost of a path is the sum of visited
integers.
The two slightly different matrices are shown in figure below. The minimum cost path is illustrated in the figure and the 2 nd path takes advantage of the adjacency property of the first and last row.
You'll be given two integers m
and n
that
indicate the number of rows and columns at the first line. The next m
lines will be the matrix and each line represents one row of the given
matrix. You're required to output the minimum cost.
Notes: : The test cases have the properties: number of rows is between 1 and 10; number of columns is between 1 and 100; number in matrix can be positive or negative; All path weights can be represented by 30-bit signed integer.
Example 1
Input: 5 6 3 4 1 2 8 6 6 1 8 2 7 4 5 9 3 9 9 5 8 4 1 3 2 6 3 7 2 8 6 4 Output: 16 Explanation: the path: 1 2 3 4 4 5
Example 2
Input: 5 6 3 4 1 2 8 6 6 1 8 2 7 4 5 9 3 9 9 5 8 4 1 3 2 6 3 7 2 1 2 3 Output: 11 Explanation: the path: 1 2 1 5 4 5