USACO 2014 - Tháng 3 - Hạng Đồng

\(N\) cô bò của Farmer John (\(1 \le N \le 100\)), được đánh số thuận tiện từ \(1\) đến \(N\), đang đứng thành một hàng. Thứ tự của chúng được mô tả bởi mảng \(A\), trong đó \(A(i)\) là số hiệu của cô bò ở vị trí \(i\). Farmer John muốn sắp xếp lại chúng theo một thứ tự khác để chụp ảnh tập thể; thứ tự này được mô tả bởi mảng \(B\), trong đó \(B(i)\) là số hiệu của cô bò cần đứng ở vị trí \(i\) sau cùng.

Ví dụ, giả sử ban đầu các cô bò đứng theo thứ tự:

A = 5 1 4 2 3

và Farmer John muốn chúng chuyển thành thứ tự:

B = 2 5 3 1 4

Để chuyển từ thứ tự \(A\) sang thứ tự \(B\), các cô bò thực hiện một số phép dịch chuyển "theo chu trình". Mỗi phép dịch chuyển như vậy bắt đầu khi một cô bò đi đến đúng vị trí của mình trong thứ tự \(B\), đẩy cô bò khác ra khỏi vị trí đó; cô bò bị đẩy lại đi đến đúng vị trí của mình và đẩy một cô bò khác, quá trình tiếp tục cho đến khi cuối cùng có một cô bò đi vào vị trí mà cô bò đầu tiên trong chu trình chiếm giữ lúc ban đầu. Chẳng hạn, với cách sắp xếp trên, nếu bắt đầu một chu trình bằng bò \(5\), bò \(5\) sẽ đi đến vị trí \(2\) và đẩy bò \(1\) ra; bò \(1\) đi đến vị trí \(4\) và đẩy bò \(2\) ra; bò \(2\) đi đến vị trí \(1\), khép lại chu trình. Các cô bò tiếp tục thực hiện những phép dịch chuyển theo chu trình cho đến khi tất cả đều ở đúng vị trí trong thứ tự \(B\). Lưu ý rằng mỗi cô bò tham gia đúng một phép dịch chuyển theo chu trình, trừ khi cô đứng cùng một vị trí trong cả hai thứ tự \(A\) và \(B\).

Hãy tính số phép dịch chuyển theo chu trình khác nhau và độ dài của phép dịch chuyển theo chu trình dài nhất khi các cô bò tự sắp xếp lại.

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\) chứa số nguyên \(A(i)\).
• \(N\) dòng cuối, dòng thứ \(i\) chứa số nguyên \(B(i)\).

Ràng buộc

• \(1 \le N \le 100\).

Dữ liệu ra

In ra hai số nguyên cách nhau bởi dấu cách. Số thứ nhất là số phép dịch chuyển theo chu trình, số thứ hai là số cô bò tham gia phép dịch chuyển dài nhất. Nếu không có phép dịch chuyển theo chu trình nào, in ra \(-1\) cho số thứ hai.

Ví dụ

5
5
1
4
2
3
2
5
3
1
4

2 3

Nguồn

USACO 2014 March Contest, Bronze — Reordering the Cows

Tác giả: Brian Dean, 2014.

Đó là một ngày hè nóng nực và cô bò Bessie cảm thấy khá lười biếng. Cô muốn chọn một vị trí trong cánh đồng để có thể tiếp cận nhiều cỏ ngon nhất có thể mà chỉ phải đi một quãng ngắn.

Cánh đồng của Bessie có \(N\) cụm cỏ (\(1 \le N \le 100\,000\)), có thể được xem như một trục số một chiều rất dài. Cụm cỏ thứ \(i\) chứa \(g_i\) đơn vị cỏ (\(1 \le g_i \le 10\,000\)) và nằm tại một điểm \(x_i\) riêng biệt trên cánh đồng (\(0 \le x_i \le 1\,000\,000\)). Bessie muốn chọn một điểm trên cánh đồng làm vị trí ban đầu (điểm này có thể trùng với một cụm cỏ) sao cho lượng cỏ nằm cách vị trí đó không quá \(K\) bước là lớn nhất (\(1 \le K \le 2\,000\,000\)).

Hãy giúp Bessie xác định lượng cỏ lớn nhất mà cô có thể tiếp cận nếu chọn vị trí ban đầu tối ưu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(g_i\) và \(x_i\), mô tả cụm cỏ thứ \(i\).

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(1 \le g_i \le 10\,000\).
• \(0 \le x_i \le 1\,000\,000\) và các giá trị \(x_i\) đôi một khác nhau.
• \(1 \le K \le 2\,000\,000\).

Dữ liệu ra

In ra lượng cỏ lớn nhất nằm trong khoảng cách \(K\) tính từ vị trí tối ưu của Bessie.

Ví dụ

4 3
4 7
10 15
2 2
5 1

11

Nguồn

USACO 2014 March Contest, Bronze — The Lazy Cow

Tác giả: Brian Dean, 2014.

Một sự thật ít người biết về loài bò là chúng bị mù màu đỏ-lục, nghĩa là màu đỏ và màu lục trông giống hệt nhau đối với chúng. Điều này khiến việc thiết kế một tác phẩm nghệ thuật hấp dẫn cả bò lẫn người trở nên đặc biệt khó khăn.

Xét một bức tranh hình vuông được mô tả bởi lưới \(N \times N\) ký tự (\(1 \le N \le 100\)), mỗi ký tự là R (đỏ), G (lục) hoặc B (lam). Một bức tranh thú vị nếu có nhiều "vùng" màu có thể phân biệt với nhau. Hai ký tự thuộc cùng một vùng nếu chúng kề cạnh trực tiếp (ở phía đông, tây, bắc hoặc nam) và có màu không thể phân biệt được. Ví dụ, bức tranh

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

có \(4\) vùng (\(2\) vùng đỏ, \(1\) vùng lam và \(1\) vùng lục) khi một người nhìn vào, nhưng chỉ có \(3\) vùng (\(2\) vùng đỏ-lục và \(1\) vùng lam) khi một cô bò nhìn vào.

Cho một bức tranh, hãy tính số vùng trong bức tranh khi được nhìn bởi một người và bởi một cô bò.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa một chuỗi gồm \(N\) ký tự, mô tả một hàng của bức tranh.

Ràng buộc

• \(1 \le N \le 100\).
• Mỗi ô chứa một trong ba ký tự R, G, B.

Dữ liệu ra

In ra hai số nguyên cách nhau bởi dấu cách, lần lượt là số vùng trong bức tranh khi được nhìn bởi một người và bởi một cô bò.

Ví dụ

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

4 3

Nguồn

USACO 2014 March Contest, Bronze — Cow Art

Tác giả: Brian Dean, 2014.