TLEOJ Contest #16 - Truy vấn MEX
Xem PDF
Nộp bài
Điểm:
1900
Thời gian:
0.96s
Bộ nhớ:
128M
Input:
bàn phím
Output:
màn hình
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, pypy3, Python
Hôm nay đượ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 là 3 vì 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 là 0 vì 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
Bình luận