Statistics

Problem Statement for "MagicNumbersAgain"

Problem Statement

Sequence (d1, d2, d3, ..., dt) is a digit representation of X (with no leading zeros) if the i-th digit of X is di. In particular, d1 is the most and dt 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 = Y2 for some integer Y.
  • For the digit representation (d1, d2, d3, ..., dt) of X it holds d1 < d2 > d3 < d4, and so on. That is, for each odd i < t it holds di < di + 1, and for each even i < t it holds di > di + 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. 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.

  2. 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.

  3. 121

    121

    Returns: 1

  4. 5679

    1758030

    Returns: 73

  5. 1304164

    2000000

    Returns: 14

  6. 1304164

    1907161

    Returns: 14

  7. 1304165

    1907161

    Returns: 13

  8. 1

    1

    Returns: 1

  9. 1

    10000000000

    Returns: 1149

  10. 10000000000

    10000000000

    Returns: 0

  11. 1000000000

    10000000000

    Returns: 589

  12. 10

    1234567890

    Returns: 566

  13. 1000000

    9999999999

    Returns: 1063

  14. 9999999999

    10000000000

    Returns: 0

  15. 2

    4

    Returns: 1

  16. 4

    9

    Returns: 2

  17. 24

    26

    Returns: 1

  18. 1501275177

    8330329353

    Returns: 533

  19. 17734730

    6383220611

    Returns: 909

  20. 2084048076

    4060336726

    Returns: 210

  21. 2284006856

    9035470905

    Returns: 413

  22. 231457451

    7732700841

    Returns: 735

  23. 8240370457

    9854044437

    Returns: 12

  24. 6589010881

    9345242761

    Returns: 69

  25. 6797853005

    9619875765

    Returns: 53

  26. 1555956841

    8182526689

    Returns: 519

  27. 3611916921

    3682513801

    Returns: 17

  28. 2377186301

    5202542937

    Returns: 282

  29. 367295822

    4368245701

    Returns: 493

  30. 4456734205

    7142592909

    Returns: 172

  31. 7096237713

    9496639625

    Returns: 31

  32. 4470460209

    8391275841

    Returns: 191

  33. 1

    1000000000

    Returns: 560

  34. 1000

    10000000000

    Returns: 1135

  35. 5

    10000000000

    Returns: 1147

  36. 400000099

    10000000000

    Returns: 679

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.
This problem was used for: