USACO 2012 - Tháng 12 - 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 2013 - Meet and Greet 100 (p) 4.0s 512M
2 USACO 2013 - Scrambled Letters 100 (p) 4.0s 512M
3 USACO 2013 - Crazy Fences 100 (p) 4.0s 512M

1. USACO 2013 - Meet and Greet

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

Như mọi người đều biết, bò là những sinh vật rất lịch thiệp trong giao tiếp: mỗi khi hai con bò gặp lại nhau sau một khoảng thời gian xa cách, chúng chào nhau bằng một tiếng "moo" thân thiện.

Bò Bessie và cô bạn Elsie đang đi lại trên một con đường dài trong trang trại của Farmer John. Trên thực tế, ta có thể coi con đường này là một trục số một chiều. Bessie và Elsie đều bắt đầu tại gốc tọa độ, sau đó cả hai cùng bắt đầu đi với tốc độ như nhau trong một khoảng thời gian. Cho mô tả các chuyển động của mỗi con bò, hãy xác định số tiếng "moo" được trao đổi.

Bessie và Elsie có thể ngừng di chuyển tại những thời điểm khác nhau, và không con nào di chuyển quá \(1\,000\,000\) đơn vị thời gian.

Dữ liệu vào

  • Dòng 1 chứa hai số nguyên cách nhau bởi dấu cách, \(B\) (\(1 \le B \le 50\,000\)) và \(E\) (\(1 \le E \le 50\,000\)).
  • Các dòng \(2..1+B\): \(B\) dòng này mô tả chuyển động của Bessie. Mỗi dòng chứa một số nguyên dương, theo sau là L hoặc R, biểu thị quãng đường Bessie di chuyển theo hướng trái hoặc phải.
  • Các dòng \(2+B..1+B+E\): \(E\) dòng này mô tả chuyển động của Elsie. Mỗi dòng chứa một số nguyên dương, theo sau là L hoặc R, biểu thị quãng đường Elsie di chuyển theo hướng trái hoặc phải.

Dữ liệu ra

  • Dòng 1 chứa một số nguyên là số tiếng "moo" được hai con bò trao đổi. Việc cả hai cùng bắt đầu tại gốc tọa độ không tạo ra một tiếng "moo".

Ví dụ

Ví dụ 1

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

Bessie đi sang trái trong 3 đơn vị thời gian, sau đó sang phải trong 5 đơn vị thời gian, tiếp theo sang trái trong 1 đơn vị thời gian và cuối cùng sang phải trong 2 đơn vị thời gian; rồi cô đứng yên. Elsie đi sang phải trong 4 đơn vị thời gian, sau đó sang trái trong 4 đơn vị thời gian, tiếp theo sang phải trong 4 đơn vị thời gian và cuối cùng sang trái trong 2 đơn vị thời gian; rồi cô đứng yên.

Bessie và Elsie gặp nhau sau khi tạm thời xa nhau tại thời điểm 7, thời điểm 9 và thời điểm 13.

Nguồn

USACO 2012 December Contest, Bronze — Problem 1: Meet and Greet

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

2. USACO 2013 - Scrambled Letters

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

Farmer John dán trên cửa chuồng một danh sách \(N\) con bò (\(1 \le N \le 50\,000\)) được sắp xếp theo thứ tự bảng chữ cái. Tên mỗi con bò được biểu diễn bằng một chuỗi phân biệt gồm từ 1 đến 20 ký tự chữ thường.

Vốn luôn thích gây rắc rối, bò Bessie thay đổi danh sách bằng cách sắp xếp lại thứ tự các con bò. Ngoài ra, cô còn xáo trộn các chữ cái trong tên của từng con bò. Cho danh sách đã bị thay đổi này, hãy giúp Farmer John tính, đối với mỗi mục trong danh sách, vị trí nhỏ nhất và lớn nhất mà mục đó có thể từng xuất hiện trong danh sách ban đầu.

Dữ liệu vào

  • Dòng 1 chứa một số nguyên duy nhất \(N\).
  • Các dòng \(2..1+N\): mỗi dòng chứa tên đã bị xáo trộn thứ tự các chữ cái của một con bò.

Dữ liệu ra

  • Các dòng \(1..N\): dòng \(i\) cho biết vị trí nhỏ nhất và lớn nhất trong danh sách ban đầu của Farmer John mà phiên bản gốc của chuỗi đầu vào thứ \(i\) có thể từng xuất hiện.

Ví dụ

Ví dụ 1

Input 
4
essieb
a
xzy
elsie
Output 
2 3
1 1
4 4
2 3
Giải thích

Chuỗi "a" luôn xuất hiện đầu tiên trong danh sách của FJ bất kể thế nào, và tương tự, chuỗi "xzy" luôn xuất hiện cuối cùng bất kể các chữ cái của nó ban đầu được sắp xếp ra sao. Hai chuỗi "essieb" và "elsie" đều có thể chiếm vị trí 2 hoặc 3, tùy thuộc vào thứ tự chữ cái ban đầu của chúng (ví dụ, "bessie" ở vị trí 2 và "elsie" ở vị trí 3, so với "sisbee" ở vị trí 3 và "ilees" ở vị trí 2).

Nguồn

USACO 2012 December Contest, Bronze — Problem 2: Scrambled Letters

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

3. USACO 2013 - Crazy Fences

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

Sau khi ghé thăm một bảo tàng nghệ thuật hiện đại, Farmer John quyết định thiết kế lại trang trại bằng cách di chuyển toàn bộ \(N\) (\(1 \le N \le 500\)) hàng rào giữa các đồng cỏ! Mỗi hàng rào được mô tả bởi một đoạn thẳng nằm ngang hoặc thẳng đứng trên mặt phẳng hai chiều. Nếu hai hàng rào gặp nhau thì chúng chỉ gặp tại các đầu mút.

FJ có \(C\) con bò (\(1 \le C \le 500\)) trong trang trại. Mỗi con bò ở tại một điểm trên mặt phẳng hai chiều không nằm trên bất kỳ hàng rào nào, và không có hai con bò nào ở cùng một điểm. Hai con bò được xem là thuộc cùng một cộng đồng nếu một con có thể đi đến con kia mà không chạm vào bất kỳ hàng rào nào. Hãy giúp FJ xác định số lượng bò trong cộng đồng lớn nhất.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên \(N\) và \(C\), cách nhau bởi dấu cách.
  • \(N\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\), mô tả một hàng rào chạy từ điểm \((x_1, y_1)\) đến điểm \((x_2, y_2)\). Mỗi hàng rào hoặc thẳng đứng (\(x_1 = x_2\)) hoặc nằm ngang (\(y_1 = y_2\)). Mọi tọa độ đều nằm trong khoảng từ \(0\) đến \(1\,000\,000\).
  • \(C\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\), mô tả một con bò ở vị trí \((x, y)\). Mọi tọa độ đều nằm trong khoảng từ \(0\) đến \(1\,000\,000\).

Dữ liệu ra

In ra số lượng bò trong cộng đồng lớn nhất.

Ví dụ

Ví dụ 1

Input 
7 3
0 0 10 0
10 0 10 5
12 5 10 5
10 5 1 5
12 5 12 7
0 7 12 7
0 7 0 0
3 4
6 6
17 3
Output 
2
Giải thích

Có \(7\) hàng rào và \(3\) con bò.

Bò số \(1\) và bò số \(2\) cùng thuộc một cộng đồng vì chúng có thể đi đến nhau mà không chạm vào bất kỳ hàng rào nào. Bò số \(3\) không thể đi đến bò số \(1\) hoặc bò số \(2\) mà không băng qua một hàng rào.

Nguồn

USACO 2012 December Contest, Bronze — Problem 3: Crazy Fences

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