ACM UVA (10183)

/*
 *******************************************************************************
 *
 * Filename: 10183.c
 *
 * Author: Ye Xiaofeng , yexfeng # gmail.com
 *
 *******************************************************************************
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct strnumber {
    int len;
    char value[150];
};

#define VALUE(num) ( num->value + 150 - 1 - num->len )

struct strnumber *strnumber_new(char *number)
{
    struct strnumber *new_number;

    new_number = (struct strnumber *)malloc(sizeof(struct strnumber));
    new_number->len = 0;
    memset(new_number->value, '0', 150);
    new_number->len = strlen(number);
    strcpy(new_number->value+150-1-new_number->len, number);

    return new_number;
}

void strnumber_set_number(struct strnumber *number, char *str)
{
    number->len = 0;
    memset(number->value, '0', 150);
    number->len = strlen(str);
    strcpy(number->value+150-1-number->len, str);
}

void strnumber_plusplus(struct strnumber *number)
{
    char *p;
    int carray_flag = 0;
    int i;
    char *value = number->value;

    i = 1;
    do {
        p = &value[150-1-i];
        if (i > number->len) {
            *p = '1';
            number->len++;
        } else {
            (*p)++;
        }
        if (*p - '0' >= 10) {
            *p = '0';
            carray_flag = 1;
        } else {
            carray_flag = 0;
        }
        i++;
    } while (carray_flag != 0);
}

void strnumber_free(struct strnumber *number)
{
    if (NULL != number) {
        free(number);
        number = NULL;
    }
}


void strnumber_empty(struct strnumber *num)
{
    memset(num->value, '0', 150);
    num->value[150-1] = '\0';
    num->len = 0;
}

int strnumber_cmp_str(struct strnumber *num, char *str)
{
    char *p1 = VALUE(num);
    char *p2 = str;
    int len;

    len = strlen(str);
    if (num->len != len) {
        return (num->len < len) ? -1 : 1;
    } else {
        while (*p1 != '\0' && *p2 != '\0') {
            if (*p1 != *p2) {
                return (*p1 < *p2) ? -1 : 1;
            }
            ++p1;
            ++p2;
        }
        return 0;
    }

}

/*
 * Compare two strnumber.
 * Return 0 if num1 is equle to num2.
 * Return -1 if num1 is less than num2.
 * Return 1 if num1 is greater than num2.
 */
int strnumber_cmp_strnumber(struct strnumber *num1, struct strnumber *num2)
{

    if (num1->len != num2->len) {
        return (num1->len < num2->len) ? -1 : 1;
    } else {
        return strnumber_cmp_str(num1, VALUE(num2));
    }
}


void strnumber_add1(struct strnumber *result_num,
                    struct strnumber *src_num)
{
    char *cursor1;
    char *cursor2;
    int carry_flag = 0;
    int i;

    cursor1 = &result_num->value[150-2];
    cursor2 = &src_num->value[150-2];

    i = 1;
    while (i <= src_num->len || carry_flag == 1) {
        if (i > result_num->len) {
            *cursor1 = *cursor2 - '0' + carry_flag;
            result_num->len++;
        } else {
            *cursor1 = *cursor1 + *cursor2 + carry_flag - 2 * '0';
        }
        if (*cursor1 >= 10) {
            carry_flag = 1;
            *cursor1 = '0' + *cursor1 - 10;
        } else {
            *cursor1 = '0' + *cursor1;
            carry_flag = 0;
        }
        --cursor1;
        --cursor2;
        ++i;
    }

}

void strnumber_add2(struct strnumber *result_num,
                    struct strnumber *src_num1,
                    struct strnumber *src_num2)
{
    char *cursor1;
    char *cursor2;
    char *cursor_result;
    int carry_flag = 0;
    int i;

    strnumber_empty(result_num);
    cursor_result = &result_num->value[150-2];
    cursor1 = &src_num1->value[150-2];
    cursor2 = &src_num2->value[150-2];

    i = 1;
    while (i <= src_num1->len || i <= src_num2->len || carry_flag == 1) {
        *cursor_result = *cursor1 - '0' + *cursor2 - '0' + carry_flag;
        if (*cursor_result >= 10) {
            *cursor_result = '0' + *cursor_result - 10;
            carry_flag = 1;
        } else {
            *cursor_result += '0';
            carry_flag = 0;
        }

        --cursor1;
        --cursor2;
        --cursor_result;
        result_num->len++;
        ++i;
    }
}

int count(char *lstr, char *rstr)
{
    static struct strnumber *number1 = NULL;
    static struct strnumber *number2 = NULL;
    static struct strnumber *number3 = NULL;
    struct strnumber *number_tmp = NULL;
    int i;

    if (number1 == NULL) {
        number1 = strnumber_new("0");
        number2 = strnumber_new("1");
        number3 = strnumber_new("");
    } else {
        strnumber_set_number(number1, "0");
        strnumber_set_number(number2, "1");
    }

    i = 0;
    strnumber_add2(number3, number1, number2);
    while (strnumber_cmp_str(number3, rstr) <= 0) {
        if (i == 0) {
            if (strnumber_cmp_str(number3, lstr) >= 0) {
                i++;
            }
        } else {
            i++;
        }
        number_tmp = number1;
        number1 = number2;
        number2 = number3;
        number3 = number_tmp;
        strnumber_add2(number3, number1, number2);
    }

    printf("%d\n", i);
    return i;
}

int main(int argc, char **argv)
{
    char lstr[200];
    char rstr[200];

    scanf("%s %s", lstr, rstr);
    while (strcmp(lstr, "0") != 0 || strcmp(rstr, "0") != 0) {
        count(lstr, rstr);
        scanf("%s %s", lstr, rstr);
    }

    return 0;
}