EllysThree | Topcoder Archive

Problem Statement

Elly has a rectangular matrix with N rows and M columns. Each cell contains a digit (0-9). The girl defines a "path" from the cell in the upper left corner (row 0, column 0) to the lower right one (row N-1, column M-1) as a sequence of cells sharing a side going only down or to the right.

Each path has an associated value â that is the integer we get when we concatenate the digits in the visited cells, in the order we visit them. Values with leading zeroes are allowed. Let's look at the following possible matrix with 4 rows and 7 columns:

The path going down, right, right, down, right, right, right, down, right has value 1895781265. Other possible paths have values 1849312095, 1895781365, or 1858721365, among many others.

The girl can change some (possibly all or none) of the cells of the matrix. If the current digit in a cell is X, in one operation the girl can change it to either X-1 or X+1. The digits change cyclically between 0 and 9 â thus changing 0 to 9 or 9 to 0 takes a single operation. Elly can do as many operations as she wants â thus she can get to any other matrix of digits with the same dimensions.

Elly wants to get a matrix on which all paths have values divisible by three. Of course, she wants to do it with as few operations as possible. Given the ints N and M, as well as the String[] matrix giving the initial digits in the matrix, return the minimum number of operations required to do so.

Definition

Class:: EllysThree
Method:: getMin
Parameters:: int, int, String[]
Returns:: int
Method signature:: int getMin(int N, int M, String[] matrix)
(be sure your method is public)

Constraints

N and M will be between 1 and 50, inclusive.
matrix will contain exactly N elements.
Each element of matrix will contain exactly M characters.
Each character in matrix will be a digit ('0'-'9').

Examples

```
4
```
```
7
```
```
{"1849312",
 "8951400",
 "5678129",
 "8721365"}
```
```
Returns: 10
```
The example from the problem statement. One of the possible resulting matrices is: 1839421 8961510 6678139 9721365
```
1
```
```
3
```
```
{"042"}
```
```
Returns: 0
```
Leading zeroes are allowed, thus this matrix is valid without any changes.
```
9
```
```
1
```
```
{"1", "3", "3", "7", "6", "6", "6", "4", "2"}
```
```
Returns: 1
```
Increasing by one any of the digits yields a matrix of the required type.

{"9454743993694",
 "2621082535304",
 "7042910517370",
 "1085880558575",
 "1649500905308",
 "1329832441329",
 "8039295627801"}

Returns: 42

The Answer is 42.

{"3924540372699482461959052373",
 "3775662604951838761645280661",
 "4590019155668566895846525300",
 "7660057219937532806711524044",
 "1564147647984682605010172146",
 "7045841532282877576364456274",
 "3814819683751796473651237567",
 "4031424800358860980124855111",
 "5002523845580224146215648232",
 "8491414555026773578968320263",
 "4946734059870766934433755091",
 "9792652664307908810065499322",
 "5883633601313699981657212869",
 "0270456241288992902960982050",
 "8248225251569913625753339601",
 "6038989966909434471708165284",
 "7157408935676850512694539390",
 "1903308470539870820923313050",
 "5672155010906362182244410101",
 "5613238011479959434003125799",
 "1616602903240654799752974673",
 "9917238043310329767524789648",
 "9386866245651931148351599616",
 "0288261775320885692141607061",
 "4502491177791892689367563262",
 "2387625226003663573293368187",
 "1851685890743516942422293606",
 "6116997930274118769324412710",
 "0640686746123981416169165875",
 "2809115257849686014067667122",
 "2036057721028023144804036953",
 "8941139704540145857739666512",
 "9853874329000744480537363737"}

Returns: 484

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.