TST 2019
Table of contents
Đề bài
Đề bài ở đây không ghi đầy đủ các subtask bé.
Ngày 1
Bài 1
Có $n$ người và một rạp chiếu phim có $k \cdot n$ ghế ngồi.
Người thứ $i$ sẽ ngồi ở hàng ghế thứ $a_i$. Không có hai người ngồi cùng ghế.
Có $m$ mối quan hệ $(x, y)$ nghĩa là người $x$ là bạn 2 chiều của người $y$.
Định nghĩa độ thân thiện của rạp chiếu phim là tổng độ thân hiện của tất cả cặp người $(x, y)$. Cặp người $(x, y)$ có độ thân thiện bằng $1$ khi và chỉ khi:
- $x, y$ là bạn
- Nếu $x$ ngồi ở vị trí $(a, b)$ thì $y$ ngồi ở $(a+1, b)$ hoặc $(a-1, b)$ (nếu tồn tại).
Bạn cần tìm cách xếp sao cho độ thân thiện của rạp chiếu phim là lớn nhất có thể.
Giới hạn:
- $k \leq 17$
- $n \leq 10\,000$
- $m \leq 100\,000$
- $1 \leq a_i \leq K$
Bài 2
Cho $n$ chướng ngại vật $(x_i, y_i)$ trên mặt phẳng được giới hạn bởi hai đường thẳng $x = A$ và $x = B$.
Tìm bán kính $r$ của đường tròn lớn nhất có thể mà đi từ $y = -\infty$ đến $y = \infty$ mà không va phải chướng ngại vật nào, và vẫn đi trong khoảng giữa hai đường thẳng $x = A$ và $x = B$.
Giới hạn: $n \leq 100000$
Bài 3
Có $n$ công việc, mỗi công việc có hai giai đoạn. Công việc thứ $i$ mất $a_i$ thời gian để xong giai đoạn một, $b_i$ thời gian để xong giai đoạn hai. Mọi công việc cần phải xong giai đoạn một mới có thể sang giai đoạn hai. Mọi công việc cần phải xong cả hai giai đoạn mới tính là hoàn thành.
Cho $3$ số $w_1, w_2, w_3$. Giả sử các công việc được thực hiện theo trình tự $p_1, p_2, …, p_n$. Gọi $F_i$ là thời gian công việc thứ $i$ được hoàn thành.
Ta cần chọn một thời điểm $S$ sao cho $res = max(S_1, S_2, S_3)$ là nhỏ nhất, trong đó:
- $S_1 =$ giá trị lớn nhất có thể của |S - F_i| \cdot w_1$ với mọi i
- $S_2 =$ giá trị lớn nhất có thể của |S - F_i| \cdot w_2$ với mọi i
- $S_3 = S \cdot w_3$
Giới hạn: $n \leq 88888$.
Bài 4
Cho một xâu $T$ gồm các loại kí tự “(”, “{“, “[“, “)”, “}”, “]”, “?”.
Ta tạo ra xâu $S$ như sau:
- Ban đầu $S$ rỗng.
- Với mỗi kí tự của $T$, theo thứ tự từ trái sang phải: ta thêm nó vào cuối xâu $S$, và thêm kí tự $?$ vào cuối xâu $S$.
Có bao nhiêu các thay các dấu $?$ trong $S$ bằng các dấu ngoặc sao cho $S$ là một dãy ngoặc đúng (modulo $1\,000\,000\,007$)
Giới hạn: $|T| \leq 1000$.
Ngày 2
Bài 5
Xét một ma trận vuông $A$ kích cỡ $N \cdot N$. Ta gọi các ma trận đặc trưng của $A$ là các ma trận kích cỡ $(N - 1) \cdot (N - 1)$ tạo bằng cách xóa đi $1$ hàng và $1$ cột của $A$. Độ đa dạng của ma trận $A$ là số ma trận đặc trưng phân biệt của $A$.
Có $q$ ma trận vuông và với mỗi ma trận cần tính độ đa dạng của nó.
Giới hạn: $q \leq 10$, $N \leq 500$, các số trong ma trận là số tự nhiên $\leq 500$.
Bài 6
Cho một cây $n$ đỉnh có gốc ở đỉnh $1$, mỗi đỉnh có trọng số $v_i$, mỗi cạnh có trọng số $w_i$.
Gọi $d(u, v)$ là tổng trọng số các cạnh trên đường đi từ $u$ đến $v$.
Gọi $F(u) = d(u, v) \cdot v_v$ với mọi $v$.
Mục tiêu của bài là tìm $u$ sao cho $F(u)$ đạt giá trị nhỏ nhất có thể.
Đồng thời có các truy vấn có dạng:
- Tăng/giảm giá trị một đỉnh
- Tăng/giảm giá trị các đỉnh trong cùng cây con, với cùng một giá trị (đảm bảo không có $v_i$ nào âm sau mỗi truy vấn)
Sau mỗi truy vấn, cần in ra $F(u)$ nhỏ nhất.
Giới hạn:
- $n, q \leq 2\cdot10^5$
- $w_i, v_i$ là các số tự nhiên $\leq 10^7$.
Bài 7
Cho một hoán vị $p_1, p_2, …, p_n$ độ dài $n$.
Gọi độ đặc biệt của hoán vị là số thao tác swap hai phần tử liên tiếp ít nhất để đưa hoán vị cơ bản.
Hoán vị cơ bản được định nghĩa là một hoán vị vòng quanh của $1, 2, …, n$. Hoán vị cơ bản thứ $i$ là hoán vị có $p_1 = i$.
Có hoán vị $p$ và $q$ truy vấn:
Swap hai phần tử $a$, $b$ (không nhất thiêt liên tiếp) và in ra số thứ tự bé nhất của một hoán vị cơ bản mà $p$ (mới) có thể đến được sau ít lần swap nhất.
Giới hạn: $n, q \leq 10^5$
Bài 8
Đây là bài interactive.
Ta cần tìm xâu $S$ độ dài $n$ ($\leq 100$) với ba loại kí tự “a”, “b, “c”.
Có thể hỏi máy chấm câu hỏi sau:
Đua máy chấm một xâu $T$ không quá $100$ kí tự, máy sẽ trả về độ dài của xâu con chung dài nhất của $S$ và $T$
Giới hạn: Hỏi $500$ câu sẽ bị $0$ điểm.