aboutsummaryrefslogtreecommitdiff
path: root/Practical2
diff options
context:
space:
mode:
authorCamil Staps2015-12-09 23:24:29 +0000
committerCamil Staps2015-12-09 23:24:29 +0000
commit71f8ddbaa83e15492401cb6fa6a7a2d54284f316 (patch)
treeb7554e9fcc25cc2c7b9117906da3d3b8b632e6ea /Practical2
parentRemoved redundant packages (diff)
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.
Diffstat (limited to 'Practical2')
-rw-r--r--Practical2/c/Makefile12
-rw-r--r--Practical2/c/checkout.c60
-rwxr-xr-xPractical2/tester/test.sh2
3 files changed, 44 insertions, 30 deletions
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