/home/toolbox/public_html/solutions/1/100/xx.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 int tmp;
36
37 moreToDo = EOF != scanf("%d ", start);
38 /* printf("moreToDo=[%d]\n",moreToDo); */
39 if (moreToDo)
40 {
41 /* then */
42 scanf("%d ", stop);
43 if (*start > *stop)
44 {
45 /* then */ *s1 = *start; /* else */
46 *s2 = *stop;
47 } /* then */ else
48 {
49 /* else */ *s1 = *stop;
50 *s2 = *start;
51 }
52 } /* then */
53 return moreToDo;
54 } /* END FUNCTION getInput */
55
56 unsigned long int calcOne(unsigned long int in)
57 {
58 /* BEGIN FUNCTION calcOne */
59 unsigned long int retval = 1;
60 if (1 != in)
61 {
62 /* then */
63 retval = (0 == (in % 2)) ? in / 2 : 3 * in + 1 ;
64 } /* then */
65 return retval;
66 } /* END FUNCTION calcOne */
67
68 unsigned long int calc(unsigned long int in)
69 {
70 /* BEGIN FUNCTION calc */
71 unsigned long int retval;
72 int cnt = 1;
73 unsigned long int tmp;
74 unsigned long int t1;
75 int xx = 0;
76
77 /* printf("Enter calc (%d)\n", in); */
78 /* if (0 == (tot % 10000)) */
79 /* { */
80 /* tot = 0; */
81 /* tot1++; */
82 /* printf("tot1=(%ld)\n", tot1); */
83 /* } */
84 /* tot++; */
85 retval = in;
86 while ((1 != retval) && (retval > 0))
87 {
88 /* while */
89 if (MAXSIZE > retval)
90 {
91 /* then */
92 if (0 != ary[retval])
93 {
94 /* then */
95 cnt = cnt + ary[retval] - 1;
96 } /* then */
97 else
98 {
99 /* else */
100 tmp = calcOne(retval);
101 t1 = calc(tmp);
102 cnt = cnt + t1;
103 ary[retval] = cnt - xx;
104 /* printf("Array updates: ary[%d] = (%d)\n", retval, ary[retval]); */
105 } /* else */
106 /* printf("retval=(%d) cnt=(%d)\n", retval, cnt); */
107 retval = 1;
108 } /* then */
109 else
110 {
111 /* else */
112 retval = calcOne(retval);
113 cnt++;
114 xx++;
115 /* printf("retval=(%d) cnt=(%d)\n", retval, cnt); */
116 } /* else */
117 } /* while */
118 return (cnt);
119 } /* BEGIN FUNCTION calc */
120
121 int process(int start, int stop)
122 {
123 /* BEGIN FUNCTION process */
124 int i;
125 int max = MININT;
126 int tmp;
127
128 for (i=start; i >= stop; i--)
129 {
130 /* for */
131 tmp = calc(i);
132 max = (max < tmp) ? tmp : max;
133 } /* for */
134
135 return max;
136 } /* END FUNCTION process */
137
138 int main ()
139 {
140 /* main */
141 int moreToDo; /* tell me when to stop */
142 int start; /* starting point */
143 int stop; /* stopping point */
144 int s1;
145 int s2;
146 unsigned long int ans; /* calculated answer */
147
148 /* init(); */
149 moreToDo = getInput(&start, &stop, &s1, &s2);
150 while (moreToDo)
151 {
152 /* while */
153 ans = process(s1, s2);
154 /* dump(); */
155 printf("%d %d %ld\n", start, stop, ans);
156 moreToDo = getInput(&start, &stop, &s1, &s2);
157 } /* while */
158
159 return 0;
160 } /* main */
161