MagicalGirlLevelThreeDivOne | Topcoder Archive

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.

Definition

Class:: MagicalGirlLevelThreeDivOne
Method:: theMaxPower
Parameters:: String[], int, long, long
Returns:: long
Method signature:: long theMaxPower(String[] first, int n, long lo, long hi)
(be sure your method is public)

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.

Examples

```
{"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

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.