bạn được cho trước một dãy số nguyên a1, a2, …, an. Đếm số cách chia dãy thành 3 đoạn mà…
- User
bạn được cho trước một dãy số nguyên a1, a2, …, an. Đếm số cách chia dãy thành 3 đoạn mà các phần tử trong mỗi đoạn là liên tiếp nhau, sao cho tổng các phần tử của mỗi đoạn là bằng nhau. Nói cách khác, đếm số cặp (i,j) (2 ≤ i ≤ j ≤ n) sao cho: ∑(k=1)^(i-1)▒〖a[k]〗=∑(k=i)^j▒〖a[k]〗=∑_(k=j+1)^n▒〖a[k]〗 INPUT: Dòng 1: chứa số nguyên dương n (1 ≤ n ≤ 5*105) Dòng 2: chứa n số nguyên a[1], a[2], …, a[n] (|a[i]| ≤ 109) OUTPUT: Một dòng duy nhất chứa giá trị là số cách phân chia dãy số bằng python
- Assistant
Bạn có thể sử dụng thuật toán Two Pointers để giải quyết bài toán này. Đầu tiên, ta tính tổng của dãy số a và lưu vào biến total_sum. Sau đó, ta khởi tạo hai biến left và right lần lượt là một và n (vị trí đầu và cuối của dãy). Tiếp theo, ta khởi tạo hai biến left_sum và right_sum ban đầu lần lượt là a[left] và a[right]. Tiếp theo, ta dùng một vòng lặp while để tìm các cặp (i, j) hợp lệ. Trong vòng lặp này, ta so sánh left_sum, right_sum, và total_sum / 3 để tìm các vị trí i và j thoả mãn điều kiện cần. Sau đó, ta tăng biến dem lên 1 và cập nhật left_sum và right_sum. Cuối cùng, ta in ra giá trị của biến dem.
Dưới đây là code Python để giải bài toán:
n = int(input()) a = list(map(int, input().split())) total_sum = sum(a) # Tính tổng của dãy a if total_sum % 3 != 0: # Nếu tổng không chia hết cho 3 thì không tồn tại phân chia hợp lệ print(0) else: partition_sum = total_sum // 3 # Tính tổng mà mỗi phần đoạn cần có left = 1 # Vị trí đầu của dãy right = n # Vị trí cuối của dãy left_sum = a[left-1] # Tính tổng của phần đoạn bên trái right_sum = a[right-1] # Tính tổng của phần đoạn bên phải count = 0 # Biến đếm số cách phân chia hợp lệ while left < right: if left_sum == partition_sum and right_sum == partition_sum: count += 1 left += 1 right -= 1 left_sum += a[left-1] right_sum += a[right-1] elif left_sum < partition_sum: left += 1 left_sum += a[left-1] else: right -= 1 right_sum += a[right-1] print(count)Độ phức tạp thời gian của thuật toán này là O(n), với n là số phần tử trong dãy số a.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.