Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #define FOR(a,b,c) for(long long a = b ; a < c ; ++a)
- #define MEMO_SIZE 1000005
- long memoization[MEMO_SIZE] = {0};
- long long max (long long a, long long b) {
- return a > b ? a : b;
- }
- long long min (long long a, long long b) {
- return a < b ? a : b;
- }
- int isEven (long long n) {
- return n % 2 == 0;
- }
- int canBeMemoized (long long n) {
- return n < MEMO_SIZE;
- }
- int isNotMemoizedYet (long long n) {
- return canBeMemoized(n) && memoization[ (int) n ] == 0;
- }
- int isMemoized (long long n) {
- return canBeMemoized(n) && memoization[ (int) n ] != 0;
- }
- long long solution (long long n) {
- if (isMemoized(n)) return memoization[ (int) n ];
- int result = 1;
- while (n != 1) {
- if ( isEven(n) ) n /= 2;
- else {
- n = ((n*3) + 1) / 2;
- ++result;
- }
- ++result;
- }
- if (isNotMemoizedYet(n)) {
- memoization[ (int) n] = result;
- }
- return result;
- }
- long long countingN (long long a, long long b) {
- long long lower = min(a, b);
- long long upper = max(a, b);
- long long maximum = 0;
- FOR(i,lower,upper+1) {
- long long n = solution(i);
- maximum = max(maximum, n);
- }
- return maximum;
- }
- int main () {
- long long a, b, n;
- while (scanf("%lld %lld", &a, &b) == 2) {
- printf("%lld\n", countingN(a, b));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement