TST 2020

Table of contents

  1. Đề bài
    1. Ngày 1
    2. Ngày 2

Đề bài

Ngày 1

Bài 1

Cho 1 dãy số $a$ gồm $n$ phần tử. Ta muốn chia thỏa dãy thành các đoạn con liên tiếp thỏa mãn:

  • Có số đoạn ít nhất.
  • Tổng của các số cùng một đoạn không vượt quá một số $C$ cho trước.

Tìm cách chia sao cho tổng của các số lớn nhất của từng đoạn là lớn nhất.

Giới hạn:
Trong tất cả các test: $n \leq 10^5$ , $a_i$ là số nguyên dương $\leq 10^9$, $C \leq 10^{10}$.

  • Subtask 1: $n \leq 100$
  • Subtask 2: $a_1 \geq a_2 \geq … \geq a_n$
  • Subtask 3: Dữ liệu vào đảm bảo số đoạn ít nhất cần để chia dãy không quá 3
  • Subtask 4: $C \leq 100$
  • Subtask 5: Không có ràng buộc gì thêm

Bài 2

Đây là bài interactive.

Cho cây $n$ đỉnh (có thể biểu diễn dưới dạng đồ thị phẳng, chỉ có cạnh song song trục tọa độ). Ta tô màu các đỉnh theo quy tắc:

  1. Chọn một đỉnh bất kì làm gốc, tô màu nó là 0
  2. Những đỉnh kề với đỉnh màu 0, chưa tô màu thì tô màu 1
  3. Những đỉnh kể với đỉnh màu 1, chưa tô màu thì tô màu 2
  4. Những đỉnh kể với đỉnh màu 2, chưa tô màu thì tô màu 0
  5. …

Bạn có thể hỏi máy chấm màu của một đỉnh bất kì. Nhiệm vụ của bạn là trả về nút gốc được chọn là nút nào. Để đạt điểm tối đa của một test thì số câu hỏi phải $\leq 20$.

Mỗi file input có nhiều test con. Điểm của một input sẽ được tính dựa trên số câu hỏi lớn nhất dùng để trả lời các test con.

Giới hạn: Trong tất cả các test: $n \leq 10^5$.

  • Subtask 1 (10): $n \leq 20$
  • Subtask 2 (18): Cây có dạng đường thẳng
  • Subtask 3 (18): $n \leq 1000$
  • Subtask 4 (54): Không có ràng buộc gì thêm

Bài 3:

Cho một dãy $n$ phần tử. Cần phải trả lời $q$ truy vấn có dạng sau:

$Query(l,r)$: cần tìm 2 số $x$, $y$ thỏa mãn $1 \leq x \leq l \leq r \leq y \leq n$, sao cho đoạn $[x,y]$ có trung bình cộng lớn nhất trong tất cả đoạn $[x, y]$ có thể chọn.

Giới hạn: Trong tất cả test: $n \leq 10^6$, $q \leq 5 \cdot 10^5$, $|a_i| \leq 4 \cdot 10^6$

  • Subtask 1 (10): $n, q \leq 100$
  • Subtask 2 (12): $n \leq 2000, q \leq 10^5$
  • Subtask 3 (14): $n \leq 10^5, q \leq 50$
  • Subtask 4 (20): $n, q \leq 50\,000$
  • Subtask 5 (30): $n \leq 10^6, q \leq 10^5$
  • Subtask 6 (14): Không có ràng buộc gì thêm

Ngày 2

Bài 4:

Cho một lưới dạng tổ ong (mỗi ô là hình lục giác đều), có tâm đánh số là $0$, có $r$ lớp bao quanh tâm đó, được đánh số theo đường xoắn ốc.

Hình minh họa gần giống với đề bài, với $r = 2$:
Hình minh họa gần giống với đề bài

Có $n$ ô cấm không được dùng.

Đếm số lượng bộ 6 ô không cấm, sao cho khi lấy tâm 6 ô đó, nối lại thì ta được hình lục giác đều.

Giới hạn: $r \leq 300$, $n \leq$ số lượng ô.

  • Subtask 1 (14): $r \leq 3, n \leq 2$
  • Subtask 2 (16): $r \leq 50, n \leq 2$
  • Subtask 3 (14): $r \leq 300, n \leq 0$
  • Subtask 4 (16): $r \leq 300, n \leq 2$
  • Subtask 5 (20): $r \leq 100$
  • Subtask 6 (20): không có ràng buộc gì thêm

Bài 5:

Cho một cây, gốc là đỉnh $1$, cạnh có trọng số, đỉnh có màu đen hoặc trắng.

Có $3$ loại truy vấn sau:

  • Đổi màu $1$ đỉnh
  • Xét cây con gốc $u$: dựng đồ thi mới gồm các đỉnh màu đen của cây con gốc $u$. Đây là đồ thị đầy đủ, với trọng số của cạnh $(u,v)$ (trên đồ thị mới) chính là trọng số của đường đi từ $u$ đến $v$ trên cây ban đầu. Yêu cầu tìm chu trình Hamilton có trọng số nhỏ nhất trên đồ thị này.
  • Giống truy vấn trên, nhưng cần tìm đường đi thay vì chu trình.

Giới hạn: $n, q \leq 2\cdot10^5$

  • Subtask 1: $n, q \leq 5000$ và $u = 1$ trong mọi truy vấn $2$, $3$
  • Subtask 2: Các truy vấn loại $1$ chỉ đổi làm đổi màu đỉnh từ trắng thành đen và $u = 1$ trong mọi truy vấn loại $2$, $3$
  • Subtask 3: Trong các truy vấn loại $2$, $u = 1$ và không có truy vấn loại $3$
  • Subtask 4: $u = 1$ Trong các truy vấn loại $2$, $3$
  • Subtask 5: Không có truy vấn loại $3$
  • Subtask 6: Không có ràng buộc gì thêm.

Bài 6:

Đây là bài output only.

Ta có một kho hàng nằm ở địa điểm $0$, có $n$ địa điểm cần giao hàng. Ta có $1$ cái xe tải và $m$ cái mô tô.

Xe mô tô sẽ giao hàng theo quy luật:

Đi từ $0$, đến $x$, quay về $0$, với thời gian là $C_x$.

Chiếc xe tải sẽ giao hàng theo quy luật:

Bắt đầu từ địa điểm $0$, đi tới địa điểm $1$, rồi đi tới $2, …, n$, rồi quay về $0$. Lưu ý là nếu địa điểm $i$ đã giao hàng (bằng xe mô tô rồi) thì xe tải sẽ bỏ qua địa điểm đó (ví dụ địa điểm $5$ và $6$ đã được giao bằng xe tải thì xe tải sẽ đi từ $4$ đến $7$ luôn, bỏ qua $5$ và $6$). Thời gian đi từ đỉnh $i$ tới đỉnh $j$ là $T_{ij}$.

Ta cần xếp lịch để giao hàng sao cho trong $3$ đỉnh liên tiếp, tồn tại ít nhất $1$ đỉnh giao bằng xe tải, đồng thời thời gian hoàn thành là nhỏ nhất.

Giới hạn: $n \leq 500$

  • $10$ test đầu, $m = 1$
  • $10$ test sau, $m \leq 5$