To solve this problem, we need to determine the number of ways to split a given string of digits into three non-empty parts such that the sum of the digits in each part is equal.
Approach
- Total Sum Check: First, calculate the total sum of the digits in the string. If this sum is not divisible by 3, it's impossible to split the string into three parts with equal sums, so the answer is 0.
- Target Sum: If the total sum is divisible by 3, the target sum for each part is the total sum divided by 3.
- Prefix Sum Collection: As we iterate through the string, we collect positions where the prefix sum equals the target sum (for the first part) and twice the target sum (for the first two parts combined).
- Count Valid Splits: For each valid position of the first part, count how many valid positions exist for the second part (using binary search for efficiency) to form three valid parts.
Solution Code
import bisect
def count_valid_splits(S):
total_sum = sum(int(c) for c in S)
if total_sum % 3 != 0:
return 0
n = len(S)
T = total_sum // 3
pos_T = []
pos_2T = []
current_sum = 0
for i in range(n):
current_sum += int(S[i])
length = i + 1 # length of the prefix up to current character
# Check if current sum is T and valid for first part (leaves room for two more parts)
if current_sum == T:
if length <= n - 2:
pos_T.append(length)
# Check if current sum is 2*T and valid for first two parts (leaves room for third part)
if current_sum == 2 * T:
if length <= n - 1:
pos_2T.append(length)
# Calculate the number of valid splits
result = 0
for pos in pos_T:
# Find the number of elements in pos_2T greater than pos
idx = bisect.bisect_right(pos_2T, pos)
result += len(pos_2T) - idx
return result
# Read input and output the result
S = input().strip()
print(count_valid_splits(S))
Explanation
- Total Sum Check: The total sum of digits must be divisible by 3 to split into three equal parts.
- Target Sum: Each part should sum to
total_sum // 3. - Prefix Sum Collection: We track positions where the prefix sum reaches the target sum (for the first part) and twice the target sum (for the first two parts). This helps in identifying valid split points.
- Binary Search: For each valid first split point, we use binary search to quickly find the number of valid second split points. This is efficient because the prefix sum list is non-decreasing.
This approach ensures we efficiently count valid splits with a time complexity of O(n log n) due to binary search, which is suitable for large input sizes. The space complexity is O(n) for storing the positions of valid splits.


作者声明:本文包含人工智能生成内容。