TST 2014

Table of contents

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

Đề bài

Đề bài ở đây không ghi đầy đủ các subtask bé.

Ngày 1

Bài 1

Cho $n$ quả bóng bowling xếp thành hàng thẳng, đánh số từ $1$ đến $n$ (theo thứ tự từ trái qua phải).

Người chơi được ném bóng vào các quả bóng bowling một số lần tùy ý, nhưng phải ném ít nhất một lần. Khi ném vào quả bóng bowling thứ $i$, các quả bóng bowling có chỉ số chênh lệch không quá $r$ so với $i$ sẽ bị đổ.

Khi quả bowling thứ $i$ bị đổ, người chơi nhận được $a_i$ điểm. Tính số điểm tối đa mà người chơi nhận được.

Giới hạn:

  • $0 \leq r \leq n \leq 2 \cdot 10^5$
  • $a_i \leq 10^9$.

Bài 2

Cho một đơn đồ thị vô hướng không khuyên và có trọng số. Có nhiều truy vấn, mỗi truy vấn chứa 3 đỉnh $x, y, z$:

Tìm cách bỏ đi một số cạnh của đồ thị sao cho, với mọi đỉnh $u$ của đồ thị, độ dài đường đi ngắn nhất trong các đường đi từ $x$ hoặc $y$ hoặc $z$ tới $u$ là không đổi và tổng trọng số các cạnh được giữ lại là nhỏ nhất. In ra tích của tổng nhỏ nhất này với $100$.

Giới hạn:

  • Đồ thị có không quá $500$ đỉnh, $10000$ cạnh và có không quá $10000$ truy vấn.
  • Trọng số các cạnh nguyên dương và có giá trị tuyệt đối không quá $10^9$.

Bài 3

Các cây sưa được trồng trên các vị trí phân biệt trên $2$ đường thẳng song song với nhau. Khoảng cách giữa 2 đường thẳng này là $w$.

$m$ cây sưa được trồng trên đường thẳng thứ nhất có tọa độ là $a_1 < a_2< … < a_m$. $n$ cây sưa được trồng trên đường thẳng thứ hai có toạ đồ là $b_1 < b_2 < … < b_n$.

Một sợi dây độ dài $L$ dùng để bao quanh các cây sưa, sao cho có $1$ số cây liên tiếp (ít nhất là $1$) trên mỗi đường thẳng được bao bọc bởi sợi dây.

Tính số cây sưa tối đa có thể bao được.

Giới hạn:

  • $m \leq 2000 , n \leq 2000$.
  • Dữ liệu vào đảm bảo nếu số cây sưa tối đa bao được với một dây độ dài $L$ là $P$ thì không tồn tại cách bao $P+1$ cây sưa với sợi dây có độ dài $L+10^-5$.

Bài 4

Radar là một hệ thống trạm quan sát, gồm hai thiết bị được gắn ở $2$ điểm $(x_1, y_1)$ và $(x_2, y_2)$ thỏa mãn $x_1 \leq x_2$ và $y_2 \leq y_1$. Thiết bị ở $(x_1, y_1)$ có thể quan sát các điểm ở phía dưới bên phải nó, thiết bị ở $(x_2, y_2)$ có thể quan sát các điểm ở phía trên bên trái nó.

Vùng nhìn thấy của một radar là hợp vùng quan sát được của 2 thiết bị của nó. Radar $a$ được coi là nhìn thấy radar $b$ khi và chỉ khi tồn tại một trong $2$ thiết bị của radar $b$ được đặt trong vùng nhìn thấy của radar $a$. Từ định nghĩa này, ta khó dàng chứng minh rằng radar $a$ nhìn thấy radar $b$ khi và chỉ khi radar $b$ nhìn thấy radar $a$.

Cho $n$ radar. Yêu cầu:

  1. Tìm một tập con các radar sao cho $2$ radar thuộc tập hợp này đôi một không nhìn thấy nhau. In ra lực lượng của tập hợp lớn nhất thỏa mãn điều kiện này.
  2. Tìm cách ghép các radar thành cặp sao cho $2$ radar thuộc cặp bất kỳ đều nhìn được thấy nhau và một radar chỉ xuất hiện trong tối đa một cặp. In ra số lượng cặp tối đa ghép được.

Giới hạn: $n \leq 10000$.

Ngày 2

Bài 5

Cho $n$ điểm trên mặt phẳng Decartes, tìm số nguyên $L$ nhỏ nhất sao cho:

  1. Tồn tại 2 hình vuông cạnh $L$ bao chứa $n$ điểm.
  2. Tồn tại 2 hình vuông không có điểm chung cạnh $L$ bao chứa $n$ điểm.

$1$ hình vuông được gọi là chứa $1$ điểm nếu như điểm đó nắm trên cạnh hoặc nằm trong hình vuông này.

Giới hạn:

  • $n \leq 10^5$ .
  • Tọa độ các điểm có giá trị tuyệt đối không quá $10^9$.

Bài 6

Có $n$ điểm trên đường thẳng. Điểm thứ $i$ có tọa độ $x_i$ và tại đó có $1$ con ngựa có khả năng đi quãng đường không quá $k_i$ và đi một đơn vị độ dài mất $a_i$ giây.

Bạn cần đi từ điểm $s$ tới điểm $t$. Khi đứng ở mỗi điểm, bạn có thể đổi sang đi con ngựa ở điểm đó hoặc tiếp tục đi bằng con ngựa hiện tại. Thời gian để đổi ngựa ở mọi điểm đều là $\Delta$. Một con ngựa chỉ được sử dụng không quá $1$ lần (tức là sau khi đổi $1$ con ngựa sang con khác thì không thể sử dụng lại nó nữa).

Tính thời gian nhỏ nhất để đi từ $s$ tới $t$, hoặc in ra $-1$ nếu không thể thực hiện điều này.

Giới hạn:

  • Các số trong input không âm và không quá $10^9$.
  • $1 \leq s,t \leq n \leq 10^5$.

Bài 7

Có $n$ cặp phong bì. Mỗi phong bì thuộc mỗi cặp chứa $2$ số nguyên phân biệt.

Với mỗi cặp phong bì, bạn được quyền lấy $0$ hoặc $1$ phong bì bất kỳ. Tập hợp các phong bì bạn lấy cần thỏa mãn tính chất: Xét mọi tập con $S$ của tập các phong bì bạn lấy, tồn tại ít nhất 1 số nguyên xuất hiện trong các phong bì của $S$ một số lẻ lần.

Tìm số phong bì lớn nhất lấy được thỏa mãn điều kiện trên.

Giới hạn: $n \leq 300$.

Bài 8

Cho một mạng truyền thông có dạng cây $n$ đỉnh, trong đó mỗi đỉnh của cây là một trạm thông tin.

Có $m$ yêu cầu liên lạc, mỗi yêu cầu gồm 2 địa điểm $u, v$ là 2 đỉnh của cây, và $c$ là lợi nhuận của yêu cầu đó. Cần chọn ra 2 đỉnh $a, b$ trên cây sao cho tổng lợi nhuận của mọi yêu cầu có cả 2 địa điểm nằm trên đường đi từ $a$ đến $b$ trên cây là lớn nhất.

Giới hạn: $n \leq 150000, m \leq 100000$