Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

UPCOMING CHALLENGES:

CURRENT CHALLENGES:

Nickel 2018

PAST CHALLENGES

Cobaltum 2018

Ferrum 2018

Manganum 2017

Chromium 2017

Vanadium 2016

Titanium 2016

Scandium 2016

Calcium 2015

Kalium 2015

Argon 2015

Chlorum 2014

Sulphur 2014

Phosphorus 2014

Silicium 2014

Aluminium 2014

Magnesium 2014

Natrium 2014

Neon 2014

Fluorum 2014

Oxygenium 2014

Nitrogenium 2013

Carbo 2013

Boron 2013

Beryllium 2013

Lithium 2013

Helium 2013

Hydrogenium 2013

Omega 2013

Psi 2012

Chi 2012

Phi 2012

Upsilon 2012

Tau 2012

Sigma 2012

Rho 2012

Pi 2012

Omicron 2012

Xi 2012

Nu 2011

Mu 2011

Lambda 2011

Kappa 2011

Iota 2011

Theta 2011

Eta 2011

Zeta 2011

Epsilon 2011

Delta 2011

Gamma 2011

Beta 2010

Alpha 2010

ambitious

Calculate how balls roll through a board of switches.

Programming language:
Spoken language:

A board consisting of ball switches arranged into N rows and M columns is given. A *ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

K balls are rolled through the board one by one. Each ball enters the board through the top edge of the top-left ball switch. Then it rolls through the board and possibly changes its direction depending on the modes of the switches through which it passes. Eventually it leaves the board either:

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

For example, consider a board consisting of 2 rows and 3 columns. The following image shows the initial modes of all switches and how the first four balls will roll through the board.

Write a function:

int solution(int **A, int N, int M, int K);

that,given a matrix A consisting of N rows and M columns describing a board of ball switches and a non-negative number K of balls inserted into this board, returns the number of balls that will leave the board through the bottom edge of the bottom-right switch.

The matrix A describes the board as follows:

- each element of the matrix has value −1, 0 or +1 and describes the initial mode of the corresponding ball switch;
- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of ball switches arranged into N rows and M columns is given. A *ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

K balls are rolled through the board one by one. Each ball enters the board through the top edge of the top-left ball switch. Then it rolls through the board and possibly changes its direction depending on the modes of the switches through which it passes. Eventually it leaves the board either:

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

For example, consider a board consisting of 2 rows and 3 columns. The following image shows the initial modes of all switches and how the first four balls will roll through the board.

Write a function:

int solution(vector< vector<int> > &A, int K);

that,given a matrix A consisting of N rows and M columns describing a board of ball switches and a non-negative number K of balls inserted into this board, returns the number of balls that will leave the board through the bottom edge of the bottom-right switch.

The matrix A describes the board as follows:

- each element of the matrix has value −1, 0 or +1 and describes the initial mode of the corresponding ball switch;
- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of ball switches arranged into N rows and M columns is given. A *ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

K balls are rolled through the board one by one. Each ball enters the board through the top edge of the top-left ball switch. Then it rolls through the board and possibly changes its direction depending on the modes of the switches through which it passes. Eventually it leaves the board either:

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

For example, consider a board consisting of 2 rows and 3 columns. The following image shows the initial modes of all switches and how the first four balls will roll through the board.

Write a function:

class Solution { public int solution(int[][] A, int K); }

that,given a matrix A consisting of N rows and M columns describing a board of ball switches and a non-negative number K of balls inserted into this board, returns the number of balls that will leave the board through the bottom edge of the bottom-right switch.

The matrix A describes the board as follows:

- each element of the matrix has value −1, 0 or +1 and describes the initial mode of the corresponding ball switch;
- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

*ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

Write a function:

func Solution(A [][]int, K int) int

The matrix A describes the board as follows:

- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

*ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

Write a function:

class Solution { public int solution(int[][] A, int K); }

The matrix A describes the board as follows:

- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

*ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

Write a function:

function solution(A, K);

The matrix A describes the board as follows:

- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

*ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

Write a function:

function solution(A, K)

The matrix A describes the board as follows:

- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

*ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

Write a function:

int solution(NSMutableArray *A, int K);

The matrix A describes the board as follows:

- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

*ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

Assume that the following declarations are given:

type TMatrix = array of array of longint;

Write a function:

function solution(A: TMatrix; N: longint; M: longint; K: longint): longint;

The matrix A describes the board as follows:

- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

*ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

Write a function:

function solution($A, $K);

The matrix A describes the board as follows:

- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

*ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

Write a function:

def solution(A, K)

The matrix A describes the board as follows:

- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

*ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

Write a function:

def solution(a, k)

The matrix A describes the board as follows:

- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

*ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

Write a function:

object Solution { def solution(a: Array[Array[Int]], k: Int): Int }

The matrix A describes the board as follows:

- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

*ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

Write a function:

public func solution(inout A : [[Int]], _ K : Int) -> Int

The matrix A describes the board as follows:

- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

*ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

Write a function:

public func solution(_ A : inout [[Int]], _ K : Int) -> Int

The matrix A describes the board as follows:

- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

*ball switch* is a device that can change the direction of a rolling ball. It has the following properties:

- it is square-shaped;
- it can be in one of three modes: −1, 0 or +1;
- a ball can enter it through the top or the left edge;
- a ball can leave it through the bottom or the right edge;
- if the mode is −1, a ball entering the device will leave it through the bottom edge;
- if the mode is +1, a ball entering the device will leave it through the right edge;
- if the mode is 0, a ball entering the device will not change direction;
- after a ball leaves the device, its mode is immediately negated.

- through the bottom edge of one of the switches in the bottom row; or
- through the right edge of one of the switches in the rightmost column.

Write a function:

Private Function solution(A As Integer()(), K As Integer) As Integer

The matrix A describes the board as follows:

- element A[0][0] corresponds to the top-left ball switch;
- element A[N−1][M−1] corresponds to the bottom-right ball switch.

For example, given K = 4 and matrix A such that:

the function should return 1, because:

- the balls roll through the board as shown in the image above;
- only the second ball leaves the board through the bottom edge of the bottom-right ball switch.

Assume that:

- N and M are integers within the range [1..1,000];
- each element of matrix A is an integer that can have one of the following values: −1, 0, 1;
- K is an integer within the range [0..1,000,000,000];
- the matrix A correctly describes some board of ball switches;
- balls are inserted in to the board and roll through it according to the rules specified above.

Complexity:

- expected worst-case time complexity is O(N*M);
- expected worst-case space complexity is O(M).

Information about upcoming challenges, solutions and lessons directly in your inbox.

© 2009–2018 Codility Ltd., registered in England and Wales (No. 7048726). VAT ID GB981191408. Registered office: 107 Cheapside, London EC2V 6DN