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:

Palladium 2020

PAST CHALLENGES

Rhodium 2019

Ruthenium 2019

Technetium 2019

Molybdenum 2019

Niobium 2019

Zirconium 2019

Yttrium 2019

Strontium 2019

Rubidium 2018

Arsenicum 2018

Krypton 2018

Bromum 2018

Future Mobility

Grand Challenge

Digital Gold

Selenium 2018

Germanium 2018

Gallium 2018

Zinc 2018

Cuprum 2018

Cutting Complexity

Nickel 2018

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

Calculate how balls roll through a board of switches.

Programming 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:

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.

Write an ** efficient** algorithm for the following assumptions:

- 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.

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