USACO 2013 - Tháng 11 - Hạng Bạc - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	USACO 2014 - Farmer John has no Large Brown Cow	100 (p)	4.0s	512M
2	USACO 2014 - Crowded Cows	100 (p)	4.0s	512M
3	USACO 2014 - Pogo-Cow	100 (p)	4.0s	512M

1. USACO 2014 - Farmer John has no Large Brown Cow

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

Farmer John thích sưu tầm càng nhiều giống bò khác nhau càng tốt. Trên thực tế, ông đã sưu tầm gần như mọi giống bò có thể hình dung được, chỉ trừ một vài giống được ghi trong một danh sách ngắn gồm \(N\) dòng (\(1 \le N \le 100\)). Danh sách trông như sau:

Farmer John has no large brown noisy cow.
Farmer John has no small white silent cow.
Farmer John has no large spotted noisy cow.

Mỗi mục trong danh sách mô tả một con bò còn thiếu bằng một danh sách ngắn các tính từ, và mọi mục đều có cùng số lượng tính từ (trong ví dụ này là 3). Số tính từ trên mỗi dòng nằm trong khoảng \(2..30\).

Farmer John có một con bò ứng với mọi tổ hợp tính từ khả dĩ khác không xuất hiện trong danh sách. Trong ví dụ này, tính từ thứ nhất có thể là large hoặc small, tính từ thứ hai có thể là brown, white hoặc spotted, và tính từ thứ ba có thể là noisy hoặc silent. Như vậy có \(2 \times 3 \times 2 = 12\) tổ hợp khác nhau, và Farmer John có một con bò ứng với mỗi tổ hợp, ngoại trừ những tổ hợp được nêu cụ thể trong danh sách. Trong ví dụ này, một con bò large white noisy là một trong 9 con bò của ông. Farmer John chắc chắn rằng mình có nhiều nhất \(1\,000\,000\,000\) con bò.

Nếu Farmer John liệt kê những con bò của mình theo thứ tự từ điển, con bò thứ \(K\) trong danh sách này là con nào?

Dữ liệu vào

Dòng 1 chứa hai số nguyên \(N\) và \(K\).
Các dòng \(2..1+N\): mỗi dòng là một câu có dạng Farmer John has no large spotted noisy cow.. Mỗi tính từ trong câu là một xâu gồm nhiều nhất 10 chữ cái thường. Bạn biết câu đã kết thúc khi gặp xâu cow. có dấu chấm ở cuối.

Dữ liệu ra

Dòng 1 chứa mô tả của con bò thứ \(K\) trong trang trại.

Phân nhóm

Trong 10 test của bài toán này:

Các test \(2..4\) có nhiều nhất hai tính từ trên mỗi dòng trong danh sách của Farmer John.
Các test \(2..6\) có đúng hai giá trị khả dĩ cho mỗi tính từ. Trong tất cả các test còn lại, mỗi tính từ có từ 1 đến \(N\) giá trị khả dĩ.

Ví dụ

Ví dụ 1

Input

3 7
Farmer John has no large brown noisy cow.
Farmer John has no small white silent cow.
Farmer John has no large spotted noisy cow.

Output

small spotted noisy

Giải thích

Dữ liệu vào đúng với ví dụ đã nêu trong đề bài. Farmer John muốn biết con bò thứ 7 trong trang trại khi các con bò được liệt kê theo thứ tự từ điển.

Farmer John có những con bò ứng với các mô tả sau, được liệt kê theo thứ tự từ điển:

large brown silent
large spotted silent
large white noisy
large white silent
small brown noisy
small brown silent
small spotted noisy
small spotted silent
small white noisy

Con bò thứ 7 trong danh sách này được mô tả là small spotted noisy.

Nguồn

USACO 2013 November Contest, Silver — Problem 1: Farmer John has no Large Brown Cow

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

2. USACO 2014 - Crowded Cows

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

\(N\) con bò của Farmer John (\(1 \le N \le 50\,000\)) đang gặm cỏ dọc theo một hàng rào một chiều. Con bò \(i\) đứng tại vị trí \(x(i)\) và có chiều cao \(h(i)\) (\(1 \le x(i), h(i) \le 1\,000\,000\,000\)).

Một con bò cảm thấy "chật chội" nếu ở bên trái nó, trong khoảng cách \(D\), có một con bò khác cao ít nhất gấp đôi nó, đồng thời ở bên phải nó, trong khoảng cách \(D\), cũng có một con bò khác cao ít nhất gấp đôi nó (\(1 \le D \le 1\,000\,000\,000\)). Vì những con bò cảm thấy chật chội sản xuất ít sữa hơn, Farmer John muốn đếm số bò như vậy. Hãy giúp ông.

Dữ liệu vào

Dòng 1 chứa hai số nguyên \(N\) và \(D\).
Các dòng \(2..1+N\): dòng \(i+1\) chứa hai số nguyên \(x(i)\) và \(h(i)\). Vị trí của tất cả \(N\) con bò đôi một khác nhau.

Dữ liệu ra

Dòng 1 chứa số con bò cảm thấy chật chội.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Có 6 con bò và ngưỡng khoảng cách để cảm thấy chật chội là 4. Bò số 1 ở vị trí \(x=10\) và có chiều cao \(h=3\), các con bò còn lại được mô tả tương tự.

Hai con bò tại các vị trí \(x=5\) và \(x=6\) đều cảm thấy chật chội.

Nguồn

USACO 2013 November Contest, Silver — Problem 2: Crowded Cows

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

3. USACO 2014 - Pogo-Cow

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

Trong một nỗ lực thiếu suy tính nhằm tăng khả năng di chuyển của cô bò cưng Bessie, Farmer John đã gắn một chiếc cà kheo lò xo vào mỗi chân của Bessie. Giờ đây Bessie có thể nhảy rất nhanh khắp trang trại, nhưng cô vẫn chưa học được cách giảm tốc.

Để giúp Bessie luyện tập khả năng kiểm soát bước nhảy tốt hơn, Farmer John dựng một đường tập dọc theo một lối đi thẳng một chiều qua trang trại. Tại nhiều vị trí đôi một khác nhau trên lối đi, ông đặt \(N\) mục tiêu để Bessie cố gắng đáp xuống (\(1 \le N \le 1000\)). Mục tiêu \(i\) nằm tại vị trí \(x(i)\) và có giá trị \(p(i)\) điểm nếu Bessie đáp xuống đó. Bessie bắt đầu tại vị trí của bất kỳ mục tiêu nào do cô chọn và chỉ được di chuyển theo một hướng, nhảy từ mục tiêu này sang mục tiêu khác. Mỗi bước nhảy phải dài ít nhất bằng bước nhảy trước đó và phải đáp xuống một mục tiêu.

Bessie nhận được điểm của mọi mục tiêu mà cô chạm vào (bao gồm mục tiêu ban đầu nơi cô xuất phát). Hãy tính tổng điểm lớn nhất cô có thể đạt được.

Dữ liệu vào

Dòng 1 chứa số nguyên \(N\).
Các dòng \(2..1+N\): dòng \(i+1\) chứa \(x(i)\) và \(p(i)\), mỗi giá trị là một số nguyên trong khoảng \(0..1\,000\,000\).

Dữ liệu ra

Dòng 1 chứa tổng điểm lớn nhất Bessie có thể nhận được.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Có 6 mục tiêu. Mục tiêu thứ nhất ở vị trí \(x=5\) và có giá trị 6 điểm, các mục tiêu còn lại được mô tả tương tự.

Bessie nhảy từ vị trí \(x=4\) (8 điểm) đến vị trí \(x=5\) (6 điểm), rồi đến vị trí \(x=7\) (6 điểm) và cuối cùng đến vị trí \(x=10\) (5 điểm).

Nguồn

USACO 2013 November Contest, Silver — Problem 3: Pogo-Cow

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