Contagem de Espetinhos Válidos

Prévia do material em texto

Kabob Skewers — Solution
Author
SigmaCamp Submission
Problem Summary
Given a bin layout (4 bins of 3 ingredients each) and queries of the form (start ingredient, end
ingredient, length k), count the number of valid skewers of exactly k ingredients that start at the
given start ingredient and end at the given end ingredient, where two consecutive ingredients
cannot come from the same bin.
Solution Code
def solve(input_file='input.txt', output_file='output.txt'):
 with open(input_file, 'r') as f:
 lines = f.read().strip().split('\n')
 # Parse bin layout
 bin_layout = lines[0].strip()
 bins = [b.strip().split() for b in bin_layout.split('|')]
 # Map each ingredient to its bin index
 ingredient_to_bin = {}
 for bin_idx, ingredients in enumerate(bins):
 for ing in ingredients:
 ingredient_to_bin[ing.strip()] = bin_idx
 # Parse queries
 q = int(lines[1].strip())
 queries = []
 for i in range(2, 2 + q):
 parts = lines[i].strip().split()
 start = parts[0]
 end = parts[1]
 k = int(parts[2])
 queries.append((start, end, k))
 results = []
 for start, end, k in queries:
 start_bin = ingredient_to_bin[start]
 end_bin = ingredient_to_bin[end]
 if k == 1:
 results.append(1 if start == end else 0)
 continue
 # DP grouped by bins for efficiency.
 # S[b] = sum of paths ending at any ingredient in bin b.
 # At each step, from any ingredient, we can go to any of the
 # 9 ingredients not in the same bin. Since each other bin has
 # exactly 3 ingredients, the contribution to each other bin is uni
 S = [0] * 4
 S[start_bin] = 1
 dp_end = 1 if start == end else 0
 for step in range(1, k):
 total = sum(S)
 dp_end = total - S[end_bin]
 new_S = [0] * 4
 for b in range(4):
 new_S[b] = 3 * (total - S[b])
 S = new_S
 results.append(dp_end)
 with open(output_file, 'w') as f:
 f.write(' '.join(map(str, results)))
if =_name=_ == '=_main=_':
 solve()
How It Works
The algorithm uses dynamic programming grouped by bins:
1. Key observation: From any ingredient, the valid next ingredients are all ingredients NOT in
the same bin. Since there are 4 bins of 3 ingredients each, from any ingredient you can
transition to exactly 9 ingredients (3 per other bin).
2. State: S[b] tracks the total number of paths whose current last ingredient belongs to bin
b . This is sufficient because transitions depend only on bin membership.
3. Initialization: S[start_bin] = 1 (one path of length 1, consisting of just the start
ingredient).
4. Transition (for each additional step):
dp_end = total - S[end_bin] captures the number of paths that could end at the
specific end ingredient.
S_new[b] = 3 * (total - S[b]) — each of the 3 ingredients in bin b receives
total - S[b] paths from the previous step.
5. After k-1 transitions, dp_end gives the count of valid skewers of length k from start to
end .
Time complexity: O(k) per query.
Verification
The program was verified in two ways:
Official Sample
Input:
CHICKEN SHRIMP STEAK | PEPPER ONION MUSHROOM | PINEAPPLE TOMATO ZUCCHINI 
4
CHICKEN PEPPER 3
CHICKEN SHRIMP 2
CHICKEN SHRIMP 3
CHICKEN PINEAPPLE 4
Output: 6 0 9 63 — matches the expected output exactly.
Brute Force Verification
The DP solution was exhaustively compared against a brute-force backtracking solution for all
576 combinations of (start, end, k) with k in {1, 2, 3, 4}. All 576 test cases passed.
Usage
1. Create a file named input.txt with the bin layout on the first line, the number of queries
on the second line, and each query on subsequent lines.
2. Place solution.py in the same directory.
3. Run: python3 solution.py
4. Read the result from output.txt .