/home/toolbox/public_html/solutions/1/100/fast1.c
1 /*
2 add array to optimize
3 */
4
5 #include <stdio.h>
6
7 #define TRUE (1 == 1)
8 #define FALSE (1 != 1)
9 #define MININT (-999999)
10 #define MAXSIZE 1000000
11
12 int ary[2*MAXSIZE] = {0};
13
14 void dump()
15 {
16 /* BEGIN FUNCTION dump */
17 int i;
18
19 printf("\n");
20 for (i=1; i < MAXSIZE; i++)
21 {
22 /* for */
23 if (0 != ary[i])
24 {
25 /* if */
26 printf("ary[%d] = (%d)\n", i, ary[i]);
27 } /* if */
28 } /* for */
29 } /* BEGIN FUNCTION dump */
30
31 int getInput(int *start, int *stop, int *s1, int *s2)
32 {
33 /* BEGIN FUNCTION getInput */
34 int moreToDo;
35
36 moreToDo = EOF != scanf("%d ", start);
37 /* printf("moreToDo=[%d]\n",moreToDo); */
38 if (moreToDo)
39 {
40 /* then */
41 scanf("%d ", stop);
42 if (*start > *stop)
43 {
44 /* then */
45 *s2 = *start;
46 *s1 = *stop;
47 } /* then */
48 else
49 {
50 /* else */
51 *s2 = *stop;
52 *s1 = *start;
53 } /* else */
54 } /* then */
55 return moreToDo;
56 } /* END FUNCTION getInput */
57
58 unsigned long int calcOne(unsigned long int in)
59 {
60 /* BEGIN FUNCTION calcOne */
61 unsigned long int retval = 1;
62 if (1 != in)
63 {
64 /* then */
65 retval = (0 == (in % 2)) ? in / 2 : 3 * in + 1 ;
66 } /* then */
67 return retval;
68 } /* END FUNCTION calcOne */
69
70 unsigned long int calc(unsigned long int in)
71 {
72 /* BEGIN FUNCTION calc */
73 unsigned long int retval;
74 int cnt = 1;
75 unsigned long int tmp;
76 unsigned long int t1;
77 int xx = 0;
78
79 /* printf("Enter calc (%d)\n", in); */
80 retval = in;
81 while (1 != retval)
82 {
83 /* while */
84 if (MAXSIZE > retval)
85 {
86 /* then */
87 if (0 != ary[retval])
88 {
89 /* then */
90 cnt = cnt + ary[retval] - 1;
91 } /* then */
92 else
93 {
94 /* else */
95 tmp = calcOne(retval);
96 t1 = calc(tmp);
97 cnt = cnt + t1;
98 ary[retval] = cnt - xx;
99 /* printf("Array updates: ary[%d] = (%d)\n", retval, ary[retval]); */
100 } /* else */
101 /* printf("retval=(%d) cnt=(%d)\n", retval, cnt); */
102 retval = 1;
103 } /* then */
104 else
105 {
106 /* else */
107 retval = calcOne(retval);
108 cnt++;
109 xx++;
110 /* printf("retval=(%d) cnt=(%d)\n", retval, cnt); */
111 } /* else */
112 } /* while */
113 return (cnt);
114 } /* BEGIN FUNCTION calc */
115
116 int process(int start, int stop)
117 {
118 /* BEGIN FUNCTION process */
119 int i;
120 int max = MININT;
121 int tmp;
122
123 for (i=start; i <= stop; i++)
124 {
125 /* for */
126 tmp = calc(i);
127 max = (max < tmp) ? tmp : max;
128 } /* for */
129
130 return max;
131 } /* END FUNCTION process */
132
133 int main ()
134 {
135 /* main */
136 int moreToDo; /* tell me when to stop */
137 int start; /* starting point */
138 int stop; /* stopping point */
139 int s1;
140 int s2;
141 unsigned long int ans; /* calculated answer */
142
143 /* init(); */
144 moreToDo = getInput(&start, &stop, &s1, &s2);
145 while (moreToDo)
146 {
147 /* while */
148 ans = process(s1, s2);
149 /* dump(); */
150 printf("%d %d %ld\n", start, stop, ans);
151 moreToDo = getInput(&start, &stop, &s1, &s2);
152 } /* while */
153
154 return 1;
155 } /* main */
156
157