#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>

#define MAX_N 1024
#define WORDS ((MAX_N / 64) + 1)
#define ITERATIONS 10000000
#define NUMBER 86

// ==========================================
// 1. TRADITIONAL DP (FOR-LOOP) APPROACH
// ==========================================
int min_coins_dp(int n, int* coins, int num_coins) {
    int dp[MAX_N + 1];
    dp[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        dp[i] = 1000000; // Represent "infinity"
        for (int c = 0; c < num_coins; c++) {
            if (i >= coins[c]) {
                if (dp[i - coins[c]] + 1 < dp[i]) {
                    dp[i] = dp[i - coins[c]] + 1;
                }
            }
        }
    }
    return dp[n] == 1000000 ? -1 : dp[n];
}

// ==========================================
// 2. NATIVE BITWISE APPROACH
// ==========================================
void shift_left_and_or(uint64_t* dest, const uint64_t* src, int shift) {
    int word_shift = shift / 64;
    int bit_shift = shift % 64;

    for (int i = WORDS - 1; i >= word_shift; i--) {
        int src_idx = i - word_shift;
        uint64_t val = src[src_idx] << bit_shift;
        
        if (bit_shift > 0 && src_idx > 0) {
            val |= (src[src_idx - 1] >> (64 - bit_shift));
        }
        dest[i] |= val;
    }
}

int min_coins_bitwise(int n, int* coins, int num_coins) {
    if (n == 0) return 0;
    if (n > MAX_N) return -1;

    uint64_t state[WORDS] = {0}; 
    state[0] = 1ULL; 
    uint64_t next_state[WORDS];
    
    int steps = 0;
    int target_word = n / 64;
    int target_bit  = n % 64;
    uint64_t target_mask = 1ULL << target_bit;

    while (1) {
        steps++;
        memset(next_state, 0, sizeof(next_state));

        for (int c = 0; c < num_coins; c++) {
            shift_left_and_or(next_state, state, coins[c]);
        }

        if (next_state[target_word] & target_mask) {
            return steps;
        }

        memcpy(state, next_state, sizeof(state));
    }
}

// ==========================================
// 2. HIGH-PERFORMANCE BITWISE APPROACH
// ==========================================
int min_coins_bitwise_optimized(int n, int* coins, int num_coins) {
    if (n == 0) return 0;
    if (n > MAX_N) return -1;

    // How many 64-bit blocks do we ACTUALLY need for this 'n'?
    int active_words = (n / 64) + 1;
    
    // Allocate two arrays to act as our "Current" and "Next" states
    uint64_t bufferA[WORDS] = {0};
    uint64_t bufferB[WORDS] = {0};
    
    bufferA[0] = 1ULL; 
    
    // We will use pointers so we never have to use memcpy()!
    uint64_t* state = bufferA;
    uint64_t* next_state = bufferB;

    int steps = 0;
    int target_word = n / 64;
    uint64_t target_mask = 1ULL << (n % 64);

    while (1) {
        steps++;
        
        // Manual clearing is faster than memset because we ONLY clear active_words
        for (int i = 0; i < active_words; i++) {
            next_state[i] = 0;
        }

        // Apply coins using inline logic for maximum speed
        for (int c = 0; c < num_coins; c++) {
            int shift = coins[c];
            int w_shift = shift / 64;
            int b_shift = shift % 64;

            // Only loop up to active_words! No useless math.
            for (int i = active_words - 1; i >= w_shift; i--) {
                int src_idx = i - w_shift;
                uint64_t val = state[src_idx] << b_shift;
                
                if (b_shift > 0 && src_idx > 0) {
                    val |= (state[src_idx - 1] >> (64 - b_shift));
                }
                next_state[i] |= val;
            }
        }

        // Did we hit the target?
        if (next_state[target_word] & target_mask) {
            return steps;
        }

        // SWAP POINTERS! (Takes 0.000000001 seconds, completely eliminates memcpy)
        uint64_t* temp = state;
        state = next_state;
        next_state = temp;
    }
}

// ==========================================
// MAIN BENCHMARK
// ==========================================
int main() {
    int ukraine_coins[] = {1, 2, 5, 10, 25, 50};
    int num_coins = 6;
    int n = NUMBER; // 868 cents (Answer: 17 coins + 10 + 5 + 2 + 1 = 21 coins)
    
    printf("Evaluating N = %d over %d iterations...\n\n", n, ITERATIONS);

    clock_t start, end;
    double cpu_time_used;
    volatile int total_sum = 0; // volatile prevents compiler loop-deletion

    // --- Benchmark DP ---
    start = clock();
    for (int i = 0; i < ITERATIONS; i++) {
        total_sum += min_coins_dp(n, ukraine_coins, num_coins);
    }
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("1. Traditional DP Time: %f seconds (Answer: %d)\n", cpu_time_used, total_sum / ITERATIONS);

    // --- Benchmark Bitwise ---
    total_sum = 0; // Reset
    start = clock();
    for (int i = 0; i < ITERATIONS; i++) {
        total_sum += min_coins_bitwise(n, ukraine_coins, num_coins);
    }
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("2. Native Bitwise Time: %f seconds (Answer: %d)\n", cpu_time_used, total_sum / ITERATIONS);

        // --- Benchmark Bitwise Optimized---
    total_sum = 0; // Reset
    start = clock();
    for (int i = 0; i < ITERATIONS; i++) {
        total_sum += min_coins_bitwise_optimized(n, ukraine_coins, num_coins);
    }
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("3. Optimized Bitwise Time: %f seconds (Answer: %d)\n", cpu_time_used, total_sum / ITERATIONS);
    return 0;
}