aboutsummaryrefslogtreecommitdiff
path: root/Practical2
diff options
context:
space:
mode:
authorCamil Staps2015-12-10 08:42:56 +0000
committerCamil Staps2015-12-10 08:42:56 +0000
commit55748d704df7242b1acedae79c2eea7616eac2a9 (patch)
tree461e9ab103148d93b0873812c4bd9224a0b1cd50 /Practical2
parentRemoved Java Practical2; moved C to main directory (diff)
Faster implementation, test enhancement Practical2
Tester strings are padded nicely. Implementation uses less memory and is faster with -Ofast.
Diffstat (limited to 'Practical2')
-rw-r--r--Practical2/Makefile2
-rw-r--r--Practical2/checkout.c31
-rwxr-xr-xPractical2/tester/test.sh2
3 files changed, 17 insertions, 18 deletions
diff --git a/Practical2/Makefile b/Practical2/Makefile
index e64a1f7..0b147dd 100644
--- a/Practical2/Makefile
+++ b/Practical2/Makefile
@@ -6,7 +6,7 @@ OBJS=checkout
all: $(OBJS)
$(OBJS): % : %.c
- $(CC) -o $@ $<
+ $(CC) -o $@ $< -Ofast
clean:
rm $(OBJS)
diff --git a/Practical2/checkout.c b/Practical2/checkout.c
index 82eda3a..738aa61 100644
--- a/Practical2/checkout.c
+++ b/Practical2/checkout.c
@@ -12,33 +12,32 @@ uint32_t round_ct(uint32_t cents) {
}
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++) {
+ uint32_t sums[p];
+ if (p == 0) {
+ sums[0] = 0;
+ } else {
+ int16_t i;
+ for (i = p-1; i >= 0; i--) {
+ if (i == p-1)
+ sums[i] = products[i];
+ else
+ sums[i] = products[i] + sums[i+1];
+ }
+ }
+
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]);
+ profit[p][d] = sums[0] - round_ct(sums[0]);
} 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]);
+ int32_t try = profit[i][d-1] + sums[i] - round_ct(sums[i]);
if (try > max)
max = try;
}
diff --git a/Practical2/tester/test.sh b/Practical2/tester/test.sh
index 9051e97..8f42b77 100755
--- a/Practical2/tester/test.sh
+++ b/Practical2/tester/test.sh
@@ -9,7 +9,7 @@ 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)") ... "
+ echo -n "Running $(printf '%-15s' "$(basename $tc)") $(printf '%-10s' "($answer ")$(printf '%-10s' "/ $header)") ... "
time_start=$(($(date +%s%N)/1000000))
result=$(eval "cat '$tc' | $cmd")
time_end=$(($(date +%s%N)/1000000))