USACO 2013 - Tháng 11 - Hạng Vàng

Chuồng mới của Farmer John gồm một vòng tròn khổng lồ có \(N\) ô chuồng (\(2 \le N \le 3\,000\,000\)), được đánh số từ \(0..N-1\), trong đó ô \(N-1\) nằm kề ô \(0\).

Cuối mỗi ngày, những con bò của FJ lần lượt trở về chuồng, mỗi con có một ô chuồng ưa thích mà nó muốn chiếm. Tuy nhiên, nếu ô chuồng ưa thích của một con bò đã bị con khác chiếm, nó sẽ lần lượt dò về phía trước từ ô này cho đến khi tìm thấy ô trống đầu tiên rồi chiếm ô đó. Nếu dò qua ô \(N-1\), nó tiếp tục dò từ ô \(0\).

Cho ô chuồng ưa thích của mỗi con bò, hãy xác định chỉ số nhỏ nhất của một ô chuồng vẫn còn trống sau khi tất cả bò đã trở về. Lưu ý rằng đáp án không phụ thuộc vào thứ tự những con bò trở về chuồng.

Để tránh phải đọc một lượng dữ liệu vào khổng lồ, dữ liệu vào của bài toán được mô tả dưới dạng rút gọn bằng \(K\) dòng (\(1 \le K \le 10\,000\)), mỗi dòng có dạng:

X Y A B

Một dòng như vậy mô tả ô chuồng ưa thích của tổng cộng \(XY\) con bò: có \(X\) con bò thích mỗi ô trong các ô \(f(1)..f(Y)\), với \(f(i) = (Ai + B) \bmod N\). Các giá trị \(A\) và \(B\) nằm trong khoảng \(0..1\,000\,000\,000\).

Đừng quên giới hạn bộ nhớ tiêu chuẩn 64 MB áp dụng cho tất cả các bài toán.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên cách nhau bởi dấu cách: \(N\) và \(K\).
• Các dòng \(2..1+K\): mỗi dòng chứa các số nguyên \(X\), \(Y\), \(A\), \(B\), được hiểu như trên. Tổng số bò được mô tả bởi tất cả các dòng này không vượt quá \(N-1\). Nhiều dòng có thể thêm bò vào cùng một ô chuồng.

Dữ liệu ra

• Dòng 1 chứa chỉ số nhỏ nhất của một ô chuồng còn trống.

Ví dụ

10 3
3 2 2 4
2 1 0 1
1 1 1 7 

5

Nguồn

USACO 2013 November Contest, Gold — Problem 1: Empty Stalls

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

\(N\) con bò của Farmer John (\(1 \le N \le 50\,000\)) đứng tại các điểm đôi một khác nhau trên đồng cỏ hai chiều của ông. Ở giữa đồng cỏ có một silo ngũ cốc lớn hình tròn. Những con bò ở hai phía đối diện của silo không thể nhìn thấy nhau vì silo chắn tầm nhìn. Hãy xác định số cặp bò có thể nhìn thấy nhau theo một đường ngắm thẳng.

Silo ngũ cốc có tâm tại gốc tọa độ \((0,0)\) và bán kính \(R\). Không có con bò nào nằm trên hoặc bên trong đường tròn tương ứng với silo, và không có hai con bò nào cùng nằm trên một đường thẳng tiếp xúc với silo. Giá trị \(R\) nằm trong khoảng \(1..1\,000\,000\), và mỗi con bò đứng tại một điểm có tọa độ nguyên trong khoảng \(-1\,000\,000..+1\,000\,000\).

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(N\) và \(R\).
• Các dòng \(2..1+N\): mỗi dòng chứa hai số nguyên mô tả tọa độ \((x,y)\) của một con bò.

Dữ liệu ra

• Dòng 1 chứa số cặp bò có thể nhìn thấy nhau.

Ví dụ

4 5
0 10
0 -10
10 0
-10 0

4

Nguồn

USACO 2013 November Contest, Gold — Problem 2: Line of Sight

Tác giả đề: Brian Dean và Chad Waters, 2013.

Farmer John đang ở chợ để mua vật tư cho trang trại. Trong túi ông có \(K\) đồng xu (\(1 \le K \le 16\)), mỗi đồng có giá trị trong khoảng \(1..100\,000\,000\). FJ muốn thực hiện một dãy gồm \(N\) giao dịch mua hàng (\(1 \le N \le 100\,000\)), trong đó giao dịch thứ \(i\) có giá \(c(i)\) đơn vị tiền (\(1 \le c(i) \le 10\,000\)). Trong quá trình thực hiện lần lượt các giao dịch này, thỉnh thoảng ông có thể dừng lại và dùng một đồng xu duy nhất để thanh toán cho tất cả các món hàng đã mua kể từ lần thanh toán trước đó (dĩ nhiên, đồng xu được dùng phải có giá trị đủ lớn để thanh toán toàn bộ số tiền này). Thật không may, những người bán hàng ở chợ hoàn toàn không có tiền thối, vì vậy mỗi khi FJ dùng một đồng xu có giá trị lớn hơn số tiền phải trả, ông đáng tiếc không nhận lại được tiền thừa!

Hãy tính số tiền lớn nhất FJ có thể còn lại sau khi thực hiện lần lượt cả \(N\) giao dịch mua hàng. In ra \(-1\) nếu FJ không thể thực hiện tất cả các giao dịch.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(K\) và \(N\).
• Các dòng \(2..1+K\): mỗi dòng chứa giá trị của một đồng xu của FJ.
• Các dòng \(2+K..1+N+K\): \(N\) dòng này chứa chi phí của các giao dịch FJ dự định thực hiện.

Dữ liệu ra

• Dòng 1 chứa số tiền lớn nhất FJ có thể còn lại, hoặc \(-1\) nếu FJ không thể hoàn thành tất cả các giao dịch mua hàng.

Ví dụ

3 6
12
15
10
6
3
3
2
3
7

12

Nguồn

USACO 2013 November Contest, Gold — Problem 3: No Change

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