Computer Programming Contest Preparation

    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 #define fib(a,b) ((a+b) % 100)
   32 
   33 int numberOfTimes;
   34 BIG_NUMBER M;
   35 BIG_NUMBER N;
   36 int ans[UPPER_LIMIT];
   37 BIG_NUMBER sums[UPPER_LIMIT+1];
   38 
   39 int fib1(int a, int b)
   40 {
   41     /* FUNCTION fib */
   42 
   43     return ((a+b) % 100);
   44 } /* FUNCTION fib */
   45 
   46 BIG_NUMBER sum1(BIG_NUMBER x)
   47 {
   48     /* FUNCTION sum */
   49     int i;
   50     BIG_NUMBER tot;
   51     BIG_NUMBER tmp;
   52     BIG_NUMBER tt;
   53 
   54     tt = x / 300;
   55     tot = tt * sums[300];
   56     tmp = x - (tt * 300);
   57     DEBUG printf("%Ld vs %Ld  x=%Ld  tt=%Ld  tot=%Ld\n", tmp, x-(tt*300), x, tt, tot);
   58     for (i=1; i<=tmp; i++)
   59         {
   60             /* for i */
   61             tot = tot + ans[i];
   62         } /* for i */
   63     return tot;
   64 } /* FUNCTION sum */
   65 
   66 BIG_NUMBER sum(BIG_NUMBER x)
   67 {
   68     /* FUNCTION sum */
   69     int i;
   70     BIG_NUMBER tot;
   71     BIG_NUMBER tmp;
   72     BIG_NUMBER tt;
   73 
   74     tt = x / 300;
   75     tot = tt * sums[300];
   76     tmp = x - (tt * 300);
   77     DEBUG printf("%Ld vs %Ld  x=%Ld  tt=%Ld  tot=%Ld\n", tmp, x-(tt*300), x, tt, tot);
   78     return (sums[tmp] + tot);
   79 } /* FUNCTION sum */
   80 
   81 void dump()
   82 {
   83     /* FUNCTION dump */
   84     int i;
   85 
   86     for (i=0; i<UPPER_LIMIT; i++)
   87         {
   88             /* for i */
   89             if (0 == ans[i])
   90                 {
   91                     printf("%d ", i);
   92                 }
   93         } /* for i */
   94     printf("\n");
   95 } /* FUNCTION dump */
   96 
   97 void dump1()
   98 {
   99     /* FUNCTION dump1 */
  100     int i;
  101 
  102     for (i=0; i<100; i++)
  103         {
  104             /* for i */
  105             printf("%d: %d\n", i, ans[i]);
  106         } /* for i */
  107 } /* FUNCTION dump1 */
  108 
  109 void init()
  110 {
  111     /* FUNCTION init */
  112     int i;
  113 
  114     scanf("%d ", &numberOfTimes);
  115     ans[0] = 0;
  116     sums[0] = 0;
  117     ans[1] = 1;
  118     sums[1] = 1;
  119     ans[2] = 1;
  120     sums[2] = 1;
  121     for (i=3; i<UPPER_LIMIT; i++)
  122         {
  123             /* for i */
  124             ans[i] = fib(ans[i-1], ans[i-2]);
  125             sums[i] = sums[i-1] + ans[i];
  126             DEBUG printf("%d: %d %d\n", i, ans[i], sums[i]);
  127             printf("%d: %d %d\n", i, ans[i], sums[i]);
  128             DEBUG dump();
  129         } /* for i */
  130     DEBUG dump1();
  131     sums[300] = sums[299] + 1;
  132 } /* FUNCTION init */
  133 
  134 void getInput()
  135 {
  136     /* FUNCTION getInput */
  137     scanf(" %Ld %Ld ", &N, &M);
  138 } /* FUNCTION getInput */
  139 
  140 void process()
  141 {
  142     /* FUNCTION process */
  143     int i;
  144     BIG_NUMBER tot = 0;
  145 
  146     tot = sum(M) - sum(N-1);
  147     printf("%Ld\n", tot);
  148 
  149 } /* FUNCTION process */
  150 
  151 int main()
  152 {
  153     /* main */
  154     int i;
  155 
  156     init();
  157     for (i=0; i<numberOfTimes; i++)
  158         {
  159             /* while */
  160             getInput();
  161             process();
  162         } /* while */
  163 
  164     return EXIT_SUCCESS;
  165 } /* main */
  166 
  167