BOI 2016 - Ngày 1

Một công ty có \(n\) nhân viên đang chuẩn bị tái cơ cấu. Cơ cấu tổ chức mới được biểu diễn bằng một cây có gốc, trong đó mỗi đỉnh là cấp trên trực tiếp của các đỉnh con của mình.

Mỗi nhân viên có một danh sách những người mà họ chấp nhận làm cấp trên. Ngoài ra, tất cả nhân viên đều phải được trả lương. Mức lương phải là một số nguyên dương, và lương của mỗi cấp trên phải lớn hơn tổng lương của các cấp dưới trực tiếp của người đó.

Nhiệm vụ của bạn là tổ chức lại công ty sao cho tất cả các điều kiện trên đều được thỏa mãn và tổng lương của toàn bộ nhân viên nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\): số nhân viên. Các nhân viên được đánh số \(1,2,\ldots,n\).

\(n\) dòng tiếp theo mô tả nguyện vọng của các nhân viên. Dòng thứ \(i\) trong số này chứa số nguyên \(k_i\), theo sau là danh sách gồm \(k_i\) số nguyên. Danh sách này gồm tất cả những nhân viên mà nhân viên thứ \(i\) chấp nhận làm cấp trên của mình.

Dữ liệu ra

In ra tổng lương nhỏ nhất trong tất cả các cách tái cơ cấu hợp lệ. Dữ liệu bảo đảm tồn tại ít nhất một cách thỏa mãn.

Phân nhóm

1. Nhóm 1 (22 điểm): \(2 \le n \le 10\); \(\sum_{i=1}^{n} k_i \le 20\).
2. Nhóm 2 (45 điểm): \(2 \le n \le 100\); \(\sum_{i=1}^{n} k_i \le 200\).
3. Nhóm 3 (33 điểm): \(2 \le n \le 5000\); \(\sum_{i=1}^{n} k_i \le 10000\).

Ví dụ

4
1 4
3 1 3 4
2 1 2
1 3

8

Nguồn

Baltic Olympiad in Informatics 2016, ngày thi thứ nhất, bài A.

Tại thủ đô của Byteland có một công viên hình chữ nhật được bao quanh bởi hàng rào. Các cây và khách tham quan trong công viên được biểu diễn bằng các hình tròn.

Công viên có bốn cổng, mỗi cổng nằm ở một góc: \(1\) là góc dưới bên trái, \(2\) là góc dưới bên phải, \(3\) là góc trên bên phải và \(4\) là góc trên bên trái. Khách tham quan chỉ có thể vào và ra khỏi công viên qua các cổng này.

Một khách tham quan có thể vào hoặc ra khỏi công viên khi hình tròn biểu diễn người đó tiếp xúc với cả hai cạnh tạo thành góc của cổng tương ứng. Khách tham quan có thể di chuyển tự do trong công viên, nhưng không được chồng lấn với bất kỳ cây nào hoặc với hàng rào.

Hai đối tượng được gọi là tiếp xúc nếu chúng có đúng một điểm chung. Hai đối tượng được gọi là chồng lấn nếu chúng có nhiều hơn một điểm chung.

Với mỗi khách tham quan, biết cổng mà người đó sẽ đi vào, hãy xác định những cổng mà người đó có thể đi ra.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số cây trong công viên và số khách tham quan.

Dòng thứ hai chứa hai số nguyên \(w\) và \(h\): chiều rộng và chiều cao của công viên. Góc dưới bên trái có tọa độ \((0,0)\), còn góc trên bên phải có tọa độ \((w,h)\).

\(n\) dòng tiếp theo mô tả các cây. Mỗi dòng chứa ba số nguyên \(x\), \(y\) và \(r\): cây có tâm tại \((x,y)\) và bán kính \(r\). Các cây không chồng lấn với nhau hoặc với hàng rào.

Cuối cùng là \(m\) dòng mô tả các khách tham quan. Mỗi dòng chứa hai số nguyên \(r\) và \(e\): bán kính của khách tham quan và cổng mà người đó sẽ đi vào công viên.

Ngoài ra, tại mỗi góc công viên có một vùng hình vuông kích thước \(2k \times 2k\) mà không cây nào chồng lấn lên, trong đó \(k\) là bán kính của khách tham quan lớn nhất.

Dữ liệu ra

Với mỗi khách tham quan theo thứ tự trong dữ liệu vào, in ra một dòng gồm số hiệu các cổng mà người đó có thể đi ra, theo thứ tự tăng dần và không có dấu cách ở giữa.

Ràng buộc

Trong mọi phân nhóm, \(4k < w,h \le 10^9\), trong đó \(k\) là bán kính của khách tham quan lớn nhất.

Phân nhóm

1. Nhóm 1 (27 điểm): \(1 \le n \le 2000\); \(m=1\).
2. Nhóm 2 (31 điểm): \(1 \le n \le 200\); \(1 \le m \le 10^5\).
3. Nhóm 3 (42 điểm): \(1 \le n \le 2000\); \(1 \le m \le 10^5\).

Ví dụ

5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1

1234
2
14

Nguồn

Baltic Olympiad in Informatics 2016, ngày thi thứ nhất, bài B.

Một bảng ô vuông kích thước \((2n+1) \times (2n+1)\) được xây dựng như sau. Số \(1\) được đặt ở ô chính giữa, số \(2\) được đặt ở ô ngay bên phải nó, và các số tiếp theo được đặt dọc theo một đường xoắn ốc ngược chiều kim đồng hồ.

Nhiệm vụ của bạn là trả lời \(q\) truy vấn. Mỗi truy vấn yêu cầu tính tổng các số trong một vùng hình chữ nhật của bảng, lấy phần dư khi chia cho \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\): tham số xác định kích thước bảng và số truy vấn.

\(q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1\), \(y_1\), \(x_2\) và \(y_2\), với \(-n \le x_1 \le x_2 \le n\) và \(-n \le y_1 \le y_2 \le n\). Bạn cần tính tổng các số trong vùng hình chữ nhật có hai góc đối diện là \((x_1,y_1)\) và \((x_2,y_2)\).

Dữ liệu ra

Với mỗi truy vấn theo thứ tự trong dữ liệu vào, in ra một dòng chứa kết quả, lấy phần dư khi chia cho \(10^9+7\).

Ràng buộc

Trong mọi phân nhóm, \(1 \le q \le 100\).

Phân nhóm

1. Nhóm 1 (12 điểm): \(1 \le n \le 1000\).
2. Nhóm 2 (15 điểm): \(1 \le n \le 10^9\); mọi truy vấn đều có \(x_1=x_2\) và \(y_1=y_2\).
3. Nhóm 3 (17 điểm): \(1 \le n \le 10^5\).
4. Nhóm 4 (31 điểm): \(1 \le n \le 10^9\); mọi truy vấn đều có \(x_1=y_1=1\).
5. Nhóm 5 (25 điểm): \(1 \le n \le 10^9\).

Ví dụ

2 3
0 -2 1 1
-1 0 1 0
1 2 1 2

74
9
14

Nguồn

Baltic Olympiad in Informatics 2016, ngày thi thứ nhất, bài C.