Cod sursa(job #954153)

Utilizator mihai_r2005Richard Mihai Andrei mihai_r2005 Data 28 mai 2013 13:18:52
Problema Loto Scor 5
Compilator c Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct _listitem
{
    struct _listitem *next;
    int plus;
    int sum;
    struct _listitem *predec;
} ListItem;

void addListItem(ListItem **list, int sum, int plus, ListItem* predec)
{
    if (*list == NULL) {
        *list = malloc(sizeof(ListItem));
        (*list)->sum = sum;
        (*list)->plus = plus;
        (*list)->predec = predec;
        (*list)->next = NULL;
    } else {
        ListItem *llist = *list;
        ListItem *pre = NULL;
        while (llist != NULL) {
            if (sum == llist->sum)
                return;
            pre = llist;
            llist = llist->next;
        }
        pre->next = malloc(sizeof(ListItem));
        llist = pre->next;
        llist->sum = sum;
        llist->plus = plus;
        llist->next = NULL;
        llist->predec = predec;
    }
}

void printSol(FILE *fo, ListItem *list){
    while (list != NULL) {
        fprintf(fo, "%d ", list->plus);
        list = list->predec;
    }
}

int main(int argc, const char * argv[])
{
    int n = 0;
    int s = 0;
    int nums[100];
    ListItem* lists[6];
    
    FILE *fi = fopen("loto.in", "r");
    FILE *fo = fopen("loto.out", "w");
    
    // Read input
    fscanf(fi, "%d", &n);
    fscanf(fi, "%d", &s);
    for (int i = 0; i < n; i++) {
        fscanf(fi, "%d", &nums[i]);
    }
    
    // Calc answer
    lists[0] = NULL;
    for (int i = 0; i < n; i++) {
        addListItem(&lists[0], nums[i], nums[i], NULL);
    }
    for (int c = 1; c < 6; c++) {
        lists[c] = NULL;
        ListItem *llist = lists[c-1];
        while (llist != NULL) {
            for (int i = 0; i < n; i++) {
                if (llist->sum + nums[i] <= s) {
                    addListItem(&lists[c], llist->sum + nums[i], nums[i], llist);
                }
            }
            llist = llist->next;
        }
    }
    
    // Search answer and print it
    char foundSol = 0;
    ListItem *llist = lists[5];
    while (llist->next != NULL) {
        if (llist->sum == s) {
            foundSol = 1;
            printSol(fo, llist);
        }
        
        llist = llist->next;
    }
    
    if (!foundSol) {
        fprintf(fo, "-1\n");
    }
    
    fflush(fo);
    fclose(fi);
    fclose(fo);
    return 0;
}