aboutsummaryrefslogtreecommitdiff
path: root/Practical2/c
diff options
context:
space:
mode:
Diffstat (limited to 'Practical2/c')
-rw-r--r--Practical2/c/Makefile13
-rw-r--r--Practical2/c/checkout.c73
2 files changed, 0 insertions, 86 deletions
diff --git a/Practical2/c/Makefile b/Practical2/c/Makefile
deleted file mode 100644
index e64a1f7..0000000
--- a/Practical2/c/Makefile
+++ /dev/null
@@ -1,13 +0,0 @@
-CC=gcc
-OBJS=checkout
-
-.PHONY: all run clean
-
-all: $(OBJS)
-
-$(OBJS): % : %.c
- $(CC) -o $@ $<
-
-clean:
- rm $(OBJS)
-
diff --git a/Practical2/c/checkout.c b/Practical2/c/checkout.c
deleted file mode 100644
index 82eda3a..0000000
--- a/Practical2/c/checkout.c
+++ /dev/null
@@ -1,73 +0,0 @@
-#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;
- }
-}
-
-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) {
- profit[p][d] = 0;
- } else if (d == 0) {
- profit[p][d] = sums[0][p] - round_ct(sums[0][p]);
- } else {
- 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 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++) {
- scanf("%d", &(products[i]));
- sum += products[i];
- if (products[i] % 5 == 0) {
- n_products--;
- i--;
- }
- }
-
- printf("%d\n", sum - maximum_profit(products, n_products, dividers));
-}
-