TLEOJ Contest #16 - Truy vấn MEX

giaminh2211

Hôm nay giaminh2211 được học định nghĩa của MEX của tập hợp và cảm thấy rất hứng thú với định nghĩa này nên đã nghĩ ra 1 bài toán liên quan đến hàm MEX này.

Cho mảng n phần tử a_1, a_2, …, a_n.
Cho q truy vấn, mỗi truy vấn bạn được cho 1 số nguyên dương x.
Xét mảng b với b_i=a_i+i \times x với (1 \leq i \leq n).
Với mỗi truy vấn hãy in ra MEX của mảng b của truy vấn đó.

Định nghĩa của MEX
Định nghĩa MEX của tập S

MEX của một tập hợp S là số nguyên không âm nhỏ nhất không thuộc tập hợp S .

Giải thích cụ thể
  • MEX của S là số nguyên không âm nhỏ nhất mà không xuất hiện trong S .
  • Ví dụ:
  • Nếu S = \{0, 1, 2, 4, 5, -3\} , thì MEX của S 3 3 là số nguyên không âm nhỏ nhất không có trong S .
  • Nếu S = \{1, 2, 3, -1, -2, -3, 69, -96, 169, 196, -11092001\} , thì MEX của S 0 0 là số nguyên không âm nhỏ nhất không có trong S .

Input and Output

Input
  • Dòng đầu chứa hai số nguyên n, q (1 \leq n, q \leq 10^5)
  • Dòng thứ hai chứa n số nguyên a_i (-10^9 \leq a_i \leq 10^9)
  • q dòng sau dòng thứ i gồm 1 số nguyên dương là x (1 \leq x \leq n) của truy vấn thứ i
Output
  • Một dòng duy nhất chứa số nguyên là đáp án của bài toán
Subtask
  • Subtask 1 (50\% số điểm) : 1 \leq n, q \leq 1000.
  • Subtask 2 (50\% số điểm còn lại) : Không có giới hạn gì thêm.

Test 1

Input
5 2
-1 -1 -6 -2 4
1
2
Output
3
2
...More

TLEOJ Contest #16 - Trung bình hay trung vị

Cho dãy số nguyên dương an phần tử, tìm số dãy con b không rỗng của a thỏa mãn đồng thời hai điều kiện sau:

  • Dãy b có kích thước lẻ.
  • Trung bình cộng dãy b nhỏ hơn trung vị dãy b
Dãy con

Một dãy con của một dãy số a là một dãy số có thể thu được bằng cách xóa đi một số phần tử trong a mà không thay đổi thứ tự các phần tử còn lại. Nói cách khác, nếu a là dãy số a_1, a_2, ..., a_n , thì một dãy con độ dài k của a sẽ có dạng a_{i_1}, a_{i_2}, ..., a_{i_k} với 1 \leq i_1 < i_2 < ... < i_k \leq n .

Trung bình cộng là gì

Trung bình cộng của dãy b có kích thước m\frac{\sum^m_{i=1}b_i}{m}.

Trung vị là gì

Trung vị của dãy b tăng dần có kích thước m có giá trị bằng b_{\frac{m+1}{2}}, nếu b chưa được sắp xếp tăng dần, sắp xếp b theo giá trị tăng dần rồi mới tìm trung vị.

Yêu cầu: In ra số dãy con thỏa mãn điều kiện theo \text{mod} 998244353.

Input, Output và Subtasks

Input: (bàn phím)
  • Dòng đầu tiên chứa số nguyên dương n (1\le n\le 100).
  • Dòng thứ hai gồm n số nguyên dương a_i (a_i\le 500).
Output: (màn hình)
  • In ra số dãy con thỏa mãn điều kiện theo \text{mod} 998244353.
Subtasks

Gọi x=\text{max}(a_1,a_2,\dots,a_n)

  • Subtask 1 (20\%) n\le 10.
  • Subtask 2 (20\%) n\le 50,x\le 100.
  • Subtask 3 (20\%) x=2.
  • Subtask 4 (40\%) không có ràng buộc gì thêm.

Sample

Input (bàn phím)
5 
1 2 2 3 4
Output (màn hình)
2
Notes

Ta tìm được hai dãy con là:

  • \{1;3;4\} có trung bình cộng là \frac{1+3+4}{3}\approx 2.6, có trung vị là 3.
  • \{1;2;2\} có trung bình cộng là \frac{1+2+2}{3}\approx 1.6, có trung vị là 2.
...More

TLEOJ Contest #15 - Tree GCD

VilleClaude

Cho 1 cây có n đỉnh, các đinh được đánh số từ 1 đến n. Đỉnh thứ i có trọng số là w_i. Gọi d(x,y,z) là số cạnh ít nhất để liên thông 3 đỉnh x,y,z (1\le x<y<z\le n). Gọi g(x,y,z) là số lượng ước nguyên tố của gcd(w_x,w_y,w_z).
Yêu cầu: Hãy tính tổng tất cả các giá trị g(x,y,z) \times d(x,y,z) với mọi x,y,z thỏa mãn 1\le x<y<z\le n.

Input, Output và Subtasks

Input: (TREEGCD.INP)
  • Dòng đầu tiên gồm 1 số nguyên dương n (1\le n\le 2.10^5).
  • Dòng tiếp theo gồm n số nguyên dương w_1,w_2,...,w_n(1\le w_i\le 2.10^5).
  • Tiếp theo là n-1 dòng mô tả cây, mỗi dòng gồm 2 nguyên dương u,v(1\le u,v\le n,u\neq v) cho biết có cạnh nối giữa đỉnh u và đỉnh v. Đảm bảo dữ liệu vào luôn là cây.
Output: (TREEGCD.OUT)
  • Gồm 1 số nguyên là đáp án của bài toán. Kết quả có thể rất lớn nên hãy chia lấy dư cho 10^9+7.
Subtasks
  • Subtask 1: Đảm bảo n\le 200. (20% số điểm)
  • Subtask 2: Đảm bảo n\le 2.10^5,w_i\le 2. (30% số điểm)
  • Subtask 3: Không có ràng buộc gì thêm. (50% số điểm)

Sample

Input (TREEGCD.INP)
4
1 2 2 4
1 2
1 3
1 4
Output (TREEGCD.OUT)
3
...More

TLEOJ Contest #16 - Dãy con thú vị

Cho số nguyên dương L và dãy số nguyên a_1, a_2,..., a_{n-1}, a_n (a_i \leq L). Một dãy con khác rỗng của a được tạo ra bằng cách xóa đi một vài phần tử (có thể không xóa phần tử nào, nhưng phải giữ lại ít nhất một phần tử) và giữ nguyên thứ tự các phần tử còn lại. Độ thú vị của một dãy b_1, b_2,..., b_{m-1}, b_m được định nghĩa là:

\sum_{i = 1}^{i \le m} p[b[i]] + \sum_{i = 1}^{i \le m} q[b[i]][b[i+1]]

Tìm độ đẹp lớn nhất có thể của một dãy con không rỗng của a

Input and Output

Input
  • Dòng đầu gồm hai số nguyên n, L (n \leq 10^5, 1 \leq L \leq min(n, 50))
  • Dòng thứ hai chứa n số nguyên dương a_1, a_2,..., a_{n-1}, a_n
  • Dòng thứ ba gồm L số nguyên p_1, p_2,...,p_L (|p_i| \leq 10^4)
  • L dòng tiếp theo, dòng thứ i chứa L số nguyên q_{i1}, q_{i2},..., q_{iL} (|q_{ij}| \leq 10^4)
Output
  • Một dòng duy nhất chứa số nguyên là độ đẹp lớn nhất tìm được.
Scoring
  • Subtask 1 (40\%): n \leq 20
  • Subtask 2 (30\%): n \leq 3*10^3
  • Subtask 3 (30\%): Không có ràng buộc gì thêm

Test 1

Input
4 3
1 2 3 2
1 2 3
1 2 3
1 2 3
1 2 3
Output
15
Note
Dãy con cần tìm là {1, 2, 3, 4}. Độ đẹp là (1+2+3+2) + (2+3+2) = 8+7 = 15

Test 2

Input
7 4
3 2 3 4 1 4 3
1 -1 3 -1
1 0 10 4
-100 -10 1 7
-3 -2 4 -2
3 2 1 0
Output
24
Note
Dãy con cần tìm là {3, 3, 4, 1, 3}. Độ đẹp là (3+3-1+1+3)+(4-2+3+10) = 9+15 = 24
...More