CT018

Brick Wall Cuts

MediumAcceptance: 0.0%

A wall in Codetikki consists of several rows of bricks of various integer lengths and uniform height. Find a vertical line from top to bottom that cuts through the fewest bricks. If the line passes through the edge between two bricks, it does not count as a cut. Given a wall as a list of rows (each row is a list of brick lengths), output the minimum number of bricks that must be cut. Input: first line n (number of rows), then n lines each starting with row length k followed by k brick lengths. Output: minimum cuts.

Example 1:

Input: 6 3 3 5 1 4 2 3 3 2 2 5 5 3 4 4 2 4 1 3 3 3 5 1 1 6 1 1
Output: 2

Example 2:

Input: 3 2 1 1 2 1 1 2 1 1
Output: 0

Constraints:

1 <= n <= 10^4 1 <= sum of brick lengths per row <= 10^4 1 <= brick length <= 10^4 All rows have the same total width

Tags:

hash-table array
Loading...
Test Cases:No test cases
No test cases available.
Coding Problem Not Found | CodeTikki