Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- int cycleLength(long long int);
- int cycleLengthResult[1000001];
- int main(int argc, char *argv[])
- {
- int i = 0, j = 0, cur = 0, max = 0, k = 0, s = 0;
- for (i = 1 ; i < 1000001 ; ++ i ) cycleLength(i);
- while ( scanf("%d%d", &i, &j) != EOF )
- {
- printf("%d %d ", i, j);
- if ( i > j )
- {
- s = i;
- i = j;
- j = s;
- }
- max = 0;
- for ( k = i ; k <= j ; ++ k )
- {
- cur = cycleLengthResult[k];
- if (cur > max) max = cur;
- }
- printf("%dn", max);
- }
- return 0;
- }
- int cycleLength(long long int arg)
- {
- if ( arg > 1000000 )
- {
- if (!(arg & 1))
- return 1 + cycleLength(arg/2);
- else
- return 1 + cycleLength(arg*3+1);
- }
- if (!cycleLengthResult[arg])
- {
- int valueForArg = 0;
- if (arg == 1)
- valueForArg = 1;
- else if (!(arg & 1))
- valueForArg = 1 + cycleLength(arg/2);
- else
- valueForArg = 1 + cycleLength(arg*3+1);
- cycleLengthResult[arg] = valueForArg;
- }
- return cycleLengthResult[arg];
- }
- t(n) = 1 if n is 1
- = 3n + 1 if n is odd
- = n / 2 if n is even
- c(n) = number of times t(n) will happen
- (terrible math syntax here, but erm... go with it)
- for (int i = 1; i <= 1000000; ++i) {
- if (i % 2 == 0) {
- //We know that i / 2 must already be set, so we can just do a constant time look up
- //(your code already does this implicitly through the recursion)
- m[i] = 1 + m[i / 2];
- } else {
- m[i] = cycleLength(i);
- }
- }
- if (i % 2 == 0) {
- m[i] = 1 + m[i/2];
- } else if (i % 8 == 5) {
- m[i] = 4 + m[3 * ((i - 5) / 8) + 2];
- } else {
- m[i] = cycleLength(i);
- }
- 8j + 5 -> 24j + 16 -> 12j + 8 -> 6j + 4 -> 3j + 2
- int cycleLength(long arg);
- static inline int nextLength(long arg)
- {
- long n;
- if (arg & 1) {
- n = (arg * 3) + 1;
- } else {
- n = arg / 2;
- }
- return 1 + cycleLength(n);
- }
- int cycleLength(long arg)
- {
- if (arg > 10000000) {
- return nextLength(arg);
- }
- if (cycleLengthResult[arg] != 0) {
- return cycleLengthResult[arg];
- }
- return cycleLengthResult[arg] = nextLength(arg);
- }
- #include <cstdio>
- #include <algorithm> // std::min, std::max
- using namespace std;
- int cycleLength(int);
- const int CACHE_LEN = 1000001;
- short cache[CACHE_LEN] = {0};
- int main()
- {
- int leftNo, rightNo, minNo, maxNo;
- while ( scanf("%d%d", &leftNo, &rightNo) != EOF )
- {
- int maxCycles = 0;
- minNo = min(leftNo, rightNo);
- maxNo = max(leftNo, rightNo);
- for (int curNo = minNo; curNo <= maxNo; ++curNo )
- {
- int curCycles = cycleLength(curNo);
- if (curCycles > maxCycles) maxCycles = curCycles;
- }
- printf("%d %d %dn", leftNo, rightNo, maxCycles);
- }
- return 0;
- }
- int cycleLength(int start)
- {
- int length = cache[start];
- if (length != 0) return length;
- length++;
- long long int current = start;
- while (current != 1)
- {
- if (current % 2 == 0) current /= 2;
- else current = 3 * current + 1;
- length++;
- }
- cache[start] = length;
- return length;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement