MagicalGirlLevelThreeDivOne
SRM 514 · 2011-05-25 · by wrong
Problem Statement
Magical Girls are girls who have magical powers. They fight against evil witches to protect the Earth.
You, one of the Magical Girls, are now fighting against an evil witch. You want to use ultimate magic to defeat the witch. To use ultimate magic you have to chant a magical spell. The spell is determined with a sequence A.
A is the sequence of strings which is determined with a sequence first. Each element of first is a string which contains only '0' and '1'. Let K be the number of elements of first. Each element of A is defined as follows:
- for all i, 0 <= i < K, A[i] = first[i].
- Otherwise, A[i] = A[i-1] + A[i-K-1] + A[i-2K-1] + ... (while i-m*K-1 is not less than 0). Here operator '+' denotes concatenation of strings.
You are given three integers n, lo and hi. Let S be the substring of A[n] from lo to hi, inclusive. That is, S = A[n][lo..hi] where both lo and hi are 0-based indices into A[n]. The spell you have to chant is S and the power of the magic is equal to the length of the longest contiguous substring of S which contains only '1' characters. If S contains only '0' characters, then the power of the magic is equal to 0. Return the power of the ultimate magic.
Constraints
- first will contain between 1 and 50 elements, inclusive.
- Each element of first will contain between 1 and 50 characters, inclusive.
- Each element of first will consist of '0' (zero) and '1' (one).
- n will be between 0 and 1,000,000,000, inclusive.
- hi will be between 0 and min{1,000,000,000,000,000 (10^15), (length of A[n])-1}, inclusive.
- lo will be between 0 and hi, inclusive.
{"111", "011"}
4
2
7
Returns: 4
A[2] = "011", A[3] = "011111", A[4] = "011111011" S = A[4][2..7] = "111101"
{"1", "11", "111"}
123456789
123456789
123456789012345
Returns: 123456665555557
{"0", "00", "000"}
987654321
987654321
987654321054321
Returns: 0
{"1110", "11", "11111", "111", "1"}
314159265
271828182845904
314159265358979
Returns: 15
{"10000", "011011001011000001101000010100000111000110110",
"000001010001011000001101110", "100100000110100001010000",
"011011010", "01100000010101101110000011100011001000",
"0001010", "010011000", "000101001", "00", "1"}
1000000000
1000000000000000
1000000000000000
Returns: 1
Submissions are judged against all 118 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MagicalGirlLevelThreeDivOne with a public method long long theMaxPower(vector<string> first, int n, long long lo, long long hi) · 118 test cases · 2 s / 256 MB per case