Chọn ĐT HSG Đà Nẵng 2026 (Thi thử của NBK & LTT) Day 1

Sau khai giảng năm học mới, tập thể liên khối chuyên Tin năm học \(2026 - 2027\) tham gia các trò chơi tập thể ngoại khóa nhằm giúp các bạn trong liên khối gắn kết với nhau, hỗ trợ nhau trong học tập và rèn luyện. Mỗi lớp tổ chức một trò chơi chung cho cả liên khối. Bạn An đại diện lớp 11 Tin tổ chức trò chơi tìm mật mã như sau: Cho một số nguyên dương \(x\), mật mã của \(x\) chính là số lượng ước của \(x\). Ví dụ: \(x = 8\) có bốn ước \(1, 2, 4, 8\) nên mật mã của \(x\) là \(4\).

Trong quá trình tham gia trò chơi thấy bài toán bạn An đưa ra còn đơn giản quá nên bạn Sơn mở rộng bài toán như sau: Cho \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\). Gọi \(S = a_1 \times a_2 \times \dots \times a_n\) yêu cầu tìm mật mã của \(S\). Ví dụ: với dãy số \(\{2, 8, 4\}\), \(S = 64\) có bảy ước \(1, 2, 4, 8, 16, 32, 64\). Vậy mật mã của dãy là \(7\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(2 \le a_i \le 10^6\)) các số ghi cách nhau dấu cách.

Output

• Gồm một dòng ghi một số là mật mã tìm được, tương ứng với số lượng ước của dãy khi chia lấy phần dư cho \(10^9 + 7\).

Example

3
2 8 4

7

Ràng buộc

• \(30\%\) số tests tương ứng với \(30\%\) số điểm của bài có: \(S \le 10^{12}\);
• \(20\%\) số tests khác tương ứng với \(20\%\) số điểm của bài có: \(n \le 1000\) và \(a_i\) là số nguyên tố;
• \(50\%\) số tests còn lại tương ứng với \(50\%\) số điểm của bài không có ràng buộc gì thêm.

Bé Na có \(N\) (\(1 \le N \le 2000\)) người bạn. Tuy nhiên, không phải người bạn nào cũng giống nhau. Người bạn thứ \(i\) có độ nổi tiếng là \(P_i\) (\(1 \le P_i \le 2000\)), và bé Na muốn tối đa hóa tổng độ nổi tiếng của những người bạn đi cùng cô ấy. Người bạn thứ \(i\) chỉ đồng ý đi cùng Na nếu cô ấy đưa cho họ \(C_i\) (\(1 \le C_i \le 2000\)) đồng tiền. Họ cũng sẽ giảm giá cho cô ấy \(1\) đồng tiền nếu cô ấy đưa cho họ \(X_i\) (\(1 \le X_i \le 2000\)) cây kem ốc quế. Bé Na có thể nhận bao nhiêu lần giảm giá dạng số nguyên tùy thích từ một người bạn, miễn là các lần giảm giá đó không khiến người bạn phải đưa ngược lại tiền cho cô ấy.

Bé Na đang có sẵn \(A\) đồng tiền và \(B\) cây kem ốc quế (\(0 \le A, B \le 2000\)). Hãy giúp cô ấy xác định tổng độ nổi tiếng lớn nhất có thể đạt được nếu cô ấy chi tiêu tiền và kem ốc quế một cách tối ưu.

Input

• Dòng thứ nhất chứa ba số \(N\), \(A\) và \(B\), lần lượt biểu diễn số lượng bạn bè, số lượng đồng tiền và số lượng kem ốc quế mà bé Na có.
• Mỗi dòng trong \(N\) dòng tiếp theo chứa ba số \(P_i\), \(C_i\) và \(X_i\), lần lượt biểu diễn độ nổi tiếng (\(P_i\)), số đồng tiền cần để hối lộ người bạn thứ \(i\) đi cùng bé Na (\(C_i\)), và số kem ốc quế cần để nhận được mức giảm giá \(1\) đồng tiền từ người bạn thứ \(i\) (\(X_i\)).

Output

• In ra tổng độ nổi tiếng lớn nhất của những người bạn đi cùng bé Na, giả sử cô ấy chi tiêu tiền và kem ốc quế một cách tối ưu.

Example

3 10 8
5 5 4
6 7 3
10 6 3

15

Ràng buộc

• Có \(15\%\) số test thỏa mãn \(N \le 5\) và \(C_i = 1\).
• Có \(15\%\) số test thỏa mãn \(B = 0\).
• Có \(15\%\) số test thỏa mãn \(N, A, B, P_i, C_i, X_i \le 50\).
• Có \(25\%\) số test thỏa mãn \(N, A, B, P_i, C_i, X_i \le 200\).
• Có \(30\%\) test theo ràng buộc đề bài.

Một vương quốc cổ đại có hệ thống các hang động được nối với nhau bởi các con đường bí mật, tạo thành một cấu trúc dạng cây gồm \(n\) đỉnh, được đánh số từ \(1\) đến \(n\), trong đó đỉnh \(1\) là gốc. Mỗi hang động \(u\) chứa đúng một cổ vật quý giá, với khối lượng là \(w_u\) và giá trị là \(c_u\).

Một nhà thám hiểm thực hiện \(q\) chuyến đi. Trong chuyến đi thứ \(i\), người đó di chuyển từ hang động \(u_i\) đến hang động \(v_i\) theo con đường duy nhất nối hai đỉnh này trong cây. Trong quá trình di chuyển, người thám hiểm có thể lựa chọn một số cổ vật nằm trên đường đi để mang theo. Tuy nhiên, việc lựa chọn phải thỏa mãn các điều kiện sau:

• Số lượng cổ vật được chọn không vượt quá \(k_i\);
• Tổng khối lượng của các cổ vật được chọn không vượt quá \(W\);
• Tổng giá trị của các cổ vật được chọn là lớn nhất có thể.

Yêu cầu: Với mỗi chuyến đi, hãy xác định tổng giá trị lớn nhất mà người thám hiểm có thể thu được.

Input

• Dữ liệu vào từ tệp văn bản PATHBAG.INP gồm:
  • Dòng đầu tiên chứa ba số nguyên dương \(n, q, W\) (\(1 \le n, q \le 2\cdot 10^5\), \(W \le 30\));
  • Dòng thứ hai chứa \(n\) số nguyên dương \(w_1, w_2, \dots, w_n\) (\(1 \le w_i \le W\) với mọi \(1 \le i \le n\));
  • Dòng thứ ba chứa \(n\) số nguyên dương \(c_1, c_2, \dots, c_n\) (\(1 \le c_i \le 10^9\) với mọi \(1 \le i \le n\));
  • \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) cho biết có một đường đi trực tiếp giữa hai hang động \(u\) và \(v\);
  • \(q\) dòng cuối, dòng thứ \(i\) chứa ba số nguyên dương \(u_i, v_i, k_i\) cho biết nhà thám hiểm trong chuyến đi thứ \(i\) xuất phát từ hang động \(u_i\), kết thúc tại hang động \(v_i\), có thể mang theo không quá \(k_i\) cổ vật (\(1 \le u_i, v_i \le n\); \(1 \le k_i \le 8\)) với mọi \(1 \le i \le n\).

Output

• Ghi ra tệp văn bản PATHBAG.OUT gồm \(q\) dòng, dòng thứ \(i\) ghi một số nguyên là kết quả của chuyến đi thứ \(i\).

Constraints

• Có \(10\%\) số test ứng với \(10\%\) số điểm của bài thỏa mãn \(n, q \le 200\);
• Có \(15\%\) số test ứng với \(15\%\) số điểm của bài thỏa mãn cây là đường thẳng và \(n, q \le 5000\);
• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài thỏa mãn mọi truy vấn đều có \(u = 1\) và \(n, q \le 2\cdot 10^4\);
• Có \(25\%\) số test ứng với \(25\%\) số điểm của bài thỏa mãn \(n, q \le 2\cdot 10^4\), \(W \le 20\), \(k \le 5\);
• Có \(30\%\) số test còn lại ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm.