USACO 2012 - Tháng 1 - Hạng Đồng

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 USACO 2012 - Gifts 100 (p) 4.0s 512M
2 USACO 2012 - Haybale Stacking 100 (p) 4.0s 512M
3 USACO 2012 - Grazing Patterns 100 (p) 4.0s 512M

1. USACO 2012 - Gifts

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Nông dân John muốn tặng quà cho \(N\) (\(1 \le N \le 1000\)) chú bò của mình với tổng ngân sách \(B\) (\(1 \le B \le 1\,000\,000\,000\)) đơn vị tiền.

Chú bò \(i\) yêu cầu một món quà có giá \(P(i)\) đơn vị và phí vận chuyển \(S(i)\) đơn vị (do đó tổng chi phí để FJ đặt món quà này là \(P(i)+S(i)\)). FJ có một phiếu giảm giá đặc biệt mà ông có thể dùng để đặt một món quà tùy chọn với giá chỉ bằng một nửa giá thông thường. Vì vậy, nếu FJ dùng phiếu giảm giá cho chú bò \(i\), ông chỉ cần trả \(P(i)/2+S(i)\) cho món quà của chú bò đó. Thuận tiện thay, tất cả các giá trị \(P(i)\) đều là số chẵn.

Hãy giúp FJ xác định số lượng bò lớn nhất mà ông có đủ khả năng tặng quà.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên \(N\) và \(B\) cách nhau bởi dấu cách.
  • \(N\) dòng tiếp theo; dòng thứ \(i\) chứa hai số nguyên \(P(i)\) và \(S(i)\) cách nhau bởi dấu cách (\(0 \le P(i),S(i) \le 1\,000\,000\,000\), với \(P(i)\) chẵn).

Dữ liệu ra

  • Dòng đầu tiên chứa số lượng bò lớn nhất mà FJ có thể mua quà cho.

Ví dụ

Ví dụ 1

Input 
5 24
4 2
2 0
8 1
6 3
12 5
Output 
4
Giải thích

Có \(5\) chú bò và ngân sách của FJ là \(24\). Chú bò \(1\) muốn một món quà có giá \(4\) và phí vận chuyển \(2\), v.v.

FJ có thể mua quà cho các chú bò từ \(1\) đến \(4\) nếu dùng phiếu giảm giá cho chú bò \(3\). Tổng chi phí của ông là \((4+2)+(2+0)+(4+1)+(6+3) = 22\). Lưu ý rằng FJ cũng có thể dùng phiếu giảm giá cho chú bò \(1\) hoặc \(4\) mà vẫn không vượt quá ngân sách.

Nguồn

USACO 2012 January Contest, Bronze Division — Gifts

Tác giả đề: Kalki Seksaria và Brian Dean, 2012.

2. USACO 2012 - Haybale Stacking

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cảm thấy có lỗi vì tất cả những trò nghịch ngợm mà mình đã gây ra quanh trang trại gần đây, Bessie đồng ý giúp Nông dân John xếp chồng một lô kiện cỏ khô sắp được chuyển đến.

Ban đầu có \(N\) (\(1 \le N \le 1\,000\,000\), \(N\) lẻ) chồng trống, được đánh số từ \(1\) đến \(N\). Sau đó, FJ đưa cho Bessie một dãy gồm \(K\) chỉ dẫn (\(1 \le K \le 25\,000\)), mỗi chỉ dẫn có dạng A B, nghĩa là Bessie phải thêm một kiện cỏ khô mới lên trên mỗi chồng trong đoạn từ \(A\) đến \(B\). Ví dụ, nếu Bessie nhận được chỉ dẫn 10 13, cô phải thêm một kiện cỏ khô vào từng chồng \(10\), \(11\), \(12\) và \(13\).

Sau khi Bessie xếp các kiện cỏ theo chỉ dẫn của FJ, ông muốn biết chiều cao trung vị của \(N\) chồng — tức là chiều cao của chồng nằm giữa nếu sắp xếp các chồng theo thứ tự chiều cao (thuận tiện thay, \(N\) là số lẻ nên chồng này là duy nhất). Hãy giúp Bessie xác định câu trả lời cho câu hỏi của FJ.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) cách nhau bởi dấu cách.
  • \(K\) dòng tiếp theo, mỗi dòng chứa một chỉ dẫn của FJ dưới dạng hai số nguyên \(A\) và \(B\) cách nhau bởi dấu cách (\(1 \le A \le B \le N\)).

Dữ liệu ra

  • Dòng đầu tiên chứa chiều cao trung vị của một chồng sau khi Bessie hoàn thành các chỉ dẫn.

Ví dụ

Ví dụ 1

Input 
7 4
5 5
2 4
4 6
3 5
Output 
1
Giải thích

Có \(N=7\) chồng và FJ đưa ra \(K=4\) chỉ dẫn. Chỉ dẫn đầu tiên yêu cầu thêm một kiện cỏ khô vào chồng \(5\), chỉ dẫn thứ hai yêu cầu thêm các kiện cỏ khô vào những chồng từ \(2\) đến \(4\), v.v.

Sau khi Bessie hoàn thành, các chồng có chiều cao lần lượt là \(0,1,2,3,3,1,0\). Chiều cao trung vị là \(1\), vì \(1\) là phần tử ở giữa trong thứ tự đã sắp xếp \(0,0,1,1,2,3,3\).

Nguồn

USACO 2012 January Contest, Bronze Division — Haybale Stacking

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

3. USACO 2012 - Grazing Patterns

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Do ngân sách bị cắt giảm gần đây, FJ đã thu hẹp trang trại đến mức khu vực chăn thả cho đàn bò chỉ còn là một cánh đồng hình vuông kích thước \(5\) mét nhân \(5\) mét! Cánh đồng được chia thành một lưới \(5 \times 5\) gồm các ô vuông kích thước \(1\) mét nhân \(1\) mét, trong đó \((1,1)\) là vị trí của ô trên cùng bên trái và \((5,5)\) là vị trí của ô dưới cùng bên phải:

(1,1) (1,2) (1,3) (1,4) (1,5)
(2,1) (2,2) (2,3) (2,4) (2,5)
(3,1) (3,2) (3,3) (3,4) (3,5)
(4,1) (4,2) (4,3) (4,4) (4,5)
(5,1) (5,2) (5,3) (5,4) (5,5)

Mọi ô trong lưới đều có cỏ ngon, ngoại trừ \(K\) ô cằn cỗi (\(0 \le K \le 22\), \(K\) chẵn) không có cỏ. Bò Bessie bắt đầu gặm cỏ tại ô \((1,1)\), ô này luôn có cỏ; bò Mildred bắt đầu gặm cỏ tại ô \((5,5)\), ô này cũng luôn có cỏ.

Cứ mỗi nửa giờ, Bessie và Mildred ăn hết toàn bộ cỏ trong ô tương ứng của mình, rồi mỗi cô di chuyển đến một ô có cỏ kề cạnh (phía bắc, nam, đông hoặc tây). Họ muốn ăn hết tất cả các ô có cỏ và kết thúc tại chính xác cùng một vị trí cuối cùng. Hãy tính số cách khác nhau để điều này xảy ra. Bessie và Mildred luôn di chuyển vào các ô có cỏ, và họ không bao giờ cùng di chuyển vào một ô, trừ khi đó là ô có cỏ cuối cùng còn lại.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên \(K\).
  • \(K\) dòng tiếp theo, mỗi dòng chứa vị trí \((i,j)\) của một ô không có cỏ dưới dạng hai số nguyên \(i\) và \(j\) cách nhau bởi dấu cách.

Dữ liệu ra

  • Dòng đầu tiên chứa số cách khác nhau mà Bessie và Mildred có thể đi qua cánh đồng để ăn hết cỏ và kết thúc tại cùng một vị trí cuối cùng.

Ví dụ

Ví dụ 1

Input 
4
3 2
3 3
3 4
3 1
Output 
1
Giải thích

Lưới ban đầu trông như sau (trong đó . biểu diễn một ô có cỏ, x biểu diễn một ô không có cỏ, b chỉ vị trí bắt đầu của Bessie và m chỉ vị trí bắt đầu của Mildred):

b  .  .  .  .

.  .  .  .  .

x  x  x  x  .

.  .  .  .  .

.  .  .  .  m

Chỉ có một phương án duy nhất, trong đó Bessie và Mildred gặp nhau tại ô \((3,5)\):

b  b--b  b--b
|  |  |  |  |
b--b  b--b  b
            |
x  x  x  x b/m
            |
m--m--m--m--m
|
m--m--m--m--m

Nguồn

USACO 2012 January Contest, Bronze Division — Grazing Patterns

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