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

Sau nhiều năm đạt sản lượng sữa kỷ lục, Nông dân John hiện điều hành cả một mạng lưới gồm \(N\) trang trại (\(1 \le N \le 100\)). Trang trại \(i\) nằm tại vị trí \((x_i,y_i)\) trên mặt phẳng hai chiều, khác với vị trí của mọi trang trại khác; cả \(x_i\) và \(y_i\) đều là số nguyên.

FJ cần bạn giúp lập kế hoạch cho lộ trình giao hàng hằng ngày để mang vật tư đến \(N\) trang trại. Bắt đầu từ trang trại \(1\), ông dự định lần lượt ghé thăm các trang trại (trang trại \(1\), rồi trang trại \(2\), sau đó trang trại \(3\), v.v.), cuối cùng quay lại trang trại \(1\) sau khi ghé trang trại \(N\). FJ mất một phút để đi một bước theo hướng bắc, nam, đông hoặc tây. Hơn nữa, FJ muốn ghé mỗi trang trại đúng một lần trong toàn bộ hành trình (tất nhiên ngoại trừ trang trại \(1\), nơi ông ghé hai lần).

Hãy giúp FJ xác định thời gian nhỏ nhất để hoàn thành toàn bộ lộ trình giao hàng.

Dữ liệu vào

• Dòng đầu tiên chứa số lượng trang trại \(N\).
• \(N\) dòng tiếp theo; dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\) cách nhau bởi dấu cách (\(1 \le x_i,y_i \le 1\,000\,000\)).

Dữ liệu ra

• Dòng đầu tiên chứa số phút nhỏ nhất FJ cần để hoàn thành lộ trình giao hàng, hoặc -1 nếu không thể tìm được một lộ trình hợp lệ ghé mỗi trang trại đúng một lần (ngoại trừ trang trại \(1\)).

Ví dụ

4
2 2
2 4
2 1
1 3

12

Nguồn

USACO 2012 January Contest, Silver Division — Delivery Route

Tác giả đề: Brian Dean, 2012.

Farmer John vừa nhận một chuyến hàng mới gồm \(N\) kiện cỏ khô (\(1 \le N \le 20\)), trong đó kiện thứ \(i\) có kích thước \(S_i\) (\(1 \le S_i \le 100\)). Ông muốn chia các kiện cỏ vào ba kho sao cho công bằng nhất có thể.

Sau khi suy nghĩ kỹ, FJ quyết định rằng một cách chia các kiện cỏ “công bằng” phải làm cho phần lớn nhất nhỏ nhất có thể. Cụ thể, gọi \(B_1\), \(B_2\) và \(B_3\) lần lượt là tổng kích thước của tất cả các kiện được đặt vào kho 1, 2 và 3 (với \(B_1 \ge B_2 \ge B_3\)), FJ muốn làm cho \(B_1\) nhỏ nhất có thể.

Ví dụ, nếu có 8 kiện với các kích thước:

2 4 5 8 9 14 15 20

Một cách chia công bằng là:

Kho 1: 2 9 15   B_1 = 26
Kho 2: 4 8 14   B_2 = 26
Kho 3: 5 20     B_3 = 25

Hãy giúp FJ xác định giá trị của \(B_1\) trong một cách chia các kiện cỏ công bằng.

Dữ liệu vào

• Dòng 1 chứa số kiện cỏ \(N\).
• Các dòng từ 2 đến \(1+N\): dòng \(i+1\) chứa \(S_i\), kích thước của kiện thứ \(i\).

Dữ liệu ra

In ra giá trị của \(B_1\) trong một cách chia các kiện cỏ công bằng.

Ví dụ

8
14
2
5
15
8
9
20
4

26

Nguồn

USACO 2012 January Contest, Silver - Bale Share: https://usaco.org/index.php?page=viewproblem2&cpid=107

Tác giả: Fatih Gelgi, 2010.

Farmer John phát hiện ra rằng đàn bò của ông cho sữa chất lượng cao hơn khi phải vận động gắng sức. Vì vậy, ông quyết định đưa \(N\) con bò (\(1 \le N \le 25\,000\)) đi leo lên rồi xuống một ngọn núi gần đó!

Con bò thứ \(i\) mất \(U(i)\) đơn vị thời gian để leo lên núi, rồi mất \(D(i)\) đơn vị thời gian để xuống núi. Vì là bò đã được thuần hóa, mỗi con cần một nông dân giúp đỡ trong từng chặng leo; nhưng do tình hình kinh tế khó khăn, chỉ có hai nông dân là Farmer John và người anh em họ Farmer Don. FJ dự định dẫn bò ở chặng lên, sau đó FD sẽ dẫn bò ở chặng xuống. Vì mọi con bò đều cần người dẫn và mỗi chặng chỉ có một nông dân phụ trách, tại bất kỳ thời điểm nào nhiều nhất một con bò được leo lên (với sự hỗ trợ của FJ), và nhiều nhất một con bò được leo xuống (với sự hỗ trợ của FD). Một nhóm bò có thể tạm thời tụ lại trên đỉnh núi nếu chúng đã leo lên nhưng phải chờ FD hỗ trợ mới có thể đi xuống. Thứ tự bò xuống núi có thể khác thứ tự chúng leo lên.

Hãy xác định lượng thời gian ít nhất có thể để cả \(N\) con bò hoàn thành toàn bộ hành trình.

Dữ liệu vào

• Dòng 1 chứa số bò \(N\).
• Các dòng từ 2 đến \(1+N\): dòng \(i+1\) chứa hai số nguyên \(U(i)\) và \(D(i)\) cách nhau bởi dấu cách (\(1 \le U(i), D(i) \le 50\,000\)).

Dữ liệu ra

In một số nguyên duy nhất biểu thị lượng thời gian ít nhất để tất cả các con bò vượt qua ngọn núi.

Ví dụ

3
6 4
8 1
2 3

17

Nguồn

USACO 2012 January Contest, Silver - Mountain Climbing: https://usaco.org/index.php?page=viewproblem2&cpid=108

Tác giả: Videh Seksaria, 2012.