Connection Status:
Competition Arena > KleofasTail

KleofasTail

SRM 546 · 2011-11-22 · by misof

SRM 546 · 2011-11-22 · by misof · Simple Math
Class Name: KleofasTail
Return Type: long
Method Name: countGoodSequences
Arg Types: (long long, long long, long long)
Problem Statement

Problem Statement

Let X be a nonnegative integer. The Kleofas tail of X is an infinite sequence of nonnegative integers, defined as follows:

  • The first element is X.
  • After an even element Y, the next element of the sequence is Y/2.
  • After an odd element Z, the next element of the sequence is Z-1.

For example, the Kleofas tail of 60 starts as follows: 60, 30, 15, 14, 7, 6, ...

You are given longs K, A, and B. Return the number of integers X between A and B, inclusive, such that the Kleofas tail of X contains at least one occurrence of K.

Notes

  • Zero is an even number.

Constraints

  • K will be between 0 and 10^18, inclusive.
  • A will be between 0 and 10^18, inclusive.
  • B will be between 0 and 10^18, inclusive.
  • A will be less than or equal to B.
Examples
0)
3
4
8
Returns: 2

The value 3 occurs in the Kleofas tail of 6 and also in the Kleofas tail of 7.

1)
1
23457
123456
Returns: 100000

For each X between 23457 and 123456, inclusive, the Kleofas tail of X contains the value 1.

2)
1234567890123456
10
1000000
Returns: 0

Each Kleofas tail is a nonincreasing sequence.

3)
0
0
2
Returns: 3
4)
7
123456789012
123456789034
Returns: 23
71)
2
3
3
Returns: 1

The Kleofas tail of 3 is 3, 2, 1, 0, 0, 0, ...

Submissions are judged against all 178 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class KleofasTail with a public method long long countGoodSequences(long long K, long long A, long long B) · 178 test cases · 2 s / 256 MB per case

Submitting as anonymous