big_seq.c

//https://thehuxley.com/problem/862/oracle?quizId=6096
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DEBUG if (1)
#define MAX 100001
typedef struct node
{
    char item;
    struct node *next;
} NODE;

NODE *  create_list()
{
    return NULL;
}

NODE *add(NODE *head, char item)
{
    NODE *new_node = (NODE *)malloc(sizeof(NODE));
    new_node->item = item;
    new_node->next = head;
    //DEBUG printf("adicionado[[[%d]]]\t",new_node->item);
    return new_node;
}

int is_empty(NODE *head)
{
    return (head == NULL);
}

void printer(NODE *head)
{
    if (head == NULL)
    {
        printf("Lista vazia!\n");
    }
    while (head != NULL)
    {
        printf("[%d]", head->item);
        head = head->next;
    }
    printf("Fim da Lista!\n");
}

NODE *search(NODE *head, char item)
{
    // printf("to dentro do search\n");
    while (head != NULL)
    {
        if (head->item == item)
        {
            // printf("ENCONTREI MAIS UM!!! [%d]\n", item);
            return head; //retorna o endereço que contém o item
        }
        head = head->next;
    }
    return NULL;
}

int search_2(NODE *head, char item)//função para procurar a melhor sequencia
{
    DEBUG printf("######### Procurando por: [%c] ##########\n", item);
    int count = 0;
    while (head != NULL)
    {
        DEBUG printf("head->item = [%c]\t",head->item);
        if (head->item == item)
        {
            count++;
            //DEBUG printf("ENCONTREI MAIS UM!!! [%d]\n", item);
            DEBUG printf("voltas: [%d]\n",count);
            return count; //retorna o endereço que contém o item
        }
        head = head->next;
        count++;
        DEBUG printf("voltas: [%d]\n",count);
    }
    return 0;
}

void func(NODE *head, int size, int beg, int end)//first_one, 1,
{
    NODE* first_zero = search(head,'0');//recebo o endereço do primeiro zero.
    int beg_new = search_2(head,'0')+beg;//recebe a posição do primeiro zero
    DEBUG printf("\tComeço encontrado: [%d]\n",beg_new);

    int size1 = search_2(first_zero,'1')-1; //a partir do endereço do primeiro zero, procuro o proximo 1 e recebo o tamanho deste intervalo
    int end_new = beg_new+size1-1;//end é a posição final
    DEBUG printf("\tFim encontrado: [%d]\n",end_new);
    DEBUG printf("TAMANHO: [%d]\n",size1);
    NODE* first_one = search(first_zero,'1'); //will be my new head
    if(first_zero == NULL || first_one == NULL)//break
    {
        printf("%d %d\n",beg,end);
        return;
    }

    if (size1>size)
    {
        DEBUG printf("\n------- FUNC 1 --------\n");
        func(first_one, size1, beg_new, end_new);
    }
    else{
        DEBUG printf("\n------- FUNC 2 --------\n\n");
        func(first_zero,size,beg,end);
    }

}
int main()
{
    char input[MAX];
    NODE *lista1 = create_list(); //nó que aponta para nulo
    do
    {
        scanf("%s", input);
        int q = strlen(input);
        if(q == 1 && input[0] == '0') break;
        for (int i = q-1; i >= 0 ; i--)
        {
            //DEBUG printf("Adicionado [%c].\n",input[i]);
            lista1 = add(lista1, input[i]);
        }
        func(lista1, 0,0,0);
    } while (1);


    return 0;
}