Connection Status:
Competition Arena > CubeOfDice

CubeOfDice

TCO09 Round 4 · 2009-02-24 · by misof

TCO09 Round 4 · 2009-02-24 · by misof · Greedy, Math, Sorting
Class Name: CubeOfDice
Return Type: long
Method Name: minimumSum
Arg Types: (int, vector<int>)
Problem Statement

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.

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.

4)
10
{50,1,1,1,1,50}
Returns: 696

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

Coding Area

Language: C++17 · define a public class CubeOfDice with a public method long long minimumSum(int N, vector<int> values) · 160 test cases · 2 s / 256 MB per case

Submitting as anonymous