JOIN
Get Time

   Problem Statement  

 Problem Statement for DropCoins

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.
 

Definition

    
Class:DropCoins
Method:getMinimum
Parameters:String[], int
Returns:int
Method signature:int getMinimum(String[] board, int K)
(be sure your method is public)
    
 

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

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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 525 Round 1 - Division I, Level One
       Single Round Match 525 Round 1 - Division II, Level Two