BOI 2007 - Ngày 2

Leopold vừa trúng xổ số và nhận được một khu đất rộng lớn, trên đó có một dinh thự chính cùng nhiều tòa nhà khác. Anh muốn dựng một hàng rào bao quanh dinh thự chính.

Nhìn từ trên xuống, mỗi tòa nhà nằm trong một hình chữ nhật cấm mà hàng rào không được đi qua. Các cạnh của mọi hình chữ nhật song song với các trục tọa độ. Mỗi đoạn hàng rào cũng phải song song với một trong hai trục.

Hãy tính độ dài nhỏ nhất của một hàng rào hợp lệ bao quanh dinh thự chính.

Dữ liệu vào

Dòng đầu chứa số nguyên dương \(m\), số tòa nhà trong khu đất. Mỗi trong \(m\) dòng tiếp theo chứa bốn số nguyên \(t_x\), \(t_y\), \(b_x\), \(b_y\). Trong đó, \((t_x,t_y)\) là góc trên bên trái và \((b_x,b_y)\) là góc dưới bên phải của hình chữ nhật cấm quanh một tòa nhà.

Hình chữ nhật đầu tiên bao quanh dinh thự chính.

Dữ liệu ra

In ra một số nguyên dương là độ dài nhỏ nhất của một hàng rào hợp lệ bao quanh dinh thự chính.

Ràng buộc

Phân nhóm

• \(30\%\) số phép thử có \(m \le 10\).

Ví dụ

4
8 4 13 8
2 1 6 7
4 7 9 11
14 7 19 11

32

Xét một lưới đều gồm \(3 \times N\) điểm. Mỗi điểm có tối đa tám điểm kề như hình dưới đây.

Ta cần đếm số cách khác nhau để nối các điểm thành một đa giác thỏa mãn đồng thời:

1. Tập đỉnh của đa giác gồm toàn bộ \(3 \times N\) điểm.
2. Hai đỉnh liên tiếp của đa giác là hai điểm kề nhau trong lưới.
3. Đa giác đơn, tức là không tự cắt.

Hai đa giác có thể tạo được khi \(N=6\) được minh họa dưới đây.

Hãy tính số đa giác thỏa mãn theo modulo \(1\,000\,000\,000\).

Dữ liệu vào

Dòng duy nhất chứa một số nguyên dương \(N\).

Dữ liệu ra

In ra phần dư của số cách nối các điểm khi chia cho \(1\,000\,000\,000\).

Ràng buộc

Phân nhóm

• \(30\%\) số phép thử có \(N \le 200\).
• \(70\%\) số phép thử có \(N \le 100\,000\).

Ví dụ

3

8

4

40

Cho dãy \(a_1, \ldots, a_n\). Ta có thể thực hiện thao tác \(\operatorname{reduce}(i)\): thay hai phần tử \(a_i\), \(a_{i+1}\) bằng một phần tử duy nhất có giá trị \(\max(a_i,a_{i+1})\). Dãy nhận được ngắn hơn một phần tử và chi phí của thao tác bằng \(\max(a_i,a_{i+1})\).

Sau \(n-1\) thao tác, dãy chỉ còn một phần tử. Hãy tính tổng chi phí nhỏ nhất của một cách rút gọn dãy như vậy.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\), độ dài dãy. Mỗi trong \(n\) dòng tiếp theo chứa một số nguyên \(a_i\).

Dữ liệu ra

In ra tổng chi phí nhỏ nhất để rút gọn dãy còn một phần tử.

Ràng buộc

Phân nhóm

• \(30\%\) số phép thử có \(n \le 500\).
• \(50\%\) số phép thử có \(n \le 20\,000\).

Ví dụ

3
1
2
3

5