Connection Status:
Competition Arena > RollingDiceDivTwo

RollingDiceDivTwo

SRM 536 · 2011-11-22 · by meret

SRM 536 · 2011-11-22 · by meret · Greedy, Sorting, String Parsing
Class Name: RollingDiceDivTwo
Return Type: int
Method Name: minimumFaces
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Byteasar is playing a tabletop role-playing game with his friends. To determine the effectiveness of their heroes' actions the players use a rather unique set of dice which may have nonequal number of faces. Each die has between 1 and 9 faces, inclusive. If a die has m faces, they contain precisely all the values between 1 and m, inclusive. More precisely, for each k between 1 and m, inclusive, there is one face that shows exactly k pips. When a die is cast, every face has equal probability to come out on top.

Every time all the dice were thrown at once, Byteasar wrote down the numbers of pips visible on each of the topmost faces (in any order). The results of the i-th throw are given in throws[i]; the length of throws[i] is equal to the number of dice and each character of throws[i] denotes the number of pips visible on one of the topmost faces. For example, if throws[3][0]='7', this means that in throw 3 (0-based index) one of the dice showed exactly 7 pips on the top. Please note that the ordering of dice may be different for different throws.

Given the String[] throws containing Byteasar's notes, return the minimum possible total number of faces of all dice.

Notes

  • Please note that a die can have as few as one or two faces.

Constraints

  • rolls will contain between 1 and 50 elements, inclusive.
  • rolls[0] will contain between 1 and 50 characters, inclusive.
  • All elements of rolls will contain the same number of characters.
  • Each character in each element of rolls will be one of '1'-'9'.
Examples
0)
{"137", "364", "115", "724"}
Returns: 14

In the first throw the numbers of pips on the topmost faces of the dice were 1, 3 and 7; in the second throw they were 3, 6 and 4, in the third they were 1, 1 and 5 and in the fourth roll they were 7, 2 and 4. The players may have used dice with 3, 4 and 7 faces, giving a total of 14 faces. No other possible set of dice has less faces in total.

1)
{"1112", "1111", "1211", "1111"}
Returns: 5

The players could have used three dice with one face each and one die with two faces.

2)
{"24412", "56316", "66666", "45625"}
Returns: 30

The players could have used five dice with six faces each.

3)
{"931", "821", "156", "512", "129", "358", "555"}
Returns: 19
4)
{"3", "7", "4", "2", "4"}
Returns: 7

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

Coding Area

Language: C++17 · define a public class RollingDiceDivTwo with a public method int minimumFaces(vector<string> rolls) · 55 test cases · 2 s / 256 MB per case

Submitting as anonymous