USACO 2012 - Tháng 2 - Hạng Vàng

Farmer John cần những con bò mới! Có \(N\) con bò đang được rao bán (\(1 \leq N \leq 50\,000\)), và FJ không được chi quá ngân sách \(M\) đơn vị tiền (\(1 \leq M \leq 10^{14}\)). Bò \(i\) có giá \(P_i\) (\(1 \leq P_i \leq 10^9\)), nhưng FJ có \(K\) phiếu giảm giá (\(1 \leq K \leq N\)); khi dùng một phiếu cho bò \(i\), thay vào đó ông chỉ phải trả \(C_i\) (\(1 \leq C_i \leq P_i\)). Dĩ nhiên, FJ chỉ có thể dùng một phiếu giảm giá cho mỗi con bò.

Số bò lớn nhất mà FJ có đủ khả năng mua là bao nhiêu?

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên cách nhau bởi dấu cách: \(N\), \(K\) và \(M\).
• \(N\) dòng tiếp theo: dòng thứ \(i+1\) chứa hai số nguyên \(P_i\) và \(C_i\).

Dữ liệu ra

In ra một số nguyên duy nhất là số bò lớn nhất mà FJ có đủ khả năng mua.

Ví dụ

4 1 7
3 2
2 2
8 1
4 3

3

Nguồn

USACO 2012 February Contest, Gold Division — Cow Coupons. Tác giả đề: Neal Wu và Mark Gordon (2012).

https://usaco.org/index.php?page=viewproblem2&cpid=118

Sau khi tham gia một lớp nghệ thuật hiện đại, Farmer John bắt đầu thích thú với việc tìm kiếm các mẫu hình học trong mọi thứ xung quanh trang trại. Ông cẩn thận đánh dấu vị trí của \(N\) con bò (\(2 \leq N \leq 1000\)), mỗi con nằm tại một điểm phân biệt trên mặt phẳng hai chiều, rồi tự hỏi tập điểm này có bao nhiêu trục đối xứng khác nhau. Dĩ nhiên, một trục đối xứng là một đường thẳng mà qua đó, các điểm ở hai phía là ảnh phản chiếu của nhau.

Hãy giúp FJ trả lời câu hỏi hình học vô cùng cấp thiết này.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo: dòng thứ \(i+1\) chứa hai số nguyên cách nhau bởi dấu cách, biểu diễn tọa độ \(x\) và \(y\) của con bò thứ \(i\) (\(-10\,000 \leq x, y \leq 10\,000\)).

Dữ liệu ra

In ra số trục đối xứng khác nhau của tập điểm.

Ví dụ

4
0 0
0 1
1 0
1 1

4

Nguồn

USACO 2012 February Contest, Gold Division — Symmetry. Tác giả đề: Brian Dean (2012).

https://usaco.org/index.php?page=viewproblem2&cpid=119

Farmer John nhận thấy đàn bò của mình thường di chuyển giữa các cánh đồng gần nhau. Vì vậy, ông muốn trồng đủ cỏ trên mỗi cánh đồng không chỉ cho những con bò ban đầu ở đó, mà còn cho cả những con bò ghé sang từ các cánh đồng lân cận.

Cụ thể, trang trại của FJ gồm \(N\) cánh đồng (\(1 \leq N \leq 100\,000\)), trong đó một số cặp cánh đồng được nối với nhau bằng các đường mòn hai chiều (tổng cộng có \(N-1\) đường mòn). FJ đã thiết kế trang trại sao cho giữa hai cánh đồng bất kỳ \(i\) và \(j\) có đúng một đường đi gồm các đường mòn nối \(i\) với \(j\). Cánh đồng \(i\) là nơi ở của \(C(i)\) con bò, mặc dù đôi khi bò di chuyển sang một cánh đồng khác bằng cách đi qua không quá \(K\) đường mòn (\(1 \leq K \leq 20\)).

FJ muốn trồng đủ cỏ trên mỗi cánh đồng \(i\) để nuôi được số bò lớn nhất \(M(i)\) có thể xuất hiện tại đó, tức là số bò có khả năng đi tới cánh đồng \(i\) bằng cách đi qua nhiều nhất \(K\) đường mòn. Cho cấu trúc trang trại của FJ và giá trị \(C(i)\) của mỗi cánh đồng \(i\), hãy giúp FJ tính \(M(i)\) cho mọi cánh đồng \(i\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách, \(N\) và \(K\).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(i\) và \(j\) (\(1 \leq i, j \leq N\)), cho biết cánh đồng \(i\) và cánh đồng \(j\) được nối trực tiếp bởi một đường mòn.
• \(N\) dòng cuối: dòng thứ \(N+i\) chứa số nguyên \(C(i)\) (\(0 \leq C(i) \leq 1000\)).

Dữ liệu ra

Với mỗi \(i\) từ \(1\) đến \(N\), dòng thứ \(i\) chứa giá trị \(M(i)\).

Ví dụ

6 2
5 1
3 6
2 4
2 1
3 2
1
2
3
4
5
6

15
21
16
10
8
11

Nguồn

USACO 2012 February Contest, Gold Division — Nearby Cows. Tác giả đề: Neal Wu và Eric Price (2011).

https://usaco.org/index.php?page=viewproblem2&cpid=120