From d7ded2f26819497366823edf0cdb586b5f4e8722 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Mon, 30 Nov 2015 20:45:39 +0100
Subject: C version practical2

---
 Practical2/c/Makefile     | 15 +++++++++++++
 Practical2/c/checkout.c   | 57 +++++++++++++++++++++++++++++++++++++++++++++++
 Practical2/tester/test.sh | 16 ++++++++++---
 3 files changed, 85 insertions(+), 3 deletions(-)
 create mode 100644 Practical2/c/Makefile
 create mode 100644 Practical2/c/checkout.c

(limited to 'Practical2')

diff --git a/Practical2/c/Makefile b/Practical2/c/Makefile
new file mode 100644
index 0000000..270a693
--- /dev/null
+++ b/Practical2/c/Makefile
@@ -0,0 +1,15 @@
+CC=gcc
+
+.PHONY: all run clean
+
+all: checkout
+
+checkout:
+	$(CC) -o checkout checkout.c
+
+run:
+	./checkout
+
+clean:
+	rm checkout
+
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));
+}
+
diff --git a/Practical2/tester/test.sh b/Practical2/tester/test.sh
index f0f46e8..693ceda 100755
--- a/Practical2/tester/test.sh
+++ b/Practical2/tester/test.sh
@@ -1,15 +1,25 @@
 #!/bin/bash
 java="/usr/lib/jvm/java-8-openjdk-amd64/bin/java"
 
+# Java
+#dir="$(dirname $0)/../out/production/Practical2"
+#samples="../../../tester/samples"
+#cmd="$java nl.camilstaps.cs.Main"
+
+# C
+dir="$(dirname $0)/../c"
+samples="../tester/samples"
+cmd="./checkout"
+
 failed=0
 
-cd "$(dirname $0)/../out/production/Practical2"
-for tc in ../../../tester/samples/*.in; do
+cd "$dir"
+for tc in "$samples/"*.in; do
     answer=$(cat ${tc/in/out})
     header=$(head -n1 "$tc" | tr -d '\n')
     echo -n "Running $(basename $tc) $(printf '%-12s' "($answer ")$(printf '%-12s' "/ $header)") ... "
     time_start=$(($(date +%s%N)/1000000))
-    result=$(eval "cat '$tc' | /usr/lib/jvm/java-8-openjdk-amd64/bin/java nl.camilstaps.cs.Main")
+    result=$(eval "cat '$tc' | $cmd")
     time_end=$(($(date +%s%N)/1000000))
     time=`expr $time_end - $time_start`
     if [ $result != $answer ]; then
-- 
cgit v1.2.3