Connection Status:
Competition Arena > DropCoins

DropCoins

SRM 525 · 2011-05-25 · by ir5

SRM 525 · 2011-05-25 · by ir5 · Simple Math, Simple Search, Iteration
Class Name: DropCoins
Return Type: int
Method Name: getMinimum
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

There is a rectangle divided into 1x1 cells. Each cell is either empty or it contains a single coin.

You can apply the following operation repeatedly.

  • First, choose one of the directions: up, down, left, or right.
  • Then, move all coins in the chosen direction by exactly 1 cell. If this would cause a coin to move out of the rectangle, the coin drops out from the rectangle and disappears.
Your objective in this problem is to apply the operations so that the number of coins remaining on the rectangle becomes exactly K.

You are given the int K and a String[] board that describes the initial state of the rectangle. More precisely, character j of element i of board is 'o' if i-th row of j-th column of the rectangle contains a coin, and it is '.' otherwise.

Return the minimum number of operations you have to perform. If the objective is impossible, return -1.

Constraints

  • board will contain between 1 and 30 elements, inclusive.
  • Each element of board will contain between 1 and 30 characters, inclusive.
  • All elements of board will contain the same number of characters.
  • Each character in each element of board will be either '.' or 'o'.
  • K will be between 1 and 900, inclusive.
Examples
0)
{".o.."
,"oooo"
,"..o."}
3
Returns: 2

One of the optimal solutions is to move coins to the right twice.

1)
{".....o"
,"......"
,"oooooo"
,"oooooo"
,"......"
,"o....."}
12
Returns: 3

One of the optimal solutions: move coins up (1 coin drops, 13 remain) move coins down move coins down again (1 coin drops, 12 remain)

2)
{"...."
,".oo."
,".oo."
,"...."}
3
Returns: -1

It is impossible to make the number of remaining coins exactly 3.

3)
{"......."
,"..ooo.."
,"ooooooo"
,".oo.oo."
,"oo...oo"}
12
Returns: 4
4)
{"................."
,".ooooooo...oooo.."
,".ooooooo..oooooo."
,".oo.......oo..oo."
,".oo.......oo..oo."
,".ooooo.....oooo.."
,".ooooooo...oooo.."
,".....ooo..oo..oo."
,"......oo..oo..oo."
,".ooooooo..oooooo."
,".oooooo....oooo.."
,"................."}
58
Returns: 6
5)
{"o"}
1
Returns: 0

all coins drop out

8)
{"......o...."
,"....oooo..."
,"...ooooo..."
,"....ooooo.."
,"....oooo..."
,"....o......"
,"..........."}
16
Returns: 14

a case where strictly inside coins are necessary

Submissions are judged against all 125 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DropCoins with a public method int getMinimum(vector<string> board, int K) · 125 test cases · 2 s / 256 MB per case

Submitting as anonymous