Phân tích

Để giải bài toán này cần các bước sau:

1. Tính tổng số lượng kẹo đang có bằng cách cộng số lượng kẹo trong từng túi lại với nhau, ~total:= \sum_{i=1}^N C_i~.
2. Tìm số lượng kẹo còn lại sau khi chia đều tối đa cho ~M~ đứa trẻ. Ta có thể tính bằng cách chia tổng số kẹo cho số lượng đứa trẻ. Phép chia có thể không chia hết, vì vậy ~(total \div M)~ sẽ có phần nguyên (là lượng kẹo mỗi đứa trẻ được nhận) và phần dư (lượng kẹo còn lại). Do chúng ta chỉ quan tâm đến phần dư, ta có thể dùng toán tử ~\text{mod}~ (chia lấy dư) như sau:

Lời giải mẫu

Solve(N, M, C) {
  total = 0
  for i in 1:N {
    total = total + C[i]
  }
  remainder = modulo(total, M)
  return remainder
}

Giới hạn và độ phức tạp

Với giới hạn dữ liệu vào của bài toán này, kiểu dữ liệu số nguyên của đa số các ngôn ngữ lập trình sẽ đủ để thực hiện các phép tính mà không bị tràn. Cụ thể, giá trị tối đa có thể xảy ra là ~total = (N_{max} \times C_{imax}) = 10^8~, và có thể lưu trong một biến số nguyên 32-bit có dấu ~(int_{max} \approx 2.147 \times 10^9)~. Nếu giới hạn của đề bài lớn hơn, ta có thể tận dụng tính chất bắc cầu và tính đối xứng của phép chia lấy dư để tính kết quả như sau:

Solve(N, M, C) {
  remainder = 0
  for i in 1:N {
    remainder = remainder + modulo(C[i], M)
    remainder = modulo(remainder, M)
  }
  return remainder
}

Cách này giảm giá trị tối đa phải tính toán xuống còn ~2 \times (M_{max}-1)~ với chỉ một chút tính toán thêm. Khi giải các bài toán khác, bạn sẽ gặp những kiểu giới hạn mà cần đến cách tối ưu hóa này.

Độ phức tạp tính toán cũng là một yếu tố quan trọng để cân nhắc khi lựa chọn hướng tiếp cận một bài toán. Hai cách làm được mô tả phía trên có cùng độ phức tạp ~O(N)~, đủ để giải quyết bài toán trong giới hạn thời gian cho phép. Những bài toán khác có thể được giải bằng nhiều cách khác nhau, nhưng sẽ chỉ có một số cách là đủ nhanh để giải quyết được toàn bộ test trong thời gian cho phép. Một thuật toán với độ phức tạp ~O(G^3)~ có thể chạy được một bộ test nhỏ với ~G_{max}=20~, nhưng thuật toán đó sẽ chạy rất chậm trong một bộ test lớn với ~G_{max}=10^6~.

Tóm lại, giới hạn thời gian và bộ nhớ cho các bài toán, và giới hạn kích thước dữ liệu cho từng subtask, đã được chọn sao cho các thuật toán giải được hoặc không giải được dựa vào độ phức tạp thời gian và bộ nhớ. Nói cách khác, nếu một bài toán có giới hạn thời gian là 60 giây, rất khó xảy ra việc một thuật toán nhanh chạy trong 40 giây, còn thuật chậm chạy trong 80 giây. Thay vào đó, bạn sẽ thấy một thuật nhanh sẽ chạy trong 5 giây, còn thuật chậm sẽ chạy trong 5 năm. Vì vậy nếu bạn thấy lời giải của bạn vượt quá giới hạn thời gian của một bài toán nào đó, hãy dành thời gian để đánh giá lại thuật toán của bạn. Có thể sẽ có cách tiếp cận khác chạy nhanh hơn rất nhiều.

Tải bộ test

Bạn hãy cố gắng tập sửa lỗi mà không nhìn vào dữ liệu test! Link tải.