MagicNumbersAgain | Topcoder Archive

Problem Statement

Sequence (d₁, d₂, d₃, ..., d_t) is a digit representation of X (with no leading zeros) if the i-th digit of X is d_i. In particular, d₁ is the most and d_t is the least significant digit of X. For instance, the digit representation of X = 576 is (5, 7, 6).

We say that an integer X is magic-square iff:

X is a square of an integer, i.e., X = Y² for some integer Y.
For the digit representation (d₁, d₂, d₃, ..., d_t) of X it holds d₁ < d₂ > d₃ < d₄, and so on. That is, for each odd i < t it holds d_i < d_{i + 1}, and for each even i < t it holds d_i > d_{i + 1}.

Given A and B, output how many magic-square integers between A and B there are.

Definition

Class:: MagicNumbersAgain
Method:: count
Parameters:: long, long
Returns:: int
Method signature:: int count(long A, long B)
(be sure your method is public)

Constraints

B will be between 1 and 10,000,000,000, inclusive.
A will be between 1 and B, inclusive.

Examples

```
1
```
```
64
```
```
Returns: 7
```
The magic numbers between 1 and 64 are: 1, 4, 9, 16, 25, 36, and 49. Although 64 is a square of an integer (64=8*8), 64 is not a magic number as its first digit is not smaller than its second one.
```
50
```
```
60
```
```
Returns: 0
```
Between 50 and 60 there are no integers that are squares of other integers, hence in this range can not exist magic numbers neither.
```
121
```
```
121
```
```
Returns: 1
```
```
5679
```
```
1758030
```
```
Returns: 73
```
```
1304164
```
```
2000000
```
```
Returns: 14
```

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.