-
Notifications
You must be signed in to change notification settings - Fork 0
/
SphereCollatz.c++
170 lines (134 loc) · 3.67 KB
/
SphereCollatz.c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
// ----------------------------
// projects/collatz/Collatz.c++
// Copyright (C) 2015
// Glenn P. Downing
// ----------------------------
// -------
// defines
// -------
#ifdef ONLINE_JUDGE
#define NDEBUG
#endif
// --------
// includes
// --------
#include <cassert> // assert
#include <iostream> // endl, istream, ostream
#include <sstream> // istringstream
#include <string> // getline, string
#include <utility> // make_pair, pair
using namespace std;
// ------------
// collatz_read
// ------------
/**
* read two ints
* @param s a string
* @return a pair of ints, representing the beginning and end of a range, [i, j]
*/
pair<int, int> collatz_read (const string& s);
// ------------
// collatz_eval
// ------------
/**
* @param i the beginning of the range, inclusive
* @param j the end of the range, inclusive
* @return the max cycle length of the range [i, j]
*/
int collatz_eval (int i, int j);
// -------------
// collatz_print
// -------------
/**
* print three ints
* @param w an ostream
* @param i the beginning of the range, inclusive
* @param j the end of the range, inclusive
* @param v the max cycle length
*/
void collatz_print (ostream& w, int i, int j, int v);
// -------------
// collatz_solve
// -------------
/**
* @param r an istream
* @param w an ostream
*/
void collatz_solve (istream& r, ostream& w);
// ------------
// collatz_read
// ------------
pair<int, int> collatz_read (const string& s) {
istringstream sin(s);
int i;
int j;
sin >> i >> j;
return make_pair(i, j);}
// ------------
// collatz_eval
// ------------
// Cache size of 1 million, holds all values that will be given in test cases on SPOJ
int cache[1000000];
int collatz_eval (int i, int j) {
assert(i > 0);
assert(j > 0);
if(i > j){ // if numbers are in descending order, reverse them
int temp = i;
i = j;
j = temp;
}
// optimization, skip all prior to j/2
if(i < j / 2){
i = j / 2;
}
int maxCount = 0;
for(int x = i; x <= j; x++){
int tempX = x;
int count = 1; // initialize at 1 so that we guarantee a minimum count of 1 to replace the maxCount of 0
if(cache[x] != 0) // if we've calculated it already, return
return cache[x];
while(tempX > 1){
if(tempX < 1000000){
if(cache[tempX] != 0){ // cache hit
count += cache[tempX];
break;
}
}
if(tempX % 2 == 0){ // if even
tempX /= 2;
}else if(tempX * 3 + 1 > 0){ // if odd and it doesnt overflow integer, perform step skipping optimization
tempX = tempX + (tempX >> 1) + 1;
count++;
}else{ // otherwise, increment count and break out of loop because overflow occured.
count++;
break;
}
count++;
}
if(count > maxCount) // replace maxCount if necessary
maxCount = count;
}
assert(maxCount > 0);
return maxCount;}
// -------------
// collatz_print
// -------------
void collatz_print (ostream& w, int i, int j, int v) {
w << i << " " << j << " " << v << endl;}
// -------------
// collatz_solve
// -------------
void collatz_solve (istream& r, ostream& w) {
string s;
while (getline(r, s)) {
const pair<int, int> p = collatz_read(s);
const int i = p.first;
const int j = p.second;
const int v = collatz_eval(i, j);
collatz_print(w, i, j, v);}}
// ----
// main
// ----
int main () {
collatz_solve(cin, cout);
return 0;}