TST 2021
Table of contents
Đề bài
Ngày 1
Bài 1
Cho $n$ ống từ $1$ đến $n$, độ cao là $m + 1$. Ở độ cao thứ $i$ ($1 \leq i \leq m$), có 1 ống ngang nối giữa ống $a_i$ và $a_i + 1$. Viên bi bắt đầu từ ống $x$ sẽ rơi xuống, khi nào gặp ống ngang thì sẽ lăn sang ống dọc còn lại. Cho $q$ truy vấn:
- $1 \ i \ d$: Thay $a_i$ thành $d$.
- $2 \ l \ r$: Thả mỗi viên bi ở các ống từ $l$ đến $r$. Tính tổng bình phương vị trí cuối cùng mà các viên bi rơi xuống.
Giới hạn:
- Subtask $1$ (10): $n, m, q \leq 1000$.
- Subtask $2$ (17.5): $n, m, q \leq 2 \cdot 10^5, l = r$.
- Subtask $3$ (22.5): $n, m \leq 10^6, q \leq 2 \cdot 10^5$.
- Subtask $4$ (30): $n, m, q \leq 10^6, l = r$.
- Subtask $5$ (20): $n, m, q \leq 10^6$.
Bài 2
Có $n$ người, mỗi người có nhà ở $(x_i, y_i)$ và đi chợ ở $(u_i, v_i)$ (tọa độ có giá trị tuyệt đối $\leq 10^9$).
Tìm $k$ điểm trên một đường ngang sao cho $\Sigma$ (tổng khoảng cách từ nhà, đến 1 điểm nào đó trong $k$ điểm, và tiếp đến chợ) nhỏ nhất, và in ra $\Sigma$ đó.
Giới hạn:
- $k \leq 15$.
- Subtask $1$ (16): $n \leq 200, y_i = v_i$.
- Subtask $2$ (16): $n \leq 2000, y_i = v_i$.
- Subtask $3$: $n \leq 200$.
- Subtask $4$: $n \leq 2000$.
- Subtask $5$: $n \leq 1e5$.
Bài 3
Cho dãy $2 \cdot n$ số, mỗi giá trị từ $1$ đến $n$ xuất hiện $2$ lần trong dãy.
Tìm xâu có $n$ chữ $A$ và $n$ chữ $B$, sao cho $2$ chữ cái tương ứng với mỗi giá trị khác nhau, và số cặp chữ liên tiếp khác nhau là nhỏ nhất. Gọi giá trị đó là $x$, bạn sẽ được điểm theo công thức sau:
- $x > 0.6n \implies 0$ điểm
- $0.5n < x \leq 0.6n \implies$ $1$ giá trị điểm nào đó $<1$
- $0.45n < x \leq 0.5n \implies$ … $<3$
- $0.4n < x \leq 0.45n \implies$ … $<8$
- $0.3n < x \leq 0.4n \implies$ … $<10$
- $x \leq 0.3n \implies 10$.
Giới hạn:
- Đảm bảo luôn có xâu thoả mãn $x \leq 0.3 n$.
- Có $10$ test, trong đó $5$ test có $n \leq 1000$.
Ngày 2
Bài 4
Có $q$ test.
Ta có $1$ đãy nhị phân $n$ số, trong đó có $k$ số $0$.
Cho $m$ điều kiện, điều kiện thứ $i$ là $a[u_i] (>, =, <) a[v_i]$.
Tìm số điều kiện $x$ nhỏ nhất sao cho ta xác định được duy nhất $1$ dãy nhị phân thoả mãn $x$ điều kiện đầu tiên đó, và có $k$ số $0$. Đảm bảo luôn tồn tại $1$ dãy thoả mãn tất cả điều kiện và có $k$ số $0$.
Giới hạn:
- $m \leq 4 \cdot 10^5, \sum m \leq 2 \cdot 10^6$.
- Subtask $1$ (30): $n \leq 2000$, $\sum n \leq 10000$.
- Subtask $2$ (32.5): $n \leq 20000$, $\sum n \leq 12 \cdot 10^4$.
- Subtask $3$ (37.5): $n \leq 3 \cdot 10^5$, $\sum n \leq 12 \cdot 10^4$.
Bài 5
Đây là bài interactive.
Cho $n$ quả cân, trong đó có $n - x$ quả cân nặng $1$ kg, và $x$ quả cân nặng $(m + 1) / m$ kg.
Ta được phép hỏi tối đa $400$ câu hỏi, mỗi câu hỏi ta đưa ra một mảng chỉ số $a$ (các chỉ số phân biệt), và ta được biết tổng trọng lượng của các quả cân đó, làm tròn xuống. Tìm $x$, hoặc in ra $-1$ nếu như không thể xác định $x$.
Giới hạn:
- Chỉ AC subtask nếu đúng mọi test trong subtask đó.
- Subtask $1$ (13): $n \leq 8$, $m \leq 10^9$.
- Subtask $2$ (17): $n \leq 300$, $m \leq 10^9$.
- Subtask $3$ (17): $n \leq 10000$, $m \leq 20$.
- Subtask $4$ (19): $n \leq 10000$, $m \leq 40$.
- Subtask $5$ (23): $n \leq 2000$, $m \leq 10^9$.
- Subtask $6$ (11): $n \leq 10000$, $m \leq 10^9$.
Bài 6
Có $q \ (\leq 5)$ test.
Cho dãy $a$ gồm $n$ số, dãy $b$ gồm $m$ số. Tìm cách biến dãy $a$ thành $b$ trong tối đa $k$ thao tác, chỉ dùng $2$ thao tác insert và delete. In ra $-1$ nếu không thể.
Giới hạn:
- Subtask $1$ (10): Nếu có cách thực hiện, thì có cách chỉ dùng tối đa $1$ lần
delete. - Subtask $2$ (20): $n, m \leq 50000$, $k \leq 1000$.
- Subtask $3$ (20): $n, m \leq 2 \cdot 10^5$, $k \leq 5000$.
- Subtask $4$ (30): $n, m \leq 2 \cdot 10^5$, $k \leq 10000$.
- Subtask $5$ (20): $n, m \leq 5 \cdot 10^5$, $k \leq 10000$.