Connection Status:
Competition Arena > FoxTheLinguist

FoxTheLinguist

SRM 584 · 2013-06-25 · by cgy4ever

SRM 584 · 2013-06-25 · by cgy4ever · Graph Theory
Class Name: FoxTheLinguist
Return Type: int
Method Name: minimalHours
Arg Types: (int, vector<string>)
Problem Statement

Problem Statement

Fox Ciel plans to learn n new foreign languages because she is such a clever fox. The languages are named with characters 'A', 'B', ..., 'A'+n-1. For each language, there are ten levels of fluency from 0 to 9. Fox Ciel starts out with fluency 0 in every foreign language. Level 9 denotes mastery of the language.

A number of language courses are available to Fox Ciel. Each course has a prerequisite language and level, and it leads to a target language and level. The prerequisite language is not necessarily the same as the target language. Each course also takes a certain amount of time.

A course is described by the String[] courseInfo. Concatenate all of the Strings to obtain a single String that looks like this:

"B9->C2:0200 A0->A9:1000 A3->A4:0001"

Note that the number after the colon (':') is always four digits long. The example above contains three courses. The first one is described as "B9->C2:0200", which means that if Fox Ciel has achieved a fluency of no less than 9 in language B, she can spend 200 hours in this course to achieve a fluency of exactly 2 in language C.

How much time must Fox Ciel spend to master (i.e., reach level 9 in) every language? Return the minimal number of hours, or return -1 if it is not possible for her to master every language.

Constraints

  • n will be between 1 and 10, inclusive.
  • courseInfo will be in the format described in the problem statement.
  • courseInfo will contain between 1 and 50 elements, inclusive.
  • Each element of courseInfo will contain between 1 and 50 characters, inclusive.
  • There will be no more than 200 courses.
Examples
0)
1
{"A0->A9:1000 A0->A6:0300 A3->A9:0600"}
Returns: 900

There are three courses and one foreign language. Fox Ciel could spend 1000 hours on the first course to master the language. The optimal solution is to take the second course, followed by the third course, for a total expenditure of 300 + 600 = 900 hours.

1)
2
{"A0->A9:1000 B0->B9:1000 A1->B9:0300 B1->A9:0200"}
Returns: 1200

The optimal solution is to take the second course to master language B, then the fourth course to master language A.

2)
3
{"C0->A6:00", "01 A3", "->B9:0001 A3->C6:000", "1",
" C3->A9:0001 A9->C9:0001 A0->A9:9999",
" B0->B9:9999 C0->C9:9999 A6->A9:9999"}
Returns: 5
3)
4
{"A0->A6:6666 A0->A9:9999",
" B0->B6:6666 B0->B9:9999",
" C0->C6:6666 C0->C9:9999",
" D0->D6:6666 D0->D9:9999",
" A6->B6:0666 B6->C6:0666",
" C6->D6:0666 D6->A6:0666",
" A9->B9:0099 B9->C9:0099",
" C9->D9:0099 D9->A9:0099"}
Returns: 10296
4)
1
{"A0->A9:9999 A0->A9:8888"}
Returns: 8888

It is possible for several courses to have the same prerequisite and target.

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

Coding Area

Language: C++17 · define a public class FoxTheLinguist with a public method int minimalHours(int n, vector<string> courseInfo) · 102 test cases · 2 s / 256 MB per case

Submitting as anonymous