TopCoder problem "CubeOfDice" used in TCO09 Round 4 (Division I Level One)



Problem Statement

    
    +---+
    | D |
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
    | C |
    +---+

The ASCII art above shows the net of a general 6-sided die. There is a number written on each of the six sides. In the picture, these numbers are denoted A to F. (The net is folded so that the numbers are on the outside, but this information is not necessary to solve the following problem.)

The numbers A to F will be given to you as a int[] values, where A will be values[0], B will be values[1], and so on.

You have N^3 identical dice, each one matching the net shown above. You want to take all the dice, rotate some of them, and assemble a N×N×N cube. The cube will be standing on a table, hence only 5 of its sides will be visible.

You are given the int N, and the int[] values. Write a method that will return the smallest possible sum of the 5N^2 visible faces of the dice.

 

Definition

    
Class:CubeOfDice
Method:minimumSum
Parameters:int, int[]
Returns:long
Method signature:long minimumSum(int N, int[] values)
(be sure your method is public)
    
 

Constraints

-N will be between 1 and 1,000,000, inclusive.
-values will contain exactly 6 elements.
-Each element of values will be between 1 and 50, inclusive.
 

Examples

0)
    
2
{1,2,3,4,5,6}
Returns: 36
This input corresponds to 8 classical dice.
1)
    
3
{1,2,3,4,5,6}
Returns: 69
Now we have 27 classical dice.
2)
    
1000000
{50,50,50,50,50,50}
Returns: 250000000000000
The largest possible output. Note that all numbers are equal, hence in this case there is only one possible way to arrange the dice.
3)
    
10
{1,1,1,1,50,1}
Returns: 500
It is possible to rotate and arrange the dice so that no side with the 50 will be visible.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10316

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13762&pm=10316

Writer:

misof

Testers:

PabloGilberto , legakis , ivan_metelsky

Problem categories:

Greedy, Math, Sorting