Câu 1: Chia dư k (6 điểm)

An là một cậu bé rất yêu thích học môn Tin học. Một hôm thầy giáo giảng phần các phép toán trên một số kiểu dữ liệu, An rất thích thú với phép toán chia lấy phần nguyên và phép toán chia lấy phần dư.

Hôm nay, thầy giáo cho An 3 số tự nhiên n, m, k (k < m ≤ n). Thầy yêu cầu An tính tổng giá trị các số tự nhiên trong phạm vi từ 1 đến n có số dư là k trong phép chia cho m.

An dễ dàng tính với các số nhỏ nhưng chưa thể giải được với trường hợp tổng quát. Hãy lập trình giúp An giải bài toán trên.

Dữ liệu vào

Vào từ file KTOTAL.INP một dòng duy nhất chứa 3 số tự nhiên n, m, k.

Kết quả

Đưa ra file KTOTAL.OUT một số nguyên duy nhất là tổng các số tìm được.

Ví dụ

Ví dụ 1

Giải thích:
Các số đó là: 2, 5, 8.

Ví dụ 2

Giải thích:
Các số đó là: 1, 2, 3.

Subtasks

• Subtask 1 (3.5 điểm):
  n ≤ 10⁵

• Subtask 2 (1.0 điểm):
  10⁵ ≤ m, n ≤ 2 × 10⁹

• Subtask 3 (1.0 điểm):
  n ≤ 2 × 10⁹

• Subtask 4 (0.5 điểm):
  n ≤ 5 × 10⁹

  Tài liệu tham khảo

Cho dãy số nguyên dương ~A_1, A_2, A_3, \ldots, A_n~. Hãy tìm hai số có giá trị khác nhau trong dãy sao cho tổng của chúng là số chẵn và chênh lệch giữa hai số đó là nhỏ nhất.

Dữ liệu vào

Vào từ file MIND.INP gồm 2 dòng:

• Dòng thứ nhất chứa số nguyên ~n~ ~(2 \le n \le 3 \times 10^5)~.
• Dòng thứ hai chứa (n) số nguyên dương
  ~A_1, A_2, A_3, \ldots, A_n (A_i \le 10^8,\ i = 1,2,\ldots,n)~.

Các số trên một dòng được ghi cách nhau bởi một dấu cách.

Kết quả

Ghi ra file MIND.OUT một số nguyên dương duy nhất là chênh lệch nhỏ nhất giữa hai số tìm được.
Ghi ra -1 trong trường hợp không tồn tại cặp số thỏa mãn.

Ví dụ

Ví dụ 1

Giải thích:

• VD1: Hai số tìm được là (1, 3) hoặc (7, 9), đều có chênh lệch là 2.
• VD2: Hai số tìm được là (10, 6) có chênh lệch là 4.

Subtasks

• Subtask 1 (3.6 điểm):
  ~n \le 1000~ và tất cả các số đều là số chẵn.

• Subtask 2 (1.2 điểm):
  ~n \le 1000~.

• Subtask 3 (1.2 điểm):
  ~n \le 3 \times 10^5~.

  Tài liệu tham khảo

Bạn Vinh rất thích số tự nhiên ~k~ và không thích chữ số ~c~. Tuần này, Vinh và Hưng được giao nhiệm vụ ra đề cho một cuộc thi Tin học trong câu lạc bộ. Do vậy, mọi thông tin trao đổi qua mạng về đề thi cần được bảo mật.

Hôm nay, sau khi soạn thảo xong, Vinh gửi cho Hưng một file văn bản được đặt mật khẩu cùng với một xâu ~S~ gồm ~n~ ký tự chữ số khác '0'. Vinh đã nói trước với Hưng rằng mật khẩu là số lớn nhất được biểu diễn bởi một trong các xâu con liên tiếp độ dài ~k~ của xâu ~S~ sao cho số đó không có chữ số ~c~.

Yêu cầu: Hãy giúp Hưng lập trình xác định mật khẩu được dấu trong xâu ~S~ mà Vinh gửi.

Dữ liệu vào

Vào từ file CKSUB.INP:

• Dòng đầu tiên chứa 3 số nguyên ~n~, ~k~, ~c~ ~(0 ≤ c ≤ 9)~.
• Dòng thứ 2 chứa xâu ~S~.

Kết quả

Ghi ra file CKSUB.OUT một số nguyên duy nhất là mật khẩu tìm được.
Dữ liệu đảm bảo trong xâu ~S~ luôn tồn tại mật khẩu.

Ví dụ

Ví dụ 1

Giải thích:
~k = 1~, ~c = 2~. Các số có thể được biểu diễn bởi xâu con liên tiếp độ dài 1 của ~S~ là: 8, 2, 7, 1, 9, 4.
Số lớn nhất không chứa chữ số 2 là 9.

Ví dụ 2

Giải thích:
~k = 3~, ~c = 2~. Các số có thể được biểu diễn bởi xâu con liên tiếp độ dài 3 của ~S~ là: 827, 271, 719, 194.
Số lớn nhất không chứa chữ số 2 là 719.

Subtasks

• Subtask 1 (0.8 điểm): ~n ≤ 10~; ~k = 1~; ~c = 0~
• Subtask 2 (2.0 điểm): ~k ≤ n ≤ 18~
• Subtask 3 (1.4 điểm): ~k ≤ n ≤ 1000~

• Subtask 4 (0.8 điểm): ~k ≤ n ≤ 3 × 10^5~

  Tài liệu tham khảo