USACO 2012 - Tháng 2 - Hạng Bạc

Farmer John đã mua một chiếc máy mới có khả năng trồng cỏ trong bất kỳ vùng hình chữ nhật nào của trang trại được “căn theo trục” (tức là có các cạnh thẳng đứng và nằm ngang). Đáng tiếc, một ngày nọ máy gặp trục trặc và trồng cỏ không chỉ trong một mà trong \(N\) (\(1 \le N \le 1000\)) vùng hình chữ nhật khác nhau, một số vùng thậm chí có thể chồng lấn.

Với các vùng hình chữ nhật đã được trồng cỏ, hãy giúp FJ tính tổng diện tích trang trại hiện được cỏ bao phủ.

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\).
• Các dòng từ 2 đến \(1+N\): mỗi dòng chứa bốn số nguyên \(x_1\), \(y_1\), \(x_2\), \(y_2\) cách nhau bởi dấu cách, xác định một vùng hình chữ nhật có góc trên bên trái là \((x_1,y_1)\) và góc dưới bên phải là \((x_2,y_2)\). Mọi tọa độ đều nằm trong đoạn \(-10^8 \ldots 10^8\).

Dữ liệu ra

In tổng diện tích được cỏ bao phủ. Lưu ý rằng giá trị này có thể quá lớn để lưu trong một số nguyên 32 bit.

Ví dụ

2
0 5 4 1
2 4 6 2

20

Nguồn

USACO 2012 February Contest, Silver - Overplanting (Silver): https://usaco.org/index.php?page=viewproblem2&cpid=115

Tác giả: Brian Dean, 2012.

Là một người âm thầm đam mê máy tính, Farmer John gắn cho tất cả bò của mình các số nhị phân. Tuy nhiên, ông hơi mê tín và chỉ gắn cho bò những số nhị phân có đúng \(K\) bit 1 (\(1 \le K \le 10\)). Tất nhiên, bit đầu của mỗi nhãn luôn là bit 1. FJ gán nhãn theo thứ tự giá trị tăng dần, bắt đầu từ nhãn hợp lệ nhỏ nhất có thể — một số gồm \(K\) bit, tất cả đều là 1. Đáng tiếc, ông không còn nhớ mình đã gán nhãn đến đâu và cần bạn giúp: hãy xác định nhãn thứ \(N\) mà ông cần gán (\(1 \le N \le 10^7\)).

Dữ liệu vào

Dòng 1 chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách.

Dữ liệu ra

In nhãn thứ \(N\) mà FJ cần gán.

Ví dụ

7 3

10110

Nguồn

USACO 2012 February Contest, Silver - Cow IDs: https://usaco.org/index.php?page=viewproblem2&cpid=116

Tác giả: Brian Dean, 2012.

Farmer John sắp chuyển đi! Ông đang cố tìm nơi tốt nhất để xây một trang trại mới nhằm giảm thiểu quãng đường phải di chuyển mỗi ngày.

Khu vực FJ dự định chuyển đến có \(N\) thị trấn (\(1 \le N \le 10\,000\)). Có \(M\) con đường hai chiều (\(1 \le M \le 50\,000\)) nối một số cặp thị trấn. Từ mọi thị trấn đều có thể đến mọi thị trấn khác qua một số con đường. FJ cần bạn giúp chọn thị trấn tốt nhất làm nơi đặt trang trại mới.

Có chợ tại \(K\) thị trấn (\(1 \le K \le 5\)) mà FJ muốn ghé thăm hằng ngày. Cụ thể, mỗi ngày ông dự định rời trang trại mới, ghé thăm \(K\) thị trấn có chợ, rồi quay về trang trại. FJ có thể ghé các chợ theo bất kỳ thứ tự nào mình muốn. Khi chọn thị trấn để xây trang trại mới, FJ chỉ muốn chọn trong \(N-K\) thị trấn không có chợ, vì giá nhà ở những thị trấn này thấp hơn.

Hãy giúp FJ tính quãng đường nhỏ nhất ông phải đi trong lịch trình hằng ngày, nếu ông xây trang trại ở vị trí tối ưu và lựa chọn lịch trình ghé các chợ một cách khôn ngoan nhất có thể.

Dữ liệu vào

• Dòng 1 chứa ba số nguyên \(N\), \(M\), \(K\), cách nhau bởi dấu cách.
• Các dòng từ 2 đến \(1+K\): dòng \(i+1\) chứa một số nguyên trong đoạn \(1 \ldots N\), xác định thị trấn có chợ thứ \(i\). Mỗi chợ nằm ở một thị trấn khác nhau.
• Các dòng từ \(2+K\) đến \(1+K+M\): mỗi dòng chứa 3 số nguyên \(i\), \(j\) (\(1 \le i,j \le N\)) và \(L\) (\(1 \le L \le 1000\)), cách nhau bởi dấu cách, cho biết có một con đường dài \(L\) từ thị trấn \(i\) đến thị trấn \(j\).

Dữ liệu ra

In quãng đường nhỏ nhất FJ cần đi trong lịch trình hằng ngày nếu ông xây trang trại ở vị trí tối ưu.

Ví dụ

5 6 3
1
2
3
1 2 1
1 5 2
3 2 3
3 4 5
4 2 7
4 5 10

12

Nguồn

USACO 2012 February Contest, Silver - Relocation: https://usaco.org/index.php?page=viewproblem2&cpid=117

Tác giả: Brian Dean, 2012.