/home/toolbox/public_html/solutions/126/12620/e.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdlib.h>
7 #include <math.h>
8 #include <stdint.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 /* fprintf(stderr, "functionName: message", varslist); */
16
17 /*
18 * Author: Isaac Traxler
19 * Date: 2015-10-04
20 * Purpose: fun
21 * Problem: 12620
22 */
23
24 /*
25 * This template reads data a specified number of times.
26 */
27
28 #define UPPER_LIMIT 300
29 #define BIG_NUMBER unsigned long long
30
31
32 int numberOfTimes;
33 BIG_NUMBER M;
34 BIG_NUMBER N;
35 BIG_NUMBER sum300;
36 int ans[UPPER_LIMIT];
37
38 int fib(int a, int b)
39 {
40 /* FUNCTION fib */
41
42 return ((a+b) % 100);
43 } /* FUNCTION fib */
44
45 BIG_NUMBER sum(BIG_NUMBER n, BIG_NUMBER m)
46 {
47 /* FUNCTION sum */
48 int i;
49 BIG_NUMBER tot = 0;
50
51 for (i=n; i<=m; i++)
52 {
53 /* for i */
54 tot = tot + ans[i % 300];
55 } /* for i */
56 return tot;
57 } /* FUNCTION sum */
58
59 void dump()
60 {
61 /* FUNCTION dump */
62 int i;
63
64 for (i=0; i<UPPER_LIMIT; i++)
65 {
66 /* for i */
67 if (0 == ans[i])
68 {
69 printf("%d ", i);
70 }
71 } /* for i */
72 printf("\n");
73 } /* FUNCTION dump */
74
75 void dump1()
76 {
77 /* FUNCTION dump1 */
78 int i;
79
80 for (i=0; i<100; i++)
81 {
82 /* for i */
83 printf("%d: %d\n", i, ans[i]);
84 } /* for i */
85 } /* FUNCTION dump1 */
86
87 void init()
88 {
89 /* FUNCTION init */
90 int i;
91
92 scanf("%d ", &numberOfTimes);
93 ans[0] = 0;
94 ans[1] = 1;
95 ans[2] = 1;
96 for (i=3; i<UPPER_LIMIT; i++)
97 {
98 /* for i */
99 ans[i] = fib(ans[i-1], ans[i-2]);
100 DEBUG printf("%d: %d\n", i, ans[i]);
101 DEBUG dump();
102 } /* for i */
103 DEBUG dump1();
104 sum300 = sum(0,299);
105 } /* FUNCTION init */
106
107 void getInput()
108 {
109 /* FUNCTION getInput */
110 scanf(" %Ld %Ld ", &N, &M);
111 } /* FUNCTION getInput */
112
113 void process()
114 {
115 /* FUNCTION process */
116 int i;
117 BIG_NUMBER n;
118 BIG_NUMBER m;
119 BIG_NUMBER tot = 0;
120
121 if (299 <= (M - N))
122 {
123 /* doing more than one pass through */
124 tot = ((M - N) / 300) * sum300;
125 } /* doing more than one pass through */
126 n = N % 300;
127 m = M % 300;
128 printf(" N: %Ld / 300 = %Ld R %Ld\n", N, N/300, N%300);
129 printf(" M: %Ld / 300 = %Ld R %Ld\n", M, M/300, M%300);
130
131 /* N=3 M=300 n=3 m=0 sum300 - sum(1,n) + sum(m,300) */
132 printf("tot[%Ld] ", tot);
133 if (m < n)
134 {
135 /* split case */
136 if (n > 1)
137 {
138 /* take beginning of sequence away */
139 tot = tot - sum(1,n-1);
140 printf(" - sum(1,%Ld-1)[%Ld]", n, sum(1,n-1));
141 } /* take beginning of sequence away */
142 tot = tot + sum(m, 300);
143 printf("+ sum(%Ld, 300)[%Ld];\n", m, sum(m,300));
144 } /* split case */
145 else
146 {
147 /* normal */
148 tot = tot + sum(n, m);
149 printf("+ sum(%Ld, %Ld)[%Ld];\n", n, m, sum(n,m));
150 } /* normal */
151 printf("%Ld\n", tot);
152
153 } /* FUNCTION process */
154
155 int main()
156 {
157 /* main */
158 int i;
159
160 init();
161 for (i=0; i<numberOfTimes; i++)
162 {
163 /* while */
164 getInput();
165 process();
166 } /* while */
167
168 return EXIT_SUCCESS;
169 } /* main */
170
171