TST 2016
Table of contents
Đề bài
Đề bài ở đây không ghi đầy đủ các subtask bé.
Ngày 1
Bài 1
Tìm số dãy số độ dài $N$ thỏa mãn điều kiện:
- Bắt đầu và kết thúc là số $1$.
- Các số ở giữa là các số nguyên dương $\geq 2$.
- Số thứ $i$ chia hết cho tổng của số thứ $i+1$ và số thứ $i-1$ với mọi $2< i < N$.
Input: Số test $T \leq 100$ và $mod$ nguyên tố. Sau đó là $T$ số $N$ ($N \leq 10^6$).
Output: Từng đáp số.
Bài 2
Cho đồ thị vô hướng có trọng số $N$ đỉnh $M$ cạnh và $1$ tập hợp đỉnh $Y$. Gọi $D(u, v)$ là đường đi ngắn nhất từ $u$ đến $v$.
Cho $Q$ truy vấn, mỗi truy vấn là 1 cặp đỉnh $(u, v)$, tìm đường đi tốt nhất từ $u$ đến $v$. Đường đi tốt nhất từ $u$ đến $v$ là đường đi có giá trị ($\min(\min(D(x_i, y_i))$ với $y_i$ thuộc $Y$) với $x_i$ thuộc đường đi đã chọn) lớn nhất.
Giới hạn: $N, Q \leq 10^5$, $M \leq 2 \cdot 10^5$.
Bài 3
Có $N$ lớp đánh số từ $1$ đến $N$, lớp thứ $i$ có $B_i$ bạn nam và $G_i$ bạn nữ. Hãy chia các lớp thành các nhóm, mỗi nhóm gồm các lớp đánh số liên tiếp thỏa mãn:
- Mỗi nhóm có ít nhất $L$ và nhiều nhất $R$ lớp
- Với mỗi nhóm ta tính số nam và số nữ của cả nhóm. Nếu số nam ít hơn số nữ coi như nữ thắng thế và ngược lại. Nếu số nam và nữ bằng nhau thì không có ai thắng thế.
- Gọi $X$ là số nhóm có nam thắng thế, Y$$ là số nhóm có nữ thắng thế. Ta cần đối đa hóa $X - Y$.
In ra $X - Y$ lớn nhất có thể.
Giới hạn:
- $N \leq 10^5$.
- $B_i, G_i \leq 10^4$.
- Đảm bảo luôn tồn tại cách chia.
Bài 4
Cho $N$ quả bom trên mặt phẳng, mỗi quả bom đặt ở $(X_i, Y_i)$ và bán kính nổ $R_i$. Khi một quả bom nổ thì tất cả bom ở bán kính nổ của nó cũng nổ theo, tạo phản ứng dây chuyền.
Tìm số bom ít nhất phải kích nổ để làm nổ hết bom.
Giới hạn:
- $N \leq 3 \cdot 10^5$
- Tọa độ có trị tuyệt đối $\leq 10^6$
Ngày 2
Bài 5
Trên bàn cờ vô tận có $1$ con xe, $1$ ô đích và $N$ ô cấm. Mỗi nước con xe có thể di chuyển đến $1$ ô không cấm cùng hàng hoặc cùng cột bất kì mà không có ô cấm nào năm giữa đường đi. Tìm đường đi ngắn nhất đến ô đích.
Giới hạn:
- $N \leq 1000$.
- Tọa độ trị tuyệt đối $ \leq 10^9$.
Bài 6
Có một hộp độ dài $N$, lúc đầu ô $1$ và $2$ rỗng, các ô tiếp theo mỗi ô chứa $1$ kí tự $[A, B, C, D]$. Mỗi bước ta được phép chọn $2$ ô liên tiếp không rỗng và lấy $2$ kí tự ở đó chuyển vào $2$ ô rỗng (giữ nguyên thứ tự). Trạng thái đích là trạng thái mà $2$ ô đầu rỗng, các ô tiếp theo chứa các kí tự, trong đó những kí tự giống nhau phải đứng cạnh nhau. Tìm cách chuyển hộp về một trạng thái đích trong không quá N bước.
Giới hạn:
- Subtask $1$: $N \leq 10$.
- Subtask $2$: $N \leq 10^5$, $N - 2$ là bội của $4$ và hộp có dạng $xxABCDABCDABCDABCD…$
- Subtask $3$: $N \leq 10^5$, $N$ là số chẵn và hộp có dạng $xxABABABABABAB…$
Bài 7
Trên thư viện có $N$ giá sách ($A[1]$ đến $A[N]$), mỗi giá có $K$ quyển sách, quyển sách thứ $j$ trên giá thứ $i$ có tiêu đề là $A[i, j]$ (độ dài tất cả tiêu đề là $P$).
Ta định nghĩa $F(A, B)$ với $2$ giá sách $A$ và $B$ là $\min(length(LCP(A[1], B[1])), length(LCP(A[2], B[2])), …, length(LCP(A[k], B[k])))$.
Cho $M$ quyển sách mới và $Q$ truy vấn, mỗi truy vấn cho một giá $C$ chứa $K$ quyển sách trong $M$ quyển sách mới (có thứ tự) và một số $X$, đếm số giá sách $A[i]$ thỏa mãn $F(A[i], C) = X$.
Giới hạn:
- $N \leq 20000, M \leq 30000, Q \leq 20000$.
- $K \leq 15, P \leq 30, X \leq P$.
Bài 8
Cho $N$ đội bóng đá, mỗi đội có độ nổi tiếng $P[i]$. Có một số cặp đội có xích mích.
Hãy chọn một số đội bóng và xếp lịch đá bóng cho các đội trong $K$ ngày thỏa mãn các yêu cầu:
- Trong các đội được chọn không cặp đội nào có xích mích
- Tổng độ nổi tiếng các đội được chọn là lớn nhất
- Mỗi ngày mỗi đội phải được đá đúng 1 trận
- Trong K ngày không có cặp đội nào đá với nhau quá 1 trận
Giới hạn:
- Subtask $1$: $N \leq 20$
- Subtask $2$: $N \leq 50$
- Subtask $3$: $N \leq 500$ tuy nhiên không có quá $20$ đội có xích mích với trên $2$ đội khác.