TST 2015
Table of contents
Đề bài
Đề bài ở đây không ghi đầy đủ các subtask bé.
Ngày 1
Bài 1
Một cuộc thi đua xe có $N$ người tham dự. Đường đua có $N$ vị trí xuất phát. Tại vòng đua đầu tiên, người thứ $i$ xuất phát tại vị trí thứ $i$.
Cho trước một hoán vị $P$ của các số nguyên từ $1$ tới $N$. Vị trí xuất phát của các tay đua tại các vòng đua tiếp theo được xác định như sau: nếu vòng đua liền trước một người xuất phát tại vị trí thứ $P_i$, thì vòng đua này người đó xuất phát tại vị trí thứ $i$.
Một hoán vị $P$ được gọi là hoàn hảo với số tự nhiên $X$ nếu thoả mãn điều kiện sau:
- Trong $X$ vòng đua đầu tiên, với hai vòng đua bất kỳ, luôn tồn tại một tay đua có vị trí xuất phát tại hai vòng này khác nhau.
- Điều trên không đúng với $X+1$ vòng đua đầu tiên.
- Với mọi tay đua, không tồn tại hai vòng đua họ xuất phát cùng một vị trí.
Cho số $N$ và $X$, tìm ra một hoán vị $P$ hoàn hảo với $X$.
Giới hạn: $N \leq 1000, X \leq 1000000$.
Bài 2
Cho đơn đồ thị vô hướng $N$ đỉnh, $M$ cạnh. Mỗi cạnh có một trong hai màu: xanh hoặc đỏ.
Có $Q$ thao tác, mỗi thao tác cho trước một đỉnh của đồ thị, đổi màu tất cả các cạnh liên thuộc với đỉnh này (và có thể là in ra số cạnh màu xanh liên thuộc với đỉnh này sau truy vấn ?).
Giới hạn: $N,M,Q \leq 100000$.
Bài 3
Một dãy số nguyên dương $a_1, a_2, … ,a_k$ được gọi là dãy số đẹp nếu thoả mãn điều kiện sau:
- Các số không có các ước nguyên tố khác $2$ và $3$.
- Không số nào là ước của một số khác trong dãy.
Một số gọi là đẹp nếu tồn tại một dãy số đẹp có tổng các số bằng số đó.
Cho số nguyên dương $N$, cần tìm 3 số $a$, $b$ ,$c$ sao cho:
- $0 < a < b < c$
- $a + b + c = N$
- $a, b , c$ là số đẹp.
- Gọi $S(X)$ là tổng các chữ số của $X$. $S(a)+S(b)+S(c)$ cần nhỏ nhất có thể.
Chỉ ra $1$ bộ $a, b, c$ thoả mãn, và dãy đẹp tương ứng với các số này.
Giới hạn: $N \leq 10^{15}$.
Bài 4
Cho một bảng chữ nhật $M \cdot N$. Trên bảng có một số vùng trọng điểm, mỗi vùng trọng điểm là một hình chữ nhật con của bảng này. Các vùng trọng điểm có thể giao nhau.
Một con vi khuẩn ban đầu ở ô $(X_0, Y_0)$. Sau mỗi giây, con vi khuẩn sẽ mở rộng phần ảnh hưởng của nó ra các ô kề đỉnh hoặc kề cạnh.
Cho $Q$ truy vấn, mỗi truy vấn có một thời điểm $T$, tính diện tích vùng trọng điểm bị ảnh hưởng bởi vi khuẩn sau $T$ giây.
Giới hạn:
- $M,N,Q,T \leq 1000000$.
- Số vùng trọng điểm $K \leq 400$.
Ngày 2
Bài 5
Một giải đấu bóng đá giao hữu có $N$ đội tham gia. Đội thứ $i$ dự định đá $C_i$ trận đấu. Mỗi trận đấu được diễn ra giữa hai đội khác nhau, trong đó có mội đội nhà và một đội khách.
Cần xếp các trận đấu của giải sao cho số trận mỗi đội đá đúng như dự định, với mối đội chênh lệch giữa số lần làm khách và số lần làm chủ nhà không quá $1$ và hai đội bất kỳ đá với nhau không quá một trận.
Giới hạn: $N \leq 1000$.
Bài 6
Cho một đa giác không tự cắt trên mặt phẳng toạ độ. Có các truy vấn, với mỗi truy vấn cho hai số $a, b$, cần tính diện tích phần đa giác nằm giữa hai đường thẳng $y=a$ và $y=b$.
Giới hạn:
- Đa giác có không quá $5000$ đỉnh.
- Số truy vấn không quá $200000$.
Bài 7
Cho đơn đồ thị vô hướng. Cần tìm ra bộ 4 đỉnh $x, y, z, t$ của đồ thị sao cho trên đồ thị có các cạnh $(x, y), (y, z), (z, t)$ nhưng không có các cạnh $(x, z), (y, t), (x, t)$.
Giới hạn: số đỉnh và số cạnh của đồ thị không quá $100000$.
Bài 8
Cho lưới ô vuông trên mặt phẳng toạ độ Descartes. Ban đầu các ô đều có màu trắng. Ta sẽ tô màu các ô thành màu đen theo quy tắc sau: có $N$ bước tô; mỗi bước ta sẽ tô một hình chữ nhật con của lưới ô vuông theo $1$ trong $3$ mẫu.
- Mẫu tô $1$: Tô hết tất cả các hàng lẻ của vùng ảnh hưởng và giữ nguyên các hàng chẵn.
- Mẫu tô $2$: Tô hết tất cả các cột lẻ của vùng ảnh hưởng và giữ nguyên các cột chẵn.
- Mẫu tô $3$: Tô theo bàn cờ vua.
Đếm số ô màu đen trên lưới sau N bước tô.
Giới hạn:
- $N \leq 100000$.
- Các ô bị tô có giá trị tuyệt đối toạ độ không quá $10^9$.