From 71f8ddbaa83e15492401cb6fa6a7a2d54284f316 Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Wed, 9 Dec 2015 23:24:29 +0000
Subject: Working solution Practical 2, small fixes

 - Makefile: less dependent on program name
 - test.sh: quote variables
 - checkout.c: almost completely new algorithm. This one actually works.
   At least it does on the test cases.
---
 Practical2/c/Makefile     | 12 ++++------
 Practical2/c/checkout.c   | 60 ++++++++++++++++++++++++++++++-----------------
 Practical2/tester/test.sh |  2 +-
 3 files changed, 44 insertions(+), 30 deletions(-)

(limited to 'Practical2')

diff --git a/Practical2/c/Makefile b/Practical2/c/Makefile
index 270a693..e64a1f7 100644
--- a/Practical2/c/Makefile
+++ b/Practical2/c/Makefile
@@ -1,15 +1,13 @@
 CC=gcc
+OBJS=checkout
 
 .PHONY: all run clean
 
-all: checkout
+all: $(OBJS)
 
-checkout:
-	$(CC) -o checkout checkout.c
-
-run:
-	./checkout
+$(OBJS): % : %.c
+	$(CC) -o $@ $<
 
 clean:
-	rm checkout
+	rm $(OBJS)
 
diff --git a/Practical2/c/checkout.c b/Practical2/c/checkout.c
index 7c39a0b..82eda3a 100644
--- a/Practical2/c/checkout.c
+++ b/Practical2/c/checkout.c
@@ -11,47 +11,63 @@ uint32_t round_ct(uint32_t cents) {
     }
 }
 
-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;
+int32_t maximum_profit(uint16_t products[], uint16_t n_products, uint8_t dividers) {
+    uint32_t sums[n_products+1][n_products+1];
+    uint16_t i, j;
+    for (i = 0; i <= n_products; i++) {
+        for (j = 0; j <= n_products; j++) {
+            if (j <= i) {
+                sums[i][j] = 0;
+            } else if (j == 1) {
+                sums[i][j] = products[0];
+            } else {
+                sums[i][j] = sums[i][j-1] + products[j-1];
+            }
+        }
+    }
 
+    int32_t profit[n_products+1][dividers+1];
+    uint16_t p, d;
     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;
+            if (p == 0) {
+                profit[p][d] = 0;
+            } else if (d == 0) {
+                profit[p][d] = sums[0][p] - round_ct(sums[0][p]);
             } 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];
+                int32_t max = profit[p][d-1];
+                uint16_t i;
+                for (i = 0; i < p; i++) {
+                    int32_t try = profit[i][d-1] + sums[i][p] - round_ct(sums[i][p]);
+                    if (try > max)
+                        max = try;
                 }
+                profit[p][d] = max;
             }
         }
     }
 
-    return minimums[n_products][dividers];
+    return profit[n_products][dividers];
 }
 
 int main(void) {
     int n_products;
     int dividers;
+    uint32_t sum = 0;
+
     scanf("%d %d", &n_products, &dividers);
 
     uint16_t products[n_products];
     uint16_t i;
-    for (i = 0; i < n_products; i++)
+    for (i = 0; i < n_products; i++) {
         scanf("%d", &(products[i]));
+        sum += products[i];
+        if (products[i] % 5 == 0) {
+            n_products--;
+            i--;
+        }
+    }
 
-    printf("%d\n", minimum_payment(products, n_products, dividers));
+    printf("%d\n", sum - maximum_profit(products, n_products, dividers));
 }
 
diff --git a/Practical2/tester/test.sh b/Practical2/tester/test.sh
index 693ceda..4a982ac 100755
--- a/Practical2/tester/test.sh
+++ b/Practical2/tester/test.sh
@@ -22,7 +22,7 @@ for tc in "$samples/"*.in; do
     result=$(eval "cat '$tc' | $cmd")
     time_end=$(($(date +%s%N)/1000000))
     time=`expr $time_end - $time_start`
-    if [ $result != $answer ]; then
+    if [ "$result" != "$answer" ]; then
         echo "failure ($time ms)."
         failed=$(($failed+1))
     else
-- 
cgit v1.2.3