USACO 2017 - Tháng 12 - Hạng Vàng

Bessie và Elsie mỗi cô đã nướng \(N\) chiếc bánh (\(1 \leq N \leq 10^5\)). Mỗi chiếc trong tổng số \(2N\) chiếc bánh có một độ ngon theo đánh giá của Bessie và một độ ngon (có thể khác) theo đánh giá của Elsie.

Bessie đang nghĩ đến việc tặng một chiếc bánh của mình cho Elsie. Nếu nhận bánh từ Bessie, Elsie sẽ cảm thấy mình có nghĩa vụ tặng lại Bessie một chiếc bánh của cô. Để không tỏ ra keo kiệt cũng không quá phô trương, Elsie sẽ cố chọn một chiếc bánh mà theo đánh giá của cô, nó ngon ít nhất bằng chiếc bánh cô vừa nhận nhưng không ngon hơn quá \(D\) đơn vị (\(0 \leq D \leq 10^9\)). Có thể không tồn tại chiếc bánh như vậy; trong trường hợp đó, Elsie sẽ dùng một tên giả và tự lưu đày sang Nhật Bản.

Nhưng nếu Elsie tặng lại Bessie một chiếc bánh, Bessie cũng sẽ cố tặng Elsie một chiếc bánh mà theo đánh giá của Bessie, nó ngon ít nhất bằng chiếc bánh Elsie vừa tặng nhưng không ngon hơn quá \(D\) đơn vị. Nếu điều này là bất khả thi, Bessie cũng sẽ tự lưu đày. Nếu không, cô sẽ tặng chiếc bánh đã chọn cho Elsie. Chu trình này tiếp tục cho đến khi một trong hai cô bò bị lưu đày, một kết cục không vui, hoặc một cô bò nhận được chiếc bánh mà cô đánh giá có độ ngon bằng \(0\); trong trường hợp đó, việc trao đổi quà kết thúc và cả hai cô bò đều vui vẻ.

Lưu ý rằng một chiếc bánh không thể được tặng hai lần, và không cô bò nào được tặng trả lại chiếc bánh mà mình đã nhận.

Với mỗi chiếc trong \(N\) chiếc bánh mà Bessie có thể chọn làm món quà đầu tiên cho Elsie, hãy xác định số bánh nhỏ nhất có thể được tặng trong cuộc trao đổi sau đó trước khi hai cô bò trở nên vui vẻ.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(D\).

\(2N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách, lần lượt biểu thị độ ngon của một chiếc bánh theo đánh giá của Bessie và độ ngon của chiếc bánh đó theo đánh giá của Elsie.

\(N\) dòng đầu tiên mô tả các chiếc bánh của Bessie, và \(N\) dòng còn lại mô tả các chiếc bánh của Elsie.

Mọi giá trị độ ngon được đảm bảo nằm trong khoảng \([0, 10^9]\).

Dữ liệu ra

Kết quả gồm \(N\) dòng. Dòng \(i\) chứa một số nguyên duy nhất: số bánh nhỏ nhất có thể được tặng trong một cuộc trao đổi quà vui vẻ bắt đầu bằng chiếc bánh thứ \(i\) của Bessie. Nếu không có cuộc trao đổi nào bắt đầu bằng chiếc bánh thứ \(i\) có kết thúc vui vẻ, dòng \(i\) chứa số nguyên duy nhất \(-1\).

Ví dụ

2 1
1 1
5 0
4 2
1 4

3
1

Nguồn

USACO 2017 December Contest, Gold — A Pie for a Pie

Tác giả bài toán: Dhruv Rohatgi.

Bác nông dân John có một trang trại lớn với \(N\) chuồng bò (\(1 \leq N \leq 10^5\)), trong đó một số chuồng đã được sơn và một số chưa được sơn. Bác nông dân John muốn sơn các chuồng còn lại để tất cả các chuồng đều được sơn, nhưng bác chỉ có ba màu sơn. Hơn nữa, cô bò quý Bessie sẽ bối rối nếu hai chuồng được nối trực tiếp với nhau có cùng màu, nên bác muốn đảm bảo tình huống này không xảy ra.

Các đường nối giữa \(N\) chuồng được đảm bảo không tạo thành bất kỳ “chu trình” nào. Nói cách khác, giữa hai chuồng bất kỳ có nhiều nhất một dãy các đường nối dẫn từ chuồng này đến chuồng kia.

Có bao nhiêu cách để bác nông dân John sơn các chuồng còn lại chưa có màu?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(0 \leq K \leq N\)), lần lượt là số chuồng trong trang trại và số chuồng đã được sơn.

\(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) (\(1 \leq x, y \leq N\), \(x \neq y\)), mô tả một lối đi nối trực tiếp chuồng \(x\) với chuồng \(y\).

\(K\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(b\) và \(c\) (\(1 \leq b \leq N\), \(1 \leq c \leq 3\)), cho biết chuồng \(b\) được sơn màu \(c\).

Dữ liệu ra

Tính số cách hợp lệ để sơn các chuồng còn lại sao cho không có hai chuồng được nối trực tiếp nào cùng màu. In kết quả theo modulo \(10^9 + 7\).

Ví dụ

4 1
1 2
1 3
1 4
4 3

8

Nguồn

USACO 2017 December Contest, Gold — Barn Painting

Tác giả bài toán: Nick Wu.

Bác nông dân John đang chuẩn bị một bữa ăn ngon cho đàn bò! Trong chuồng, bác có \(N\) kiện cỏ khô (\(1 \leq N \leq 100{,}000\)). Kiện cỏ thứ \(i\) có độ ngon \(F_i\) (\(1 \leq F_i \leq 10^9\)) và độ cay \(S_i\) (\(1 \leq S_i \leq 10^9\)).

Bữa ăn chỉ gồm một món, được tạo bởi một đoạn liên tiếp chứa một hoặc nhiều kiện cỏ khô liên tiếp (bác nông dân John không thể thay đổi thứ tự các kiện cỏ). Tổng độ ngon của bữa ăn là tổng độ ngon của các kiện cỏ trong đoạn. Độ cay của bữa ăn là độ cay lớn nhất trong số tất cả các kiện cỏ thuộc đoạn.

Bác nông dân John muốn xác định độ cay nhỏ nhất mà bữa ăn một món có thể đạt được, với điều kiện tổng độ ngon phải ít nhất là \(M\) (\(1 \leq M \leq 10^{18}\)).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), lần lượt là số kiện cỏ khô và tổng độ ngon tối thiểu mà bữa ăn phải có. \(N\) dòng tiếp theo mô tả \(N\) kiện cỏ, mỗi dòng chứa hai số nguyên: trước tiên là độ ngon \(F\), sau đó là độ cay \(S\).

Dữ liệu ra

In ra độ cay nhỏ nhất của một bữa ăn một món thỏa mãn yêu cầu về độ ngon tối thiểu. Luôn tồn tại ít nhất một bữa ăn một món thỏa mãn yêu cầu về độ ngon.

Ví dụ

5 10
4 10
6 15
3 5
4 9
3 6

9

Nguồn

USACO 2017 December Contest, Gold — Haybale Feast

Tác giả bài toán: Christopher Chang và Allen Chen.