BigCube

SRM 192 · 2004-04-27 · by Rustyoldman

SRM 192 · 2004-04-27 · by Rustyoldman · Math

Show categories

Class Name: BigCube

Return Type: String

Method Name: largestCube

Arg Types: (vector<string>)

Problem Statement

This problem contains HTML superscripts which may not display properly for plugin users. Please use the applet to view the problem statement and examples

You are given a list of integer intervals, ranges, where each interval is specified by a String of the form "<low>-<high>" (quotes for clarity). Here "<low>" and "<high>" represent non-negative integers (sequences of characters between '0' and '9' inclusive with no leading zeros) which are separated by a single hyphen '-'.

Your task is to find the largest integer that is in at least one of the intervals and is a perfect cube. Return this integer in a String with no extra leading zeros and only the digits '0'-'9'. In other words, find the largest integer in the intervals that is equal to n³ for some integer n. If there is no perfect cube in the intervals, return the empty string, "" (quotes for clarity).

For example {"1-1000000000001"} would return "1000000000000" which is 10000³.

Notes

C++ users: the 64 bit integer type is long long.

Constraints

range will have between 1 and 50 elements inclusive.
Each element of range will contain between 3 and 31 characters inclusive.
Each element of range will be of the form "-" where and are separated by exactly one hyphen, '-'.
Each character of and will be a digit between '0' and '9' inclusive.
and will contain no leading zeros.
and will be between 0 and 1000000000000000 (1e15) inclusive.
will be less than or equal to

Examples

{"1-1000000000001"}
Returns: "1000000000000"

The example from above: 100003

{"10-999999999999990","11-999999999999991","12-999999999999992",
 "13-999999999999993","14-999999999999994","15-999999999999995",
 "16-999999999999996","17-999999999999993","18-999999999999994",
 "19-999999999999999"}
Returns: "999970000299999"

999993

{"0-3","10-20","30-60","80-120"}
Returns: "1"

{"0-0","2-7","9-26","28-63","65-124"}
Returns: "0"

{"999700030000-999999999999","999400119993-999700029998",
 "999100269974-999400119991","998800479937-999100269972"}
Returns: ""

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

Coding Area

Language: C++17 · define a public class BigCube with a public method string largestCube(vector<string> range) · 34 test cases · 2 s / 256 MB per case