ChocolateDividingEasy_TopCoder笔试题

Problem Statement

Mirosz adores sweets. He has just bought a rectangular bar of chocolate. The bar is divided into a grid of square cells. Different cells may have a different quality. You are given the description of the bar in a String[] chocolate. Each character in chocolate is a digit between '0' and '9', inclusive: the quality of one of the cells.

Mirosz is now going to divide the chocolate into 9 parts: one for him and one for each of his 8 friends. He will do the division by making four cuts: two horizontal and two vertical ones. Each cut must go between two rows or columns of cells. Each of the 9 parts must be non-empty. The quality of a part is the sum of the qualities of all cells it contains.

Mirosz is well-mannered and he will let his friends choose their pieces first. His friends are even more addicted to chocolate than he is. Therefore, they will certainly choose the pieces with higher quality first, and Mirosz will be left with the worst of the nine pieces.

You are given the String[] chocolate. Find the optimal places for the four cuts. More precisely, compute and return the largest possible quality of Mirosz's part of the chocolate bar.

Definition

Class:ChocolateDividingEasy
Method:findBest
Parameters:String[]
Returns:int
Method signature:int findBest(String[] chocolate)
(be sure your method is public)

Constraints

- chocolate will contain between 3 and 50 elements, inclusive.

- All elements in chocolate will contain between 3 and 50 characters, inclusive.

- All elements in chocolate will contain the same number of characters.

- All elements in chocolate will contain only digits ('0'-'9').

Examples

{
"9768",
"6767",
"5313"
}

Returns: 3

There are three valid ways to cut this chocolate. One of the optimal ones is shown below.
<tt>
9 | 7 | 6 8
--|---|-----
6 | 7 | 6 7
--|---|-----
5 | 3 | 1 3 </tt>

This way of cutting produces parts with the following qualities: 9, 7, 14, 6, 7, 13, 5, 3, and 4. The quality of the worst part (the one that Mirosz will get) is 3.

Here is another way of cutting the same chocolate:

<tt> 9 7 | 6 | 8
----|---|---
6 7 | 6 | 7
----|---|---
5 3 | 1 | 3
</tt>
If Mirosz cuts the chocolate in this way, the quality of his part will be 1, which is worse than 3.
1)

{
"36753562",
"91270936",
"06261879",
"20237592",
"28973612",
"93194784"
}

Returns: 15

There is only one optimal way to divide the chocolate:

<tt> 3 6 7 5 | 3 5 | 6 2
9 1 2 7 | 0 9 | 3 6
--------|-----|-----
0 6 2 6 | 1 8 | 7 9
2 0 2 3 | 7 5 | 9 2
--------|-----|-----
2 8 9 7 | 3 6 | 1 2
9 3 1 9 | 4 7 | 8 4 </tt>

The three parts on the top have qualities 3+6+7+5+9+1+2+7 = 40, 3+5+0+9 = 17 and 6+2+3+6 = 17
The worst part is the one in the bottom right corner. Its quality is only 1+2+4+8 = 15.
2)

{
"012",
"345",
"678"
}

Returns: 0

class ChocolateDividingEasy { int area[100][100]; public: int findBest(vector<string> chocolate) { int n=chocolate.size(),m=chocolate[0].size(),i,j,k,q; vector<vector<int> > G(n+1,vector<int>(m+1,0)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) G[i][j]=chocolate[i-1][j-1]-'0'; int Max=0; area[1][1]=G[1][1]; for(j=2;j<=m;j++) area[1][j]=G[1][j]+area[1][j-1]; for(i=2;i<=n;i++) area[i][1]=G[i][1]+area[i-1][1]; for(i=2;i<=n;i++) for(j=2;j<=m;j++) area[i][j]=G[i][j]+area[i-1][j]+area[i][j-1]-area[i-1][j-1]; for(i=1;i<n;i++) for(j=i+1;j<n;j++) for(k=1;k<m;k++) for(q=k+1;q<m;q++){ int Min=999999999; Min=min(Min,getA(1,1,i,k)); Min=min(Min,getA(1,k+1,i,q)); Min=min(Min,getA(1,q+1,i,m)); Min=min(Min,getA(i+1,1,j,k)); Min=min(Min,getA(i+1,k+1,j,q)); Min=min(Min,getA(i+1,q+1,j,m)); Min=min(Min,getA(j+1,1,n,k)); Min=min(Min,getA(j+1,k+1,n,q)); Min=min(Min,getA(j+1,q+1,n,m)); Max=max(Max,Min); } return Max; } int getA(int i,int j,int k,int q){ return area[k][q]-area[i-1][q]-area[k][j-1]+area[i-1][j-1]; } };//暴力枚举横向竖向的四刀

ChocolateDividingEasy

Problem Statement

Definition

Constraints

Examples

问题信息

热门推荐

通过挑战的用户

相关试题