THT B Vòng Sơ loại Toàn quốc 2025 - Lần 3

Với hai số nguyên \(A\) và \(B\) (\(|A|, |B| \le 10^{100}\)), ta tính \(A + B\) và \(A - B\). Từ tổng và hiệu của hai số ta có thể tìm được \(A\) và \(B\).

Yêu cầu: Cho tổng và hiệu của hai số, tìm hai số đó.

Input

• Dòng 1: chứa số nguyên là giá trị của \(A + B\).
• Dòng 2: chứa số nguyên là giá trị của \(A - B\).

Output

• Dòng 1: ghi số nguyên \(A\).
• Dòng 2: ghi số nguyên \(B\).

Example

0
-200

-100
100

Scoring

• Subtask \(1\) (\(90\%\) số điểm): \(|A|, |B| \le 10^9\).
• Subtask \(2\) (\(10\%\) số điểm): Không có ràng buộc nào thêm (\(|A|, |B| \le 10^{100}\)).

Với một số nguyên \(n\), Alice quan tâm đến các ước nguyên dương của \(n^2\) thỏa mãn điều kiện: nhỏ hơn \(n\) và không phải là ước của \(n\).

Yêu cầu: Cho số nguyên dương \(m\), xét số \(n = m \cdot (m + 1) \cdot (m + 2)\), hãy giúp Alice đếm số ước nguyên dương của \(n^2\) thỏa mãn điều kiện: nhỏ hơn \(n\) và không phải là ước của \(n\).

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ dữ liệu;
• \(T\) dòng sau, mỗi dòng chứa một số nguyên dương \(m\).

Output

• Gồm \(T\) dòng, mỗi dòng là số ước của \(n^2\) thỏa mãn: nhỏ hơn \(n\) và không phải là ước của \(n\).

Example

2
1
2

1
3

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(m \le 10^3; T \le 10;\)
• Subtask \(2\) (\(25\%\) số điểm): \(m \le 10^6; T \le 10;\)
• Subtask \(3\) (\(25\%\) số điểm): \(m \le 10^6; T \le 10^3;\)
• Subtask \(4\) (\(25\%\) số điểm): \(m \le 10^6; T \le 10^5;\)

Có ba bình đựng nước được đánh chỉ số \(1, 2, 3\), mỗi bình có thể chứa được \(V\) lít nước. Ban đầu, bình \(1\) có \(v_1\) lít nước, bình \(2\) có \(v_2\) lít nước, bình \(3\) có \(v_3\) lít nước (\(v_1 + v_2 + v_3 < V\)). Người ta muốn lấy một bình nước dùng cho công việc khác, khi đó cần phải đổ nước từ các bình sang cho nhau để nhận được một bình rỗng. Mỗi lượt, được phép đổ từ bình \(i\) sang bình \(j\) (\(i \neq j, v_i \geq v_j\)) và lượng nước được đổ là \(v_j\).

Input

• Gồm một dòng chứa ba số nguyên \(v_1, v_2, v_3\).

Output

• Dòng đầu ghi số nguyên dương \(k\) là số bước thực hiện.
• Tiếp theo là \(k\) dòng, mỗi dòng chứa hai số \(i, j\) cho biết thực hiện đổ nước từ bình \(i\) sang bình \(j\).

Example

1 2 3

2
3 1
2 3

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(v_1, v_2, v_3 \leq 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(v_1, v_2, v_3 \leq 2000\).
• Subtask \(3\) (\(60\%\) số điểm): \(v_1, v_2, v_3 \leq 10^6\).

Cho đồ thị dạng cây gồm \(N\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\), đỉnh thứ \(i\) \((1 \leq i \leq N)\) có ghi giá trị nguyên dương \(A_i\). Có \(Q\) truy vấn, truy vấn thứ \(k\) \((1 \leq k \leq Q)\) được mô tả bằng ba số \(u_k, v_k, x_k\) và cần tính giá trị \(S_k = \prod gcd(A_t, x_k) \bmod (10^9 + 7)\), trong đó \(t\) là các đỉnh nằm trên đường đi đơn từ \(u_k\) đến \(v_k\) và phép toán \(\bmod\) là phép toán chia lấy dư.

Yêu cầu: Với mỗi truy vấn hãy tính giá trị \(S_k\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N, Q\) \((N, Q \leq 10^5)\)
• Dòng tiếp theo chứa \(N\) số nguyên dương \(A_1, A_2, A_3, ..., A_N\) \((A_i \leq 10^7)\)
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) mô tả một cạnh của cây
• Dòng thứ \(k\) \((1 \leq k \leq Q)\) trong \(Q\) dòng tiếp theo chứa ba số nguyên dương \(u_k, v_k, x_k\) \((1 \leq u_k, v_k \leq N; x_k \leq 10^7)\) mô tả truy vấn thứ \(k\)

Output

• Ghi ra \(Q\) dòng tương ứng là đáp án của \(Q\) truy vấn

Example

4 3
1 2 3 4
1 2
2 3
3 4
1 4 1
4 4 2
1 4 2

1
2
4

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N, Q \leq 1000\)
• Subtask \(2\) (\(30\%\) số điểm): \(x_k\) là \(2\) lũy thừa của một số nguyên không âm
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc nào thêm

Một lớp học có \(n\) học sinh, các học sinh được đánh số từ \(0\) đến \(n-1\). Thầy giáo chủ nhiệm muốn chọn ra một nhóm học sinh để tham gia một trò chơi. Việc chọn nhóm được đánh giá thông qua các tiêu chí như: học sinh thứ \(i\) có nên chọn hay không, hay có nên chọn hai học sinh \(i,j\) cùng với nhau hay không. Do đó, thầy giáo đã xây dựng một ma trận \(Q\) để đánh giá việc chọn một nhóm.

Cụ thể, ma trận \(Q = (q_{ij})\) là ma trận đối xứng kích thước \(n \times n\), các hàng được đánh số từ \(0\) đến \(n-1\), các cột được đánh số từ \(0\) đến \(n-1\). Một cách chọn tương ứng với một vector nhị phân \(x\) gồm \(n\) thành phần, \(x = (x_0, x_1, ..., x_{n-1})\) với ý nghĩa \(x_i = 1\) hoặc \(0\) tương ứng học sinh thứ \(i\) được chọn hoặc không chọn. Một cách chọn nhóm được gọi là tốt nếu hàm \(f(x)\) đạt giá trị càng lớn nhất càng tốt:

Yêu cầu: Hãy giúp thầy giáo chọn nhóm để hàm \(f(x)\) đạt giá trị càng lớn càng tốt.

Input

• Dòng đầu chứa hai số nguyên \(n\), \(m\), trong đó \(n\) là kích thước ma trận \(Q\), \(m\) là số phần tử của ma trận \(Q\) có giá trị khác \(0\) (\(n \leq 500\))
• \(m\) dòng sau, mỗi dòng chứa ba số nguyên \(i\), \(j\), \(q_{ij}\) (\(|q_{ij}| \leq 10^9\) với \(0 \leq i,j \leq n-1\))
• Dữ liệu đảm bảo \(f(x)\) tối ưu luôn dương.

Output

• Gồm một dòng chứa \(n\) số nguyên mô tả chọn nhóm.

Example

2 2
0 0 5
1 1 -5

1 0

Scoring

Gọi \(GV\) là giá trị hàm \(f(x)\) tối ưu, \(HS\) là giá trị hàm \(f(x)\) cho cách chọn nhóm của bạn, gọi \(S\) là điểm cho một test, khi đó điểm của bạn được tính như sau:

• Nếu \(GV \leq HS\) đạt \(S\) điểm
• Nếu \(0 < \frac{GV-HS}{GV} < 1\%\) đạt \((1-\frac{GV-HS}{GV}) \times \frac{3S}{4}\) điểm
• Nếu \(1\% < \frac{GV-HS}{GV} < 10\%\) đạt \((1-\frac{GV-HS}{GV}) \times \frac{S}{3}\) điểm
• Trường hợp còn lại đạt \(0\) điểm