## Intuition The problem requires us to find the minimum cost to obtain all three vitamins "A", "B", and "C" from a selection of juices. Each juice has a cost and contains a subset of these vitamins. The key insight is to consider all possible combinations of juices that can provide all three vitamins and find the one with the minimum cost. ## Approach 1. **Bitmask Representation**: Use a bitmask to represent the presence of vitamins. For example, if a juice contains vitamins "A" and "C", it can be represented as `101` in binary (or `5` in decimal). This allows us to efficiently check combinations of juices. 2. **Initialize Costs**: Create an array `minCost` of size 8 (since there are 2^3 possible combinations of vitamins) initialized to a large number, except for the combination `000` which should be 0 (cost of obtaining no vitamins). 3. **Update Costs**: For each juice, update the `minCost` array. If a juice provides a certain combination of vitamins, update the cost for that combination if the juice's cost is lower than the current recorded cost. 4. **Combine Costs**: Iterate over all pairs of vitamin combinations to find the minimum cost to obtain all vitamins. This involves checking all pairs `(i, j)` such that `i | j == 111` (binary for 7, meaning all vitamins are covered). 5. **Result**: The answer is the minimum cost found in the previous step. If no such combination exists, output `-1`. ## Complexity - **Time**: O(n), where n is the number of juices. We iterate over each juice and update the cost for a constant number of vitamin combinations. - **Space**: O(1), as we use a fixed-size array to store costs for each vitamin combination. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; const int INF = 1e9; vector minCost(8, INF); minCost[0] = 0; // Cost of obtaining no vitamins for (int i = 0; i < n; ++i) { int cost; string vitamins; cin >> cost >> vitamins; int mask = 0; for (char v : vitamins) { if (v == 'A') mask |= 1; if (v == 'B') mask |= 2; if (v == 'C') mask |= 4; } // Update the cost for this vitamin combination minCost[mask] = min(minCost[mask], cost); } int result = INF; // Check all combinations of vitamin masks for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { if ((i | j) == 7) { // If combination i and j cover all vitamins result = min(result, minCost[i] + minCost[j]); } } } if (result == INF) { cout << -1 << '\n'; } else { cout << result << '\n'; } return 0; } ``` This solution efficiently finds the minimum cost to obtain all three vitamins using bitmasking to represent vitamin combinations and dynamic programming to store the minimum cost for each combination.

Vitamins

Problem Details