Contest ôn tập THT bảng C1 - 2023 #04

Cho một bảng vô hạn, các hàng được đánh số trên xuống dưới bắt đầu từ \(0\), các cột được đánh số từ trái sáng phải bắt đầu từ \(0\). Bảng được đánh dấu như sau:

• Ở hàng \(0\), không có ô nào được đánh dấu.
• Ở hàng \(1\), ô đầu tiên không được đánh dấu, ô tiếp theo được đánh dấu, ô tiếp theo nữa không được đánh dấu, ô tiếp theo nữa nữa được đánh dấu, và cứ như thế.
• Ở hàng \(2\), \(2\) ô đầu tiên không được đánh dấu, \(2\) ô tiếp theo được đánh dấu, và cứ tiếp tục luân phiên như vậy.
• Như vậy, ở hàng thứ \(i\) sẽ có \(i\) ô đầu tiên không được đánh dấu, \(i\) ô tiếp theo được đánh dấu, và cứ tiếp tục luân phiên như vậy.

Yêu cầu: Đếm số lượng ô được đánh dấu ở cột thứ \(k\), có thể chứng minh được rằng số lượng ô được đánh dấu ở một cột nào đó là hữu hạn.

Input

• Dòng đầu tiên chứa một số nguyên \(t\) \((1 \leq t \leq 1000)\) \(-\) số lượng test case.
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(k\) \((0 \leq k \leq 10^9)\) \(-\) chỉ số của cột cần đếm số ô được đánh dấu.

Output

• In ra \(t\) dòng, mỗi dòng in ra một số nguyên là số lượng ô được đánh dấu ứng với testcase đó.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(t \leq 100, \ k \leq 1000\).
• Subtask \(2\) (\(40\%\) số điểm): \(t \leq 100, \ k \leq 10^5\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

5
0
1
2
3
4

Output

0
1
1
3
2

Note

Hình dưới đây là một phần đầu của bảng vô hạn (ô màu đen là ô được đánh dấu):

Lớp 12 Tin có \(n\) học sinh, đánh số từ \(1\) tới \(n\). Bạn là giáo viên chủ nhiệm của lớp và muốn chọn ra một số học sinh trong số này để dự kỳ thi Tin học trẻ sắp tới. Các thí sinh trong cuộc thi được thi theo đội và không giới hạn số lượng người trong một đội (dĩ nhiên đội phải có ít nhất \(1\) người). Tuy nhiên, có một ràng buộc rằng các thí sinh trong một đội phải có điểm vòng sơ loại cấp trường không được chênh lệch quá nhiều. Cụ thể hơn, điểm giữa hai cặp thí sinh bất kỳ trong cùng một đội phải có chênh lệch điểm không vượt quá \(l\). Ngoài ra, một lớp chỉ được có tối đa \(m\) đội tham gia thi đấu. Sau vòng sơ loại cấp trường, bạn đã biết điểm thi của học sinh thứ \(i\) là \(a_i\). Hãy tìm cách chọn ra nhiều học sinh nhất trong \(n\) học sinh để đăng ký tham gia kỳ thi nhé.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(l\) (\(1 \leq n \leq 10^5,1 \leq m \leq 100, 0 \leq l \leq 10^9\)) lần lượt là số học sinh trong lớp, giới hạn số đội thi của một lớp và chênh lệch điểm thi tối đa giữa hai học sinh bất kỳ trong một đội.
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_i\) (\(1 \leq a_i \leq 10^9\)), là điểm vòng sơ loại cấp trường của học sinh thứ \(i\).

Output

• Một số nguyên duy nhất là số lượng học sinh lớn nhất chọn được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, m \leq 10\).
• Subtask \(2\) (\(20\%\) số điểm): \(m = 1\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 100\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

7 2 2
1 7 2 4 8 4 4

6

Cho dãy \(a\) gồm \(n\) phần tử có giá trị trong khoảng \([1, m]\). Hãy tìm dãy con có thứ tự từ điển nhỏ nhất của dãy \(a\) mà là hoán vị độ dài \(m\).

Dãy con của một dãy \(a\) độ dài \(n\) có thể thu được bằng cách loại bỏ đi một số (có thể là không hoặc tất cả) phần tử và giữ nguyên thứ tự của các phần tử còn lại.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \leq m \leq n \leq 2 \cdot 10^6\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq m\)). Dữ liệu đảm bảo mọi số nguyên trong khoảng \([1, m]\) xuất hiện trong dãy ít nhất một lần.

Output

• Gọi \(b\) là dãy con tìm được. Hãy in ra giá trị của \(\displaystyle \sum_{i = 1}^{m} b_i \oplus i\). Trong đó \(\oplus\) là toán tử logic XOR.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 2 \cdot 10^2\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 2 \cdot 10^3\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 2 \cdot 10^5\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 3
2 3 1 3

6

Một mạng máy tính nội bộ của một tổ chức khủng bố gồm \(N\) thiết bị được đánh số từ \(1\) đến \(N\). Các thiết bị được kết nối bởi \(N-1\) dây cáp sao cho hai thiết bị bất kì đều được kết nối với nhau thông qua một số đoạn cáp. Cáp thứ \(i\) kết nối thiết bị \(u_i\) và \(v_i\).

Mỗi thiết bị \(j\) \((1 \le j \le N)\) có một thông số \(A_j\) \((A_j \neq 0)\):

• Nếu \(A_j < 0\), thiết bị là một máy tính có mức tiêu thụ điện là \(-A_j\).
• Nếu \(A_j > 0\), thiết bị là một nguồn điện có công suất \(A_j\).

Để triệt phá hệ thống mạng này, bạn cần ngắt kết nối một số đoạn cáp. Khi đó hệ thống mạng sẽ được chia thành các thành phần liên thông. Hệ thống sẽ bị vô hiệu hóa hoàn toàn nếu như tất cả các thành phần liên thông thỏa mãn một trong hai điều kiện sau:

• Thành phần liên thông không chứa máy tính: tất cả các thiết bị \(j\) trong thành phần đều có \(A_j > 0\).
• Thành phần liên thông không cung cấp đủ điện: tổng \(A_j\) của các thiết bị \(j\) trong thành phần nhỏ hơn \(0\).

Hãy xác định cần ngắt kết nối ít nhất bao nhiêu đoạn cáp để vô hiệu hóa hoàn toàn hệ thống.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \le N \le 3000)\) - số lượng thiết bị trong hệ thống;
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) \((1 \le |A_i| \le 10^9)\) - thông số của mỗi thiết bị;
• \(N-1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_i\) và \(v_i\) \((1 \le u_i, v_i \le N, u_i \neq v_i)\) - số thứ tự của hai thiết bị mà dây cáp thứ \(i\) kết nối.

Output

• In ra số lượng dây cáp ít nhất cần ngắt kết nối để vô hiệu hóa hệ thống.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 300, |A_i| = 1\).
• Subtask \(3\) (\(20\%\) số điểm): \(|A_i| = 1\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 300\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
1 2 3 4
1 2
1 3
1 4

0

6
10 -1 10 -1 10 -1
1 2
2 3
3 4
4 5
5 6

5

8
-2 3 6 -2 -2 -5 3 2
3 4
7 6
6 2
8 2
5 3
1 8
3 7

3