1 files changed, 57 insertions, 0 deletions
diff --git a/Practical2/c/checkout.c b/Practical2/c/checkout.c
new file mode 100644
index 0000000..7c39a0b
--- /dev/null
+++ b/Practical2/c/checkout.c
@@ -0,0 +1,57 @@
+#include <stdio.h>
+#include <stdint.h>
+
+uint32_t round_ct(uint32_t cents) {
+    switch (cents % 5) {
+        case 0: return cents;
+        case 1: return cents - 1;
+        case 2: return cents - 2;
+        case 3: return cents + 2;
+        case 4: return cents + 1;
+    }
+}
+
+uint32_t minimum_payment(uint16_t products[], uint16_t n_products, uint8_t dividers) {
+    uint32_t minimums[n_products+1][dividers+1];
+    uint32_t last[n_products+1][dividers+1];
+
+    uint16_t p, d, q;
+
+    for (p = 0; p <= n_products; p++) {
+        for (d = 0; d <= dividers; d++) {
+            if (p == 0 || d == 0) {
+                uint32_t sum = 0;
+                for (q = 0; q < n_products && q < p; q++)
+                    sum += products[q];
+                minimums[p][d] = round_ct(sum);
+                last[p][d] = sum;
+            } else {
+                uint16_t try1 = minimums[p-1][d] - round_ct(last[p-1][d]) + round_ct(last[p-1][d] + products[p-1]);
+                uint16_t try2 = minimums[p-1][d-1] + round_ct(products[p-1]);
+                if (try1 < try2) {
+                    minimums[p][d] = try1;
+                    last[p][d] = last[p-1][d] + products[p-1];
+                } else {
+                    minimums[p][d] = try2;
+                    last[p][d] = products[p-1];
+                }
+            }
+        }
+    }
+
+    return minimums[n_products][dividers];
+}
+
+int main(void) {
+    int n_products;
+    int dividers;
+    scanf("%d %d", &n_products, &dividers);
+
+    uint16_t products[n_products];
+    uint16_t i;
+    for (i = 0; i < n_products; i++)
+        scanf("%d", &(products[i]));
+
+    printf("%d\n", minimum_payment(products, n_products, dividers));
+}
+