| 1 | from collections import Counter |
| 2 | from itertools import combinations |
| 3 | |
| 4 | |
| 1 | 5 | def total(basket): |
| 2 | | pass |
| 6 | if not basket: |
| 7 | return 0 |
| 8 | |
| 9 | # Edge Case: single book purchase |
| 10 | if len(basket) == 1: |
| 11 | return 800 # 800 cents = $8.00 |
| 12 | |
| 13 | # Count the frequency of each book |
| 14 | counts = Counter(basket) |
| 15 | frequencies = list(counts.values()) |
| 16 | |
| 17 | # Edge Case: all books are the same title |
| 18 | if len(counts) == 1: |
| 19 | return frequencies[0] * 800 |
| 20 | |
| 21 | # Calculate all possible groupings and find the minimum cost |
| 22 | return calculate_min_cost(frequencies) |
| 23 | |
| 24 | |
| 25 | def calculate_min_cost(frequencies): |
| 26 | # Convert to cents to avoid floating point errors |
| 27 | book_price = 800 # 800 cents = $8.00 |
| 28 | discounts = {1: 0, 2: 5, 3: 10, 4: 20, 5: 25} |
| 29 | |
| 30 | # Edge Case: empty basket |
| 31 | if not frequencies: |
| 32 | return 0 |
| 33 | |
| 34 | # Use dynamic programming with memoization |
| 35 | memo = {} |
| 36 | |
| 37 | def dp(freqs): |
| 38 | # Sort frequencies to normalize the state for memoization |
| 39 | freqs = tuple(sorted(freqs)) |
| 40 | |
| 41 | if freqs in memo: |
| 42 | return memo[freqs] |
| 43 | |
| 44 | # Edge Case: no books left |
| 45 | if not any(freqs): |
| 46 | return 0 |
| 47 | |
| 48 | min_cost = float('inf') |
| 49 | max_group_size = min(len(freqs), 5) |
| 50 | |
| 51 | # Try all possible group sizes from 1 to max_group_size |
| 52 | for group_size in range(1, max_group_size + 1): |
| 53 | # Try all combinations of books for this group size |
| 54 | # Since we're looking at frequencies, we just need to pick 'group_size' books |
| 55 | # that still have copies available |
| 56 | |
| 57 | # Find all books with non-zero counts |
| 58 | books_with_copies = [i for i, f in enumerate(freqs) if f > 0] |
| 59 | if len(books_with_copies) < group_size: |
| 60 | continue |
| 61 | |
| 62 | # Try all combinations of books for this group size |
| 63 | for book_indices in combinations(books_with_copies, group_size): |
| 64 | # Create a new frequency list after removing one copy of each book in this combination |
| 65 | new_freqs = list(freqs) |
| 66 | for idx in book_indices: |
| 67 | new_freqs[idx] -= 1 |
| 68 | |
| 69 | # Calculate cost for this grouping |
| 70 | discount = discounts[group_size] |
| 71 | group_cost = group_size * book_price * (100 - discount) // 100 |
| 72 | remaining_cost = dp(tuple(new_freqs)) |
| 73 | total_cost = group_cost + remaining_cost |
| 74 | |
| 75 | min_cost = min(min_cost, total_cost) |
| 76 | |
| 77 | memo[freqs] = min_cost |
| 78 | return min_cost |
| 79 | |
| 80 | return dp(tuple(frequencies)) |
| 81 | |
| 82 | # Handled Edge Cases: empty basket, single book purchase, all books are the same title |