MagicalGirlLevelThreeDivTwo | 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 in 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 number of '1's in S. Return the power of the ultimate magic.

Definition

Class:: MagicalGirlLevelThreeDivTwo
Method:: theCount
Parameters:: String[], int, long, long
Returns:: int
Method signature:: int theCount(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 100, 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.
hi-lo will be at most 1,000.

Examples

```
{"101", "01"}
```
```
4
```
```
2
```
```
5
```
```
Returns: 2
```
A[2] = "01", A[3] = "01101", A[4] = "0110101" S = A[4][2..5] = "1010"
```
{"01", "10"}
```
```
5
```
```
4
```
```
5
```
```
Returns: 1
```
A[2] = "10", A[3] = "1001", A[4] = "100110", A[5] = "1001101001" S = A[5][4..5] = "10"

{"1", "11", "111"}

Returns: 1001

{"0", "00", "000"}

Returns: 0

{"00110110101101001111101101001011010011111011010010"}

999999999999915

1000000000000000

Returns: 50

{"10000", "011011001011000001101000010100000111000110110", 
"000001010001011000001101110", "100100000110100001010000", 
"011011010", "01100000010101101110000011100011001000",
"0001010", "010011000", "000101001", "00", "1"}

Returns: 76

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.