Bài toán: Cấp số cộng

Mô tả:

Để chuẩn bị cho kỳ thi tuyển sinh 10 năm học 2022-2023, Bình và các bạn đang cố gắng ôn tập các môn Toán, Văn, Tiếng Anh. Buổi đầu ôn môn Toán, Thầy của Bình đưa ra định nghĩa:

Cấp số cộng là một dãy số có quy luật, trong đó kể từ số hạng thứ 2, mỗi số hạng đều bằng tổng của số hạng đứng liền trước và công sai ~d~ không đổi.
Ví dụ: Dãy số ~1, 4, 7, 10, \dots~ là một cấp số cộng với công sai ~d = 3~.

Công thức:

Giả sử cấp số cộng khởi đầu là số hạng đầu ~a_1~ và có công sai ~d~, thì:

• Số hạng thứ ~n~ được tính bằng:
  ~a_n = a_1 + (n - 1) \times d~

• Tổng của ~n~ số hạng đầu tiên được tính bằng:
  ~S_n = \frac{n \times (2 \times a_1 + (n - 1) \times d)}{2}~

Yêu cầu:

• Tìm số hạng thứ ~n~ và tổng của ~n~ số hạng đầu của cấp số cộng.

Input:

• Dòng đầu chứa một số nguyên ~n~ ~(1 \leq n \leq 10^6)~.
• Dòng thứ hai chứa hai số nguyên ~a_1, a_2~ (~|a_1| \leq 10^3, |a_2| \leq 10^4~).

Output:

• Dòng thứ nhất: Số hạng thứ ~n~ của cấp số cộng.
• Dòng thứ hai: Tổng của ~n~ số hạng đầu của cấp số cộng.

Ví dụ:

Input:

5
5 8

Output:

17
55

Giải thích:

• Công sai ~d = 8 - 5 = 3~.
• ~a_5 = 5 + (5 - 1) \times 3 = 17~.
• ~S_5 = \frac{5 \times (2 \times 5 + (5 - 1) \times 3)}{2} = 55~.

Tên bài: Đọc sách cùng nhau

Mô tả bài toán

Có ~ n ~ cuốn sách, và cả hai người bạn Tý và Tèo muốn đọc hết tất cả. Mỗi cuốn sách ~ i ~ mất ~ t_i ~ phút để đọc. Cả hai người có thể đọc đồng thời nhưng không thể đọc cùng một cuốn sách tại cùng một thời điểm.

Hai người đều đọc từ đầu đến cuối cuốn sách mà họ chọn. Nhiệm vụ của bạn là tìm tổng thời gian tối thiểu để cả hai đều đọc hết tất cả sách.

Input Format:

• Dòng đầu tiên chứa số nguyên ~ n ~: số lượng sách.
• Dòng thứ hai chứa ~ n ~ số nguyên ~ t_1, t_2, \dots, t_n ~: thời gian cần thiết để đọc mỗi cuốn sách.

Output Format:

• In ra một số nguyên: tổng thời gian tối thiểu.

Ràng buộc

• ~ 1 \leq n \leq 2 \times 10^5 ~
• ~ 1 \leq t_i \leq 10^9 ~

Ví dụ

Input:

3
2 8 3

Output:

16

Giải thích:

• Phân chia công việc tối ưu:
  • Tý đọc quyển 1 và 3 hết: ~ [2] và [3] ~, tổng thời gian = ~ 2 + 3 = 5 ~.
  • Tèo đọc quyển 2: ~ [8] ~, tổng thời gian = ~ 8 ~.
  • Vì yêu cầu cả 2 phải đọc hết các sách nên tổng thời gian tối thiểu để hoàn thành là ~ 16 ~.

Bài toán: Những viên đá

Mary thích thu thập những viên đá. Mỗi ngày Mary nhặt được một số viên đá nhất định ~ A_i ~, và Mary ghi lại số lượng này trong nhật ký. Với một số ~ M ~ (tổng số viên đá mong muốn), bạn cần xác định số ngày tối thiểu Mary cần để thu thập đủ ~ M ~ viên đá.

Input Format:

• Dòng đầu tiên chứa hai số nguyên dương ~ N ~ và ~ Q ~ (~ N ~ là số ngày, ~ Q ~ là số lượng truy vấn).
• Dòng thứ hai chứa ~ N ~ số nguyên ~ A_1, A_2, \ldots, A_N ~, số viên đá nhặt được trong từng ngày.
• Dòng thứ ba chứa ~ Q ~ số nguyên ~ M_1, M_2, \ldots, M_Q ~, mỗi số ~ M_j ~ là số viên đá Mary cần thu thập trong một truy vấn.

Output Format:

• Ghi ra ~ Q ~ dòng, mỗi dòng là số ngày tối thiểu Mary cần để thu thập đủ ~ M_j ~ viên đá cho truy vấn tương ứng.

Ràng buộc:

• ~ 1 \leq N, Q \leq 5 \cdot 10^5 ~
• ~ 1 \leq A_i \leq 10^5 ~
• ~ 1 \leq M_j \leq 10^5 ~

Ví dụ:

Input

5 4
1 2 3 4 5
3 8 10 14

Output:

2
4
4
5