TLEoj Contest #08 - Vị trí max min - TLEOJ: TLE Online Judge

TLEoj Contest #08 - Vị trí max min

Điểm: 1400 (thành phần)

Thời gian: 0.6s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

nathan4690

Dạng bài

Định nghĩa một dãy hoán vị độ dài $n$ là một dãy số độ dài $n$ chứa tất cả các số nguyên dương bé hơn hoặc bằng $n$ theo một thứ tự bất kỳ. Ví dụ, $[2,3,1,5,4]$ là một dãy hoán vị, nhưng $[1,2,2]$ và $[1,3,4]$ không phải dãy hoán vị.

Bạn được cho một dãy hoán vị $a$ độ dài $n$ . Với mỗi $i$ từ $1,2,\ldots,n-1$ , theo thứ tự này, bạn thực hiện thao tác sau:

Khởi tạo một dãy $b$ gồm $n-1$ phần tử theo định nghĩa sau:
- Nếu $i$ lẻ: $b_j = max(a_j, a_{j+1})$ với mọi $j \in [1,n-1]$
- Nếu $i$ chẵn: $b_j = min(a_j, a_{j+1})$ với mọi $j \in [1,n-1]$
Đặt dãy $a$ thành dãy $b$

Dễ thấy, sau mỗi thao tác, độ dài dãy $a$ giảm đi đúng $1$ phần tử, và sau $n-1$ thao tác, dãy $a$ sẽ chỉ còn đúng một phần tử.

Yêu cầu: Hãy tìm phần tử cuối cùng còn lại trong dãy $a$ sau $n-1$ thao tác.

Input, Output và Scoring

Input (bàn phím)

Dòng đầu tiên chứa số nguyên dương $t$ là số lượng bộ test ( $1 \leq t \leq 100$ ). Mỗi bộ test có định dạng như sau:
Dòng đầu tiên chứa số nguyên dương $n$ là độ dài của dãy hoán vị ( $1 \leq n \leq 5000$ ).
Dòng thứ hai chứa $n$ số nguyên dương $a_1,a_2,\ldots,a_n$ là dãy hoán vị được cung cấp ( $1 \leq a_i \leq n$ ).

Output (màn hình)

In ra $t$ dòng, mỗi dòng chứa một số nguyên dương duy nhất là phần tử cuối cùng còn lại trong dãy $a$ tương ứng với từng bộ test.

Subtasks

Subtask 1 ( $20\%$ số điểm): $n \leq 500$
Subtask 2 ( $20\%$ số điểm): $a_i \leq a_{i+1}$ với mọi $i \in [1,n-1]$
Subtask 3 ( $60\%$ số điểm): Không có ràng buộc gì thêm

Sample

Input (bàn phím)

Output (màn hình)

3
3

Notes

Ở test đầu tiên, các thao tác được thực hiện như sau:

Thao tác $1$ : ta có $b_1 = max(a_1,a_2) = 3$ ; $b_2 = max(a_2,a_3) = 3$ . Dãy $a$ sau thao tác này trở thành $[3,3]$
Thao tác $2$ : ta có $b_1 = min(a_1,a_2) = 3$ . Dãy $a$ sau thao tác này trở thành $[3]$

Phần tử cuối cùng trong dãy $a$ là $3$ . Lưu ý rằng dãy $a$ không nhất thiết là một hoán vị sau mỗi thao tác.

Bình luận

Không có bình luận nào.