TST 2018
Table of contents
Đề bài
Đề bài ở đây không ghi đầy đủ các subtask bé.
Ngày 1
TL: $0.5s$
ML: $512$ Mb
Bài 1
Cho mảng vòng tròn $N$ phần tử đánh số từ $1$ đến $N$. Bạn đứng tại ô $1$.
Mỗi bước bạn phải đi sang một trong hai ô kề với ô đang đứng.
Có bao nhiêu cách đi đúng $K$ bước mà sau $K$ bước bạn đứng ở ô $1$?
In ra kết quả $\mod 10^9+7$.
Giới hạn:
- Mỗi file có $1$ test.
- $N \leq 4000$
- $K \leq 10^6$
Bài 2
Cho cái cây $N$ đỉnh. Mỗi đỉnh được tô một trong 2 màu xanh, đỏ.
Thao tác flip đỉnh $u$ là đổi màu của đinh $u$ và các đỉnh kề với $u$ (xanh -> đỏ và đỏ -> xanh).
Liệu có thể biến cả cây thành màu xanh?
Cần truy vết.
Giới hạn:
- Mỗi file có $500$ test.
- $N \leq 3000$.
Bài 3
Cho một đường tròn trên mặt phẳng và $N$ đường thẳng có dạng $ax + by = c$.
Với mỗi đường thẳng, xét giao của nó với đường tròn (không giao thì không quan tâm).
Giả sử đường thẳng giao đường tròn tại $P_1$ và $P_2$ thì gọi cung ứng với đường thẳng là cung nhỏ hơn giữa hai cung $P_1 P_2$ và $P_2 P_1$.
(Đảm bảo không có đường thẳng đi qua tâm đường tròn và không có 2 đường thẳng nào cắt nhau trên đường tròn)
Bây giờ ta coi các cung vừa tạo là một đỉnh của đồ thị.
Hai đỉnh có cạnh khi và chỉ khi hai cung tương ứng có điểm chung.
Xét hai cạnh trên đồ thị.
Giữa hai cạnh $e$, $f$ có đường đi độ dài $d$ khi tồn tại dãy cạnh $e$, $w_1$, $w_2$, …, $w_d$, $f$ và các cạnh liên tiếp trong dãy có đỉnh chung.
Một tập cạnh con của đồ thị được gọi là đẹp nếu giữa hai cạnh bất kì trong tập, hoặc không có đường đi giữa chúng trên đồ thị ban đầu hoặc đường đi ngắn nhất giữa chúng trên đồ thị ban đầu $\geq 2$.
Ta quan tâm đến tập cạnh đẹp có nhiều cạnh nhất.
In ra số cạnh nhiều nhất có thể.
Giới hạn:
- Mỗi file có $10$ test.
- Các số trong bài đều nguyên và có trị tuyệt đối $\leq 10^9$
- Các sub:
- $N \leq 10$.
- $N \leq 50$.
- $N \leq 500$.
- $N \leq 50000$.
Bài 4
Ban đầu bạn có một mảng.
Có hai truy vấn:
Loại 1: Thêm phần tử vào mảng đã cho.
Loại 2: Xét mảng đã cho sau khi sort bé -> lớn, ta cần in ra tổng của K phần tử chỉ định. Các phần tử này được tạo như sau:
Cho $4$ số K, F, A, B, ta cần tính sum của các phần tử có $id$ sau:
$id_1$ = F $mod$ (size của mảng hiện tại)
$id_i$ = ($id_{i-1} \times A + B$) $mod$ (size của mảng hiện tại)
Giới hạn:
- Mỗi file có $5$ test.
- $N \leq 10^5$
- $Q \leq 20000$
- $K \leq 10^4$
- $F,A,B \leq 10^3$
Ngày 2
Bài 5
TL: $0.2s$
Bạn có một code chặt nhị phân để tìm một số trên mảng đã sort như nhau:
int binary_search(vector <int> &a, int key){
int l = 0, r = a.size() - 1;
while (l <= r){
int mid = (l + r + 1) / 2;
if (a[mid] == key)
return mid;
if (a[mid] < key)
l = mid + 1;
else
r = mid - 1;
string s = "asdsad";
}
return -1;
}
Bạn nhận ra hàm trên có thể đúng với cả mảng không sort.
Cho $N$ và key. Đếm số hoán vị từ $1$ đến $N$ mà hàm đã cho chỉ ra đúng vị trí của key.
Giới hạn:
$N \leq 10^5$
Bài 6
TL: $0.5s$
Ban đầu bạn có một tập rỗng.
Có hai truy vấn:
- Thêm một điểm trên mặt phẳng 2D vào tập. Đảm bảo điểm này có hoành độ lớn hơn tất cả các điểm trong tập hiện tại.
- Xóa đi k điểm có hoành độ lớn nhất.
Sau mỗi truy vấn, bạn phải in ra diện tích của bao lồi của tập điểm.
Xử lý online (dùng kết quả của truy vấn trước để xác định yêu cầu của truy vấn sau).
Giới hạn:
Số truy vấn $\leq 10^5$.
Bài 7
TL: $1.0s$
Bạn có một lưới tổ ong $N$ lớp được đánh số xoay vòng. Sau đây là hình minh họa lưới $2$ lớp:
Có thể thấy, hình có $N$ lớp (không tính ô ở giữa) thì có $3 \cdot N \cdot (N+1) + 1$ ô.
Bạn có $M$ vật trên lưới và cần di chuyển đến $M$ địa điểm được chỉ định (vật nào đứng ô nào cũng được).
Một bước di chuyển là chuyển một vật sang các ô kề cạnh mà không có vật nào khác.
Tính số bước di chuyển tối thiểu.
Giới hạn:
- Mỗi file có $5$ test.
- $N \leq 50$.
Bài 8
TL: $1.0s$
Đây là bài interactive.
Bạn và bạn bạn chơi một trò chơi.
Họ có một đa giác lồi $N$ đỉnh và một vài đường chéo bên trong nó.
Đảm bảo các đường chéo không cắt nhau và không tạo được các tam giác từ các đường chéo và cạnh của đa giác.
Đến lượt ai, người đó phải vẽ thêm một đường chéo của đa giác mà đa giác vẫn thỏa mãn tính chất trên.
Ai không vẽ được nữa thì thua.
Bạn được quyền chọn đi trước hoặc sau. Hãy chơi sao cho bạn thắng.
Giới hạn:
- $N \leq 10^5$.