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

Bài 4: Xe cứu thương (3 điểm)

Một thành phố có ~N~ điểm dân cư đánh số từ 1 đến ~N~, được kết nối bởi ~M~ con đường hai chiều.

Con đường thứ ~i~ nối từ điểm ~u_i~ đến điểm ~v_i~, có độ dài là ~w_i~ (đơn vị độ dài) và thời gian di chuyển là ~t_i~ (đơn vị thời gian)
~(1 ≤ u_i, v_i ≤ N; 1 ≤ w_i, t_i ≤ 100; i = 1, 2, 3, …, M)~.

Xe cứu thương (chạy điện) có thể di chuyển từ điểm dân cư này sang tất cả các điểm dân cư khác thông qua các con đường trên. Khi có yêu cầu, xe cứu thương ở vị trí hiện tại sẽ di chuyển tới điểm nhân và đưa tới bệnh viện phù hợp. Theo thông số kỹ thuật, pin của xe không cho phép di chuyển quá ~L~ (đơn vị độ dài).

Trung tâm điều phối nhận được thông tin và giao nhiệm vụ cho ~Q~ xe khác nhau.
Xe cứu thương thứ ~j~ đang ở vị trí ~X_j~ được giao nhiệm vụ tới điểm ~Y_j~ đón bệnh nhân rồi đưa tới bệnh viện ở điểm ~Z_j~
~(~Xj, Yj, Z_j ≤ N~; ~j = 1, 2, 3, …, Q~).

Yêu cầu

Với mỗi xe cứu thương, hãy xác định thời gian di chuyển ngắn nhất để xe đó có thể tới đón và đưa bệnh nhân tới bệnh viện mà không cần phải dừng lại để sạc pin.

Dữ liệu vào

Vào từ file RESCUE.INP:

• Dòng đầu tiên chứa 3 số nguyên dương ~N~, ~M~, ~L~
  ~(N ≤ 100; M ≤ 1000; L < 1024)~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ ~(i = 1, 2, 3, …, M)~ chứa 4 số nguyên
  ~u_i, v_i, w_i, t_i~ xác định con đường thứ ~i~.
• Dòng tiếp theo chứa số nguyên dương ~Q~.
• ~Q~ dòng cuối, dòng thứ ~j~ ~(j = 1, 2, 3, …, Q)~ chứa 3 số nguyên dương
  ~X_j, Y_j, Z_j~ xác định vị trí và nhiệm vụ của xe thứ ~j~.

Kết quả

Ghi ra file RESCUE.OUT gồm ~Q~ dòng.
Dòng thứ ~j~ là thời gian di chuyển ngắn nhất để xe thứ ~j~ đi đón và đưa bệnh nhân tới bệnh viện.

• Biết thời gian đưa bệnh nhân lên xe không đáng kể.
• Trường hợp xe bắt buộc phải dừng lại sạc pin thì in ra -1.

Ví dụ

RESCUE.INP

4 5 21
1 4 10 3
4 2 6 9
1 2 20 10
2 3 5 2
1 3 7 9
3
1 1 2
3 2 1
4 1 2

RESCUE.OUT

10
13
-1

Giải thích

• Xe thứ nhất đang ở điểm dân cư 1, đón bệnh nhân ở chính điểm đó rồi đi trực tiếp tới 2.
• Xe thứ hai đi theo lộ trình: ~3 → 2 → 3 → 1~.
  Không thể đi ~3 → 2 → 1~ do không đủ pin.
• Xe thứ ba không thể thực hiện được do không đủ pin.

Subtasks

• Subtask 1 (0.9 điểm):
  ~Q ≤ 100~, ~L = 1~, ~X_j = Y_j~, ~j = 1, 2, 3, …, Q~
• Subtask 2 (1.2 điểm):
  ~Q ≤ 100~, ~L = 2~
• Subtask 3 (0.6 điểm):
  ~Q ≤ 5~

• Subtask 4 (0.3 điểm):
  ~Q ≤ 10^4~

  Tài liệu tham khảo