# TST 2023

## Sơ lược
- TST 2023 môn Tin diễn ra với hai ngày thi, mỗi ngày thi có 3 bài, mỗi bài xét trên thang điểm 100.
- Cutoff dự APIO (top 15): **117.1 / 600**.

## Lưu ý
- Nếu các bạn thấy sai sót trên đề thì có thể comment để mình xem lại.
- Các bài chấm theo **batch**: Bạn chỉ có điểm của một subtask nếu đúng hết tất cả các test trong subtask đó.
- Thí sinh không được phép sử dụng điều hướng biên dịch `pragma`, `unroll-loops`, `avx2`, ...

--------------------------------------

## Bài 1:
Time limit: $2.5s$ (?)
Memory limit: $1024\ MB$ (?)

## Đề bài

**Đây là bài toán interactive (tương tác với máy chấm).**

Cho cây $N$ $(1 \le N \le 250000)$ đỉnh, vô hướng, có trọng số nguyên dương và hằng số $H$ $(1 \le H \le 2023)$. Xét các định nghĩa sau:

- $d_{min}(u, v)$: Cạnh có trọng số nhỏ nhất trên đường đi ngắn nhất từ $u$ đến $v$ $(u \neq v)$.
- $f(w, u, v) = max(d_{min}(w, u) \times H, d_{min}(w, v) \times H)\ (w \neq u, w \neq v)$.

Bạn cần trả lời $q$ truy vấn sau **online**:

- $u\ v\ C$: Cho biết độ dài của tập $S$ lớn nhất có thể có sao cho tập $S$ chứa các đỉnh **phân biệt** thỏa $\sum_{w \in S} f(w, u, v) \le C$ $(1 \le C \le 10^{18})$.

## Cài đặt

Bạn cần cài đặt hai hàm sau:

void init(vector <int> A, vector <int> B, vector <int> W, int H)

- Các vector $A, B, W$ có độ dài $N - 1$, tương ứng với $N - 1$ cạnh của cây, trong đó cạnh thứ $i$ $(0 \le i \le N - 2)$ nối $A_i$ và $B_i$ với trọng số $W_i$.
- Giá trị $H$ nguyên dương tương ứng với hằng số $H$ trên đề bài.
- Hàm được gọi duy nhất một lần tại đầu chương trình.

int query(int u, int v, long long C)

- Các tham số $u, v, C$ tương ứng với một truy vấn $u, v, C$. Hàm cần trả về đáp án cho truy vấn này.
- Hàm sẽ được gọi tối đa $Q$ $(1 \le Q \le 750000)$ lần. (Xem chi tiết tại phần subtask).

Lưu ý: Bạn được phép khai báo thêm hàm và biến bên ngoài, nhưng không được khai báo hàm tên là `main`.

## Subtask

- Subtask $1$ ($6$ điểm): $N \le 5000, Q \le 1000$.
- Subtask $2$ ($19$ điểm): $W_i \le 20$.
- Subtask $3$ ($22$ điểm): $u = v$ với mọi truy vấn.
- Subtask $4$ ($20$ điểm): Mọi đỉnh có bậc không quá $2$.
- Subtask $5$ ($18$ điểm): $Q \le 2 \times 10^5$.
- Subtask $6$ ($15$ điểm): Không có ràng buộc gì thêm.

-------------------------

## Bài 2:
Time limit: $2s$ (?)
Memory limit: $1024\ MB$ (?)

## Đề bài

Xét chuỗi hạt $S$ có $n$ $(1 \le n \le 10^9)$ hạt, mỗi hạt có thể có màu trắng hoặc màu đen. Ta có thể biểu diễn chuỗi hạt như một xâu nhị phân $S$ độ dài $n$, trong đó $0$ biểu diễn cho màu trắng và $1$ biểu diễn cho màu đen (Ta sẽ đánh số xâu từ $0$ đến $n - 1$).

Xét các định nghĩa sau:
- Hai chuỗi hạt $S$ và $T$ được gọi là **tương đồng** nếu tồn tại giá trị $j$ $(0 \le j \le n - 1)$ sao cho $S_i = T_{(i + j) \mod n}\ \forall i (0 \le i \le n - 1)$.
- Hai chuỗi hạt $S$ và $T$ được gọi là **đối xứng** nếu xâu $S$ và xâu **đảo ngược** của xâu $T$ là **tương đồng**.

Nhập vào $n$, $k$ $(1 \le k \le min(n, 20))$ và xâu nhị phân $P$ độ dài $k$. Cần tìm một tập $U$ gồm các chuỗi hạt độ dài $n$ thỏa:

- Mọi xâu biễu diễn của các chuỗi hạt đều có tiền tố độ dài $k$ là xâu $P$.
- Mọi cặp chuỗi hạt trong tập không **tương đồng** hay **đối xứng** nhau.
- Tập $U$ có nhiều chuỗi hạt nhất có thể.

Bạn cần cho biết độ dài lớn nhất của tập $U$ có thể tạo ra.

## Cài đặt

### Input
- Dòng đầu nhập vào hai số nguyên dương $n$, $k$ $(1 \le n \le 10^9, 1 \le k \le min(n, 20))$.
- Dòng thứ hai nhập vào xâu nhị phân $P$ độ dài $k$.

### Output
- In ra độ dài lớn nhất của tập $U$ có thể có. Vì đáp án có thể rất lớn, in ra đáp án $modulo\ 10^9+7$.

## Subtask

- Subtask $1$ ($11$ điểm): $n \le 22$
- Subtask $2$ ($13$ điểm): $k = 1, n \le 10^5$
- Subtask $3$ ($12$ điểm): $k = 2, n \le 10^5$, $n$ là số nguyên tố.
- Subtask $4$ (?): $n \le 10^5$
- Subtask $5$ (?): $n$ là số nguyên tố.
- Subtask $6$ (?): Không có ràng buộc gì thêm.
- **Note**: Các subtask 4 và 5 có thể sai.

----------------------------

## Bài 3:
Time limit: $2s$ (?)
Memory limit: $1024\ MB$ (?)

## Đề bài

**Đây là bài toán interactive (tương tác với máy chấm).**

Có $n$ bạn đang chơi trên một đơn đồ thị liên thông, vô hướng, có trọng số gồm $n$ đỉnh và $m$ cạnh. Trong số của các cạnh khác nhau đôi một.

Trên mỗi đỉnh của đồ thị sẽ có một người chơi đang cầm súng nước. Mỗi người chơi sẽ bắn súng một lần duy nhất vào người chơi gần mình nhất (coi trọng số như độ dài cạnh). Những bạn không bị bắn sẽ giành chiến thắng.

Bạn là một trong $n$ người chơi, tuy nhiên bạn chỉ biết $n$.

Bạn sẽ được hỏi một số lượng câu hỏi dạng:

- $S\ W$: Cho tập $S$ gồm một số các đỉnh phân biệt của đồ thị, hãy cho biết có tồn tại ít nhất một cạnh nối hai đỉnh thuộc $S$ có trọng số $\le W$ hay không.

Sau khi hỏi xong, bạn cần cho biết vị trí chơi của mình để đảm bảo việc giành chiến thắng hoặc thông báo rằng không tồn tại vị trí như vậy.

## Cài đặt

Bạn cần cài đặt hàm sau:

int play(int n)

- Tham số $n$ tương ứng với số người chơi cũng như là số đỉnh của đồ thị.
- Hàm cần trả về một số nguyên là chỉ số đỉnh đảm bảo giành chiến thắng hoặc $-1$ nếu không tồn tại.

Bạn được phép gọi hàm sau:

int ask(vector <int> S, int W)

- Hàm `ask(S, W)` sẽ trả về $1$ nếu tồn tại ít nhất một cạnh nối hai đỉnh thuộc $S$ có trọng số $\le W$, $0$ nếu ngược lại.

Lưu ý: Bạn được phép khai báo thêm hàm và biến bên ngoài, nhưng không được khai báo hàm tên là `main`.

## Subtask

Trong mọi subtask, trọng số các cạnh là một số nguyên dương $\le 3 \times 10^6$.

- Subtask $1$ ($10$ điểm): $n = 65$.
- Subtask $2$ ($20$ điểm): $n = 1000$, đồ thị là cây, mỗi đỉnh có bậc không quá $2$.
- Subtask $3$ ($30$ điểm): $n \le 1000$, đồ thị là cây.
- Subtask $4$ ($40$ điểm): $n = 2023$.

## Scoring

Gọi $d$ là số lần bạn hỏi trong một test, $D = max(d)$ với mọi test trong một subtask và $T$ là điểm của subtask đó, điểm của bạn sẽ được tính như sau:

| $D$ | Điểm |
|-------------------- |--------- |
| $D \le 41000$ | $T$ |
| $41000 < D \le 45000$ | $0.8 \times T$ |
| $45000 < D \le 50000$ | $0.5 \times T$ |
| $50000 < D \le 60000$ | $0.3 \times T$ |
| $D > 60000$ | $0$ |

----------------------------

## Bài 4:
Time limit: $3s$ (?)
Memory limit: $1024\ MB$ (?)

## Đề bài

Bạn đang cần sinh test cho bài toán sau:

Cho dãy A gồm n số nguyên dương. Gọi dãy A0 là dãy A trước khi thực hiện truy vấn.

Thực hiện q truy vấn sau thuộc 3 loại sau trên dãy A:
- GCD l r v x: A[i] = gcd(A[i], v^x) (l <= i <= r).
- LCM l r v x: A[i] = lcm(A[i], v^x) (l <= i <= r).
- CHK l r: Hãy cho biết với mọi i trong đoạn [l, r] thì A0[i] = A[i] hay không?

Tuy nhiên, với mỗi truy vấn $CHK$, bạn cũng muốn biết tồn tại bao nhiêu bộ giá trị có thể điền vào subarray $A[l .. r]$ sao cho thỏa điều kiện của truy vấn để có thể lựa chọn sinh test.

## Cài đặt

### Input
- Dòng đầu nhập hai số nguyên dương $n$, $q$ tương ứng với độ dài dãy $A$ và số truy vấn.
- $q$ dòng tiếp theo, mỗi dòng nhập vào một truy vấn như trên đề bài $(1 \le l \le r \le n, 1 \le v, x \le 10^7)$.

### Output
- Với mỗi truy vấn $CHK$, gọi $ans$ là số giá trị có thể điền vào subarray $A[l .. r]$ sao cho thỏa điều kiện của truy vấn, nếu $ans \le 9 \times 10^{18}$ thì in $ans$, ngược lại in $-1$.

## Subtask

- Subtask $1$ ($12$ điểm): $n, q \le 2000, v \le 20, x \le 2$.
- Subtask $2$ ($14$ điểm): Không có truy vấn $LCM$, $x \le 2$.
- Subtask $3$ ($16$ điểm): Không có truy vấn $LCM$.
- Subtask $4$ ($19$ điểm): $n, q \le 2000$.
- Subtask $5$ ($21$ điểm): $v \le 20$.
- Subtask $6$ ($18$ điểm): Không có ràng buộc gì thêm.

----------------------------

## Bài 5:

## Đề bài

**Đây là bài toán output-only.**

Xét một căn nhà có chiều ngang và chiều dài vô cực. Ta biểu diễn căn nhà trên hệ trục Descartes (Đề-các). Trong căn nhà có $n$ bức tường có được biểu diễn bằng đường thẳng có dạng $ax + by + c = 0$. Không tồn tại ba bức tường đồng quy tại một điểm. Các bức tường sẽ chia căn nhà thành một số phòng (kể cả các phòng không được bao hoàn toàn bởi các bức tường). Mỗi bức tường sẽ được lắp gương ở đúng một trong hai mặt của bức tường.

<insert hình vì thằng tóm đề không biết vẽ>

Xét hai đường thẳng giao nhau sẽ tạo ra bốn góc, trong đó có hai góc sẽ có một mặt tường và một mặt gương, ta lắp cửa thông nhau tại hai góc này (tức hai phòng chứa hai góc này sẽ có cửa thông nhau).

Sau đó bạn sẽ sơn các căn phòng, và thỏa các điều kiện sau:

- Mỗi phòng được sơn đúng một màu.
- Hai phòng có cửa thông nhau phải có cùng màu.
- Số màu là nhiều nhất có thể.

Bạn cần tìm cách lắp gương sao cho số màu có thể tô cho các phòng là nhiều nhất có thể.

## Cài đặt

### Input
- Bạn cần tải về10 file `input01.txt`, `input02.txt`, ..., `input10.txt`. Đây sẽ là 10 file input của bạn. Mỗi file sẽ có format:
- Dòng đầu nhập vào $n$ là số bức tường trong căn nhà.
- $n$ dòng tiếp theo, mỗi dòng nhập ba số $a, b, c$ là hệ số đường thẳng biểu diễn bức tường. $(|a|, |b|, |c| \le 10^9, a^2 + b^2 > 0, c \neq 0)$.

### Output
- Với mỗi file `inputxx.txt`, bạn sẽ nộp file output tương ứng, như sau:
- Dòng đầu in ra $c$ là số màu tô được trong phương án lắp gương của bạn.
- Dòng thứ hai in ra $n$ số nguyên dương, trong đó, số thứ $i$ sẽ in ra $0$ nếu bạn lắp gương ở mặt tường hướng về tâm $(0, 0)$, $1$ nếu ngược lại.
- Bạn có thể nộp file output cho từng test, hoặc nhiều test, hoặc nộp toàn bộ file output trong một file zip

## Subtask

| Ràng buộc | Điểm |
|-------------------- |--------- |
| Với mọi đường thẳng, $a \times b = 0$ | $10$ |
| $n = 20$ | $10$ |
| $n = 23$ | $10$ |
| $n = 26$ | $10$ |
| $n = 50$ | $10$ |
| $n = 100$ | $10$ |
| $n = 200$ | $10$ |
| $n = 300$ | $10$ |
| $n = 400$ | $10$ |
| $n = 500$ | $10$ |

## Scoring

Gọi $J$ là số màu của ban tổ chức tìm được, $P$ là số màu bạn tìm được, $T$ là số điểm của test, điểm của bạn trong test được tính như sau:
| Điều kiện | Điểm |
|----------------|--------- |
| $P \ge J$ | $T$ |
| $J > P \ge 0.9 \times J$ | $?$ (không nhớ) |
| $P < 0.9 \times J$ | $0$ |

----------------------------

## Bài 6:
Time limit: $2s$ (?)
Memory limit: $1024\ MB$ (?)

## Đề bài

**Đây là bài toán communication (Tương tác hai chiều).**

Quốc gia A được biểu diễn là một cây vô hướng với $n$ thành phố được nối bởi $n - 1$ đường đi. Chính phủ đang thiết kế hệ thống cơ sở dữ liệu để đánh dấu các vùng xanh để chuẩn bị cho các trường hợp có thiên tai, dịch bệnh xảy ra.

Ta sẽ gọi máy tính lưu toàn bộ cơ sở dữ liệu là **máy chủ**, các máy của người dân là **máy trạm**.

Khi thiên tai xảy ra, chính phủ sẽ đánh dấu các vùng xanh, bao gồm một số nguyên dương các thành phố liên thông với nhau (tức, hai thành phố trong vùng xanh luôn đi được tới nhau mà không cần đi ra khỏi vùng xanh).

Máy chủ và các máy trạm đều biết thông tin của cây, tuy nhiên chỉ có máy chủ mới biết thông tin của các vùng xanh và sẽ có một số thời điểm các vùng xanh được cập nhật.

Một quá trình tương tác giữa máy trạm và máy chủ diễn ra như sau:
1. Khi người dân cần biết thông tin về một số vùng xanh, họ sẽ liệt kê ra một danh sách gồm thành phố họ đang sống và một số thành phố có đường đi trực tiếp với thành phố đó, ta gọi danh sách này là $P$ (với $P_0$ là thành phố của họ). Họ cần biết trong $P$ có tồn tại thành phố thuộc vùng xanh hay không
2. Họ sẽ gửi một xâu nhị phân rồi gửi cho máy chủ, ta gọi là xâu $S$.
3. Máy chủ nhận xâu nhị phân $S$, gửi về máy trạm xâu nhị phân $T$.
4. Máy trạm nhận xâu nhị phân $T$ và cho biết một thành phố trong danh sách $P$ thuộc vùng xanh hoặc thông báo không có thành phố nào trong danh sách $P$ thuộc vùng xanh.

Hãy thiết kế máy chủ và máy trạm sao cho tổng lượng thông tin cần gửi là ít nhất (xem chi tiết ở phần **subtask** và **scoring**).

## Cài đặt

### Máy trạm
Với **máy trạm**, bạn cần cài đặt:

namespace client

Trong `client`, bạn cần cài đặt các hàm sau:

void init(vector <int> par)

- Mảng $par$ có độ dài cho $n - 1$, biểu diễn các cạnh trong đồ thị, trong đó, với mỗi $i$ thì có cạnh nối giữa $i + 1$ và $par_i$ trên cây $(0 \le i < n - 1)$.

string request(vector <int> P)

- Mảng $P$ sẽ là danh sách mà người dân muốn kiểm tra, trong đó, $P_0$ sẽ là thành phố người đó đang sống và có đường đi trực tiếp đến $P_i$ $(i > 0)$. Hàm trả về xâu nhị phân $S$, xâu này sẽ được gửi cho máy chủ.

int answer(string T)

- Xâu $T$ là xâu được gửi về từ máy chủ sau khi thực hiện lệnh `request`. Bạn cần trả về một thành phố trong danh sách $P$ thuộc vùng xanh hoặc trả về $-1$ nếu không tồn tại.

### Máy chủ

Với **máy chủ**, bạn cần cài đặt:

namespace server

Trong `server`, bạn cần cài đặt các hàm sau:

void init(vector <int> par)

- Mảng $par$ có độ dài cho $n - 1$, biểu diễn các cạnh trong đồ thị, trong đó, với mỗi $i$ thì có cạnh nối giữa $i + 1$ và $par_i$ trên cây $(0 \le i < n - 1)$.

void update(vector <int> green)

- Mảng green chứa thông tin các thành phố thuộc vùng xanh.
- Lưu ý: Sau truy vấn này, chỉ có các thành phố này thuộc vùng xanh, các thành phố không trong danh sách này sẽ nằm ngoài vùng xanh.

void query(string S)

- Xâu nhị phân $S$ được gửi từ máy trạm, hàm cần trả về một xâu nhị phân $T$.

### Lưu ý
- Được phép khai báo thêm biến và hàm toàn cục trong hai namespace hoặc ngoài hai namespace, nhưng không được đặt tên hàm là `main`.
- Các hàm trong cùng một namespace sẽ dùng chung dữ liệu, các biến toàn cục nằm ngoài hai namespace sẽ bị reset khi truyền thông tin giữa hai hàm.

## Subtask

Trong mọi subtask: $5 \le n \le 65536$.
Trong mỗi test, hàm `update` và `request` sẽ được gọi tối đa $1000$ lần.

- Subtask $1$ ($10$ điểm): $|P| = 2$ với mọi lần `request`.
- Subtask $2$ ($20$ điểm): $|P| = 3$ với mọi lần `request`.
- Subtask $3$ ($30$ điểm): $|P| = 4$ với mọi lần `request` và đảm bảo luôn tồn tại ít nhất một thành phố thuộc vùng xanh trong $P$.
- Subtask $4$ ($40$ điểm): $|P| \le 5$ với mọi lần `request`.

## Scoring
- Gọi $d = |S| + |T|$ trong mỗi lần `request` và `query`.
- $D = max(d)$ trong mọi lần `request` và `query`.
- $D_{max} = max(D)$ trong mọi test của một subtask và $T$ là điểm của subtask đó, điểm của bạn cho subtask đó được tính như sau:

| $D_{max}$ | Điểm |
|----------------|--------- |
| $\le 17$ | $T$ |
| $18$ | $0.85 * T$ |
| $19$ | $0.75 * T$ |
| $20$ | $?$ (không nhớ) |
| $21$ | $?$ (không nhớ) |
| $22$ | $?$ (không nhớ) |
| $23$ | $?$ (không nhớ) |
| $24$ | $0.5 * T$ |
| $25$ | $?$ (không nhớ) |
| $26$ | $?$ (không nhớ) |
| $27$ | $?$ (không nhớ) |
| $28$ | $?$ (không nhớ) |
| $29$ | $?$ (không nhớ) |
| $30$ | $?$ (không nhớ) |
| $31$ | $?$ (không nhớ) |
| $32$ | $0.26 * T$ |
| $33, 34$ | $0.25 * T$ |
| $\ge 35$ | $0$ |

## Lời giải
**Tác giả**: Trần Xuân Bách
**Link**: https://hackmd.io/@thenymphsofdelphi/Hy54KDcGh

----------------------------