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

#define MAX_SIZE 100000

int numbers[] = {-3, -6, -5, -15, 2, 7, 13, 16};
int count_numbers = 8;

int reconstruct(int *parents, int *ops, int target, int *result) {
    int size = 0;
    int cur = target;

    while (parents[cur] != -1) {
        result[size++] = ops[cur];
        cur = parents[cur];
    }

    for (int i = 0; i < size / 2; i++) {
        int temp = result[i];
        result[i] = result[size - 1 - i];
        result[size - 1 - i] = temp;
    }

    return size;
}

int shortest_path(int target, int *result) {
    if (target == 0) {
        return 0;
    }

    int *parents = (int *)malloc(sizeof(int) * (MAX_SIZE + 1));
    int *ops = (int *)malloc(sizeof(int) * (MAX_SIZE + 1));
    int *queue = (int *)malloc(sizeof(int) * (MAX_SIZE + 1));

    if (parents == NULL || ops == NULL || queue == NULL) {
        printf("Erreur d'allocation memoire.\n");
        free(parents);
        free(ops);
        free(queue);
        return -1;
    }

    for (int i = 0; i <= MAX_SIZE; i++) {
        parents[i] = -1;
        ops[i] = 0;
    }

    int front = 0, rear = 0;
    queue[rear++] = 0;
    parents[0] = -2;

    while (front < rear) {
        int current = queue[front++];

        for (int i = 0; i < count_numbers; i++) {
            int nxt = current + numbers[i];
            if (nxt < -MAX_SIZE || nxt > MAX_SIZE) {
                continue;
            }
            if (parents[nxt + MAX_SIZE] != -1) {
                continue;
            }

            parents[nxt + MAX_SIZE] = current + MAX_SIZE;
            ops[nxt + MAX_SIZE] = numbers[i];

            if (nxt == target) {
                int size = reconstruct(parents, ops, target, result);
                free(parents);
                free(ops);
                free(queue);
                return size;
            }

            queue[rear++] = nxt;
        }
    }

    free(parents);
    free(ops);
    free(queue);
    return -1;
}

int main(void) {
    int target;
    int result[MAX_SIZE];

    printf("Entrez le nombre souhaite : ");
    if (scanf("%d", &target) != 1) {
        printf("Veuillez entrer un nombre valide.\n");
        return 1;
    }

    int size = shortest_path(target, result);
    if (size == -1) {
        printf("Aucune solution trouvee.\n");
    } else {
        printf("Etapes : ");
        for (int i = 0; i < size; i++) {
            printf("%d", result[i]);
            if (i + 1 < size) {
                printf(" ");
            }
        }
        printf("\n");
    }

    return 0;
}