aboutsummaryrefslogtreecommitdiff
path: root/Practical2
diff options
context:
space:
mode:
authorCamil Staps2015-11-30 20:45:39 +0100
committerCamil Staps2015-11-30 20:48:24 +0100
commitd7ded2f26819497366823edf0cdb586b5f4e8722 (patch)
treefd989bb381486e91a5d16f0a791a503d61fc069b /Practical2
parentPractical2 seems to work (diff)
C version practical2
Diffstat (limited to 'Practical2')
-rw-r--r--Practical2/c/Makefile15
-rw-r--r--Practical2/c/checkout.c57
-rwxr-xr-xPractical2/tester/test.sh16
3 files changed, 85 insertions, 3 deletions
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