USACO 2013 - Tháng 11 - 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 2014 - Combination Lock 100 (p) 4.0s 512M
2 USACO 2014 - Goldilocks and the N Cows 100 (p) 4.0s 512M
3 USACO 2014 - Farmer John has no Large Brown Cow 100 (p) 4.0s 512M

1. USACO 2014 - Combination Lock

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

Những chú bò của Farmer John liên tục trốn khỏi trang trại và gây rắc rối. Để ngăn chúng rời đi, ông mua một chiếc khóa số hiện đại nhằm không cho chúng mở cổng đồng cỏ.

Biết rằng những chú bò của mình khá thông minh, Farmer John muốn đảm bảo chúng không thể dễ dàng mở khóa chỉ bằng cách thử nhiều tổ hợp khác nhau. Khóa có ba vòng số, mỗi vòng được đánh số từ \(1..N\) (\(1 \le N \le 100\)); vì các vòng số có dạng tròn nên \(1\) và \(N\) nằm kề nhau. Có hai tổ hợp có thể mở khóa: một tổ hợp do Farmer John đặt và một tổ hợp "chủ" do nhà sản xuất khóa đặt. Tuy nhiên, khóa có một sai số nhỏ, vì vậy nó vẫn mở nếu số trên mỗi vòng cách số tương ứng của một tổ hợp hợp lệ không quá 2 vị trí. Ví dụ, nếu tổ hợp của Farmer John là \((1,2,3)\) và tổ hợp chủ là \((4,5,6)\), khóa sẽ mở khi các vòng số được đặt thành \((1,N,5)\) (vì tổ hợp này đủ gần tổ hợp của Farmer John) hoặc \((2,4,8)\) (vì tổ hợp này đủ gần tổ hợp chủ). Lưu ý rằng \((1,5,6)\) sẽ không mở được khóa vì nó không đủ gần với riêng bất kỳ một tổ hợp nào.

Cho tổ hợp của Farmer John và tổ hợp chủ, hãy xác định số cách đặt ba vòng số khác nhau có thể mở khóa. Thứ tự có ý nghĩa, vì vậy cách đặt \((1,2,3)\) khác với \((3,2,1)\).

Dữ liệu vào

  • Dòng 1 chứa số nguyên \(N\).
  • Dòng 2 chứa ba số nguyên cách nhau bởi dấu cách, mô tả tổ hợp của Farmer John.
  • Dòng 3 chứa ba số nguyên cách nhau bởi dấu cách, mô tả tổ hợp chủ (có thể trùng với tổ hợp của Farmer John).

Dữ liệu ra

  • Dòng 1 chứa số cách đặt các vòng số khác nhau có thể mở khóa.

Ví dụ

Ví dụ 1

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

Mỗi vòng số được đánh số từ \(1..50\). Tổ hợp của Farmer John là \((1,2,3)\) và tổ hợp chủ là \((5,6,7)\).

Nguồn

USACO 2013 November Contest, Bronze — Problem 1: Combination Lock

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

2. USACO 2014 - Goldilocks and the N Cows

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

Có lẽ bạn đã nghe câu chuyện kinh điển về Goldilocks và ba chú gấu. Tuy nhiên, ít ai biết rằng sau này Goldilocks đã chọn nghề nông. Trong trang trại của cô có một chuồng chứa \(N\) con bò (\(1 \le N \le 20\,000\)). Thật không may, những con bò của cô khá nhạy cảm với nhiệt độ.

Mỗi con bò \(i\) chỉ định một khoảng nhiệt độ \(A(i)..B(i)\) mà nó cảm thấy "vừa phải" (\(0 \le A(i) \le B(i) \le 1\,000\,000\,000\)). Nếu Goldilocks đặt bộ điều nhiệt trong chuồng ở nhiệt độ \(T < A(i)\), con bò sẽ quá lạnh và sản xuất \(X\) đơn vị sữa. Nếu cô đặt bộ điều nhiệt ở nhiệt độ \(T\) nằm trong khoảng này (\(A(i) \le T \le B(i)\)), con bò sẽ cảm thấy dễ chịu và sản xuất \(Y\) đơn vị sữa. Nếu cô đặt bộ điều nhiệt ở nhiệt độ \(T > B(i)\), con bò sẽ quá nóng và sản xuất \(Z\) đơn vị sữa. Đúng như dự đoán, \(Y\) luôn lớn hơn cả \(X\) và \(Z\).

Cho \(X\), \(Y\), \(Z\) cùng khoảng nhiệt độ ưa thích của mỗi con bò, hãy tính lượng sữa lớn nhất Goldilocks có thể thu được nếu cô cài đặt bộ điều nhiệt trong chuồng một cách tối ưu. Các giá trị \(X\), \(Y\) và \(Z\) là những số nguyên trong khoảng \(0..1000\), và bộ điều nhiệt có thể được đặt ở bất kỳ giá trị nguyên nào.

Dữ liệu vào

  • Dòng 1 chứa bốn số nguyên cách nhau bởi dấu cách: \(N\), \(X\), \(Y\), \(Z\).
  • Các dòng \(2..1+N\): dòng \(1+i\) chứa hai số nguyên cách nhau bởi dấu cách là \(A(i)\) và \(B(i)\).

Dữ liệu ra

  • Dòng 1 chứa lượng sữa lớn nhất Goldilocks có thể thu được khi đặt nhiệt độ trong chuồng một cách tối ưu.

Phân nhóm

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

  • Các test \(1..4\) có \(B(i) \le 100\) với mọi con bò.
  • Các test \(1..6\) có \(N \le 1000\).

Ví dụ

Ví dụ 1

Input 
4 7 9 6
5 8
3 4
13 20
7 10
Output 
31
Giải thích

Có 4 con bò trong chuồng, với các khoảng nhiệt độ lần lượt là \(5..8\), \(3..4\), \(13..20\) và \(7..10\). Một con bò bị lạnh sản xuất 7 đơn vị sữa, một con bò cảm thấy dễ chịu sản xuất 9 đơn vị sữa, còn một con bò bị nóng sản xuất 6 đơn vị sữa.

Nếu Goldilocks đặt bộ điều nhiệt ở 7 hoặc 8 thì bò số 1 và bò số 4 sẽ cảm thấy dễ chịu, bò số 2 quá nóng và bò số 3 quá lạnh. Tổng lượng sữa thu được là 31 đơn vị.

Nguồn

USACO 2013 November Contest, Bronze — Problem 2: Goldilocks and the N Cows

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

3. 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.