Bài tập  /  Bài đang cần trả lời

Cho dãy số nguyên. Hãy chia dãy này thành nhiều đoạn sao cho tổng các phần tử trong các đoạn bằng nhau.

viết code C++ hay Python đều được
----- Nội dung ảnh -----
Cho dãy số nguyên. Hãy chia dãy này thành nhiều đoạn sao cho tổng các phần tử trong các đoạn bằng nhau.

Dữ liệu:
- Dòng đầu ghi n (n ≤ 100):
- Các dòng tiếp theo ghi a1, a2, ..., an (|ai| ≤ 10^9).

Kết quả:
- Dòng đầu tiên ghi K là số đoạn cần chia:
- Dòng thứ hai ghi K số nguyên là chỉ số cuối cùng của các đoạn theo thứ tự từ trái sang phải. Nếu có nhiều phương án thì in một phương án bất kỳ.

Ví dụ:
Dữ liệu:
6
5 2 3 2 2 1

Kết quả:
3
1 3 6
1 Xem trả lời
Hỏi chi tiết
44
Tham khảo câu trả lời từ Trợ lý ảo Lazi
Bài toán yêu cầu chia dãy số nguyên thành nhiều đoạn sao cho tổng các phần tử trong các đoạn bằng nhau. Để giải quyết bài toán này, ta có thể làm theo các bước sau:

1. **Tính tổng toàn bộ dãy số:** Đầu tiên, chúng ta cần tính tổng của tất cả các phần tử trong dãy.

2. **Tính số đoạn cần chia (K):** Xác định những giá trị mà tổng của các đoạn có thể chia đều. Nếu tổng không chia hết cho K (số đoạn), thì không thể chia dãy thành K đoạn có tổng bằng nhau.

3. **Chia dãy thành đoạn:** Thực hiện phép chia dãy thành các đoạn mà tổng của mỗi đoạn bằng tổng chia cho K.

4. **Kết quả:** Xuất ra số đoạn và các đoạn đã chia.

### Ví dụ minh họa:

**Dữ liệu:**
```
6
5 2 3 2 2 1
```
**Tổng dãy:** 5 + 2 + 3 + 2 + 2 + 1 = 15

Giả sử ta muốn chia thành 3 đoạn, mỗi đoạn sẽ có tổng là 15 / 3 = 5.

**Kết quả có thể là:**
```
3
5
2 3
2 2 1
```

### Cách thực hiện trong mã giả:

```python
def split_into_segments(arr):
total_sum = sum(arr)
n = len(arr)

for k in range(1, n + 1): # K từ 1 đến n
if total_sum % k == 0:
target_sum = total_sum // k
current_sum = 0
segment_count = 0
valid_segments = []

for number in arr:
current_sum += number
if current_sum == target_sum:
segment_count += 1
valid_segments.append(current_sum)
current_sum = 0

if segment_count == k:
return k, valid_segments

return 0, []

# Ví dụ gọi hàm
arr = [5, 2, 3, 2, 2, 1]
k, segments = split_into_segments(arr)
print(k)
for segment in segments:
print(segment)
```

Mã này sẽ kiểm tra từng giá trị K từ 1 đến n và tìm cách chia dãy thành các đoạn có tổng bằng nhau. Sau khi tìm thấy cách chia hợp lệ, bạn sẽ nhận được số đoạn và danh sách các đoạn.
1
1
Quang Cường
03/01 18:28:10
+5đ tặng
# Hàm chính để giải bài toán
def chia_day_so(day_so, n):
    t  # Tính tổng toàn bộ dãy
    if tong_day % n != 0:  # Kiểm tra nếu không thể chia đều
        return -1
    
    t // n  # Tổng mỗi đoạn phải có
    t />    cac_doan = []
    
    # Duyệt qua dãy số để tìm các điểm chia
    for i in range(len(day_so)):
        tong_hien_tai += day_so[i]
        if t tong_moi_doan:  # Khi tổng đoạn bằng phần cần chia
            cac_doan.append(i + 1)  # Lưu chỉ số cuối đoạn (1-indexed)
            t />    
    return len(cac_doan), cac_doan  # Trả về số đoạn và chỉ số cuối của các đoạn

# Nhập dữ liệu
n = int(input())  # Số phần tử trong dãy
day_so = list(map(int, input().split()))  # Dãy số

# Gọi hàm để tìm kết quả
K, cac_doan = chia_day_so(day_so, n)

# In kết quả
if K == -1:
    print("Không thể chia đều")
else:
    print(K)
    print(" ".join(map(str, cac_doan)))
 

Mở khóa để xem toàn bộ nội dung trả lời

(?)
Bạn đã đạt đến giới hạn của mình. Bằng cách Đăng ký tài khoản, bạn có thể xem toàn bộ nội dung trả lời
Cải thiện điểm số của bạn bằng cách đăng ký tài khoản Lazi.
Xem toàn bộ các câu trả lời, chat trực tiếp 1:1 với đội ngũ Gia sư Lazi bằng cách Đăng nhập tài khoản ngay bây giờ
Tôi đã có tài khoản? Đăng nhập

Bạn hỏi - Lazi trả lời

Bạn muốn biết điều gì?

GỬI CÂU HỎI
Học tập không giới hạn cùng học sinh cả nước và AI, sôi động, tích cực, trải nghiệm

Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi

Vui Buồn Bình thường
×
Trợ lý ảo Trợ lý ảo
×
Đấu trường tri thức | Lazi Quiz Challenge +500k
Gửi câu hỏi
×