diff options
author | Camil Staps | 2015-12-10 08:42:56 +0000 |
---|---|---|
committer | Camil Staps | 2015-12-10 08:42:56 +0000 |
commit | 55748d704df7242b1acedae79c2eea7616eac2a9 (patch) | |
tree | 461e9ab103148d93b0873812c4bd9224a0b1cd50 /Practical2 | |
parent | Removed 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/Makefile | 2 | ||||
-rw-r--r-- | Practical2/checkout.c | 31 | ||||
-rwxr-xr-x | Practical2/tester/test.sh | 2 |
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)) |