USACO 2012 - US Open - Hạng Đồng

Farmer John xếp \(N\) con bò (\(1 \le N \le 1000\)) thành một hàng. Mỗi con bò được nhận diện bằng một số nguyên gọi là "mã giống"; mã giống của con bò thứ \(i\) trong hàng là \(B(i)\).

FJ cho rằng hàng bò của mình sẽ trông ấn tượng hơn nhiều nếu có một đoạn liên tiếp dài gồm toàn những con bò có cùng mã giống. Để tạo ra một đoạn như vậy, FJ quyết định loại khỏi hàng tất cả những con bò mang một mã giống do ông chọn. Hãy giúp FJ tìm độ dài của đoạn liên tiếp lớn nhất gồm những con bò có cùng mã giống mà ông có thể tạo ra bằng cách loại bỏ tất cả những con bò mang một mã giống nào đó do mình chọn.

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\).
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa \(B(i)\), là một số nguyên trong khoảng từ 0 đến \(1\,000\,000\).

Dữ liệu ra

• Dòng 1 chứa kích thước lớn nhất của một đoạn liên tiếp gồm những con bò có mã giống giống hệt nhau mà FJ có thể tạo ra.

Ví dụ

9
2
7
3
7
7
3
7
5
7

4

Nguồn

USACO 2012 US Open, Bronze Division — Cows in a Row

Tác giả: Brian Dean, 2012.

Farmer John muốn giám sát \(N\) con bò của mình (\(1 \le N \le 50\,000\)) bằng một hệ thống giám sát mới mua.

Con bò thứ \(i\) nằm tại vị trí \((x_i, y_i)\) với tọa độ nguyên (trong khoảng từ 0 đến \(1\,000\,000\,000\)); không có hai con bò nào ở cùng một vị trí. Hệ thống giám sát của FJ gồm ba camera đặc biệt, mỗi camera có khả năng quan sát tất cả những con bò nằm trên một đường thẳng đứng hoặc một đường nằm ngang. Hãy xác định liệu FJ có thể bố trí ba camera này để giám sát tất cả \(N\) con bò hay không. Nói cách khác, hãy xác định liệu toàn bộ \(N\) vị trí của đàn bò có thể đồng thời được "phủ" bởi một tập hợp gồm ba đường thẳng, mỗi đường có phương nằm ngang hoặc thẳng đứng hay không.

Lưu ý: Những chương trình không làm gì ngoài việc đoán ngẫu nhiên dữ liệu ra có thể bị loại và nhận số điểm bằng không.

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\).
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa hai số nguyên \(x_i\) và \(y_i\), cách nhau bởi dấu cách, cho biết vị trí của con bò \(i\).

Dữ liệu ra

• Dòng 1: In ra 1 nếu có thể giám sát tất cả \(N\) con bò bằng ba camera; nếu không, in ra 0.

Ví dụ

6
1 7
0 0
1 2
2 0
1 4
3 4

1

Nguồn

USACO 2012 US Open, Bronze Division — Three Lines

Tác giả: Brian Dean, 2012.

Mỗi khi trời mưa, cánh đồng của Farmer John luôn bị ngập. Tuy nhiên, vì cánh đồng không hoàn toàn bằng phẳng nên nước dâng không đồng đều, để lại một số "hòn đảo" bị ngăn cách bởi những vùng nước rộng.

Cánh đồng của FJ được mô tả như một địa hình một chiều gồm \(N\) giá trị độ cao liên tiếp \(H(1) \ldots H(n)\) (\(1 \le N \le 100\,000\)). Giả sử địa hình được bao quanh bởi những hàng rào cao gần như vô hạn, hãy xét diễn biến khi có một trận mưa: những vùng thấp nhất bị nước phủ trước, tạo ra một số "hòn đảo" rời nhau; cuối cùng, tất cả chúng đều bị ngập khi mực nước tiếp tục dâng. Ngay khi mực nước bằng độ cao của một phần đất, phần đất đó được coi là đã ở dưới nước.

Hình trên minh họa một ví dụ: ở bên trái, lượng nước vừa vượt quá 1 đơn vị, để lại 4 hòn đảo (số lượng lớn nhất từng xuất hiện). Sau đó, khi tổng lượng nước đã dâng thêm là 7 đơn vị, ta có hình bên phải với chỉ hai hòn đảo còn nhô lên. Hãy tính số hòn đảo lớn nhất có thể xuất hiện tại cùng một thời điểm trong trận mưa, khi mực nước dâng cho đến lúc toàn bộ cánh đồng chìm dưới nước.

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\).
• Các dòng từ 2 đến \(1+N\): Dòng \(i+1\) chứa độ cao \(H(i)\) (\(1 \le H(i) \le 1\,000\,000\,000\)).

Dữ liệu ra

• Dòng 1 chứa một số nguyên duy nhất cho biết số hòn đảo lớn nhất xuất hiện tại bất kỳ một thời điểm nào trong suốt trận mưa.

Ví dụ

8
3
5
2
3
1
4
2
3

4

Nguồn

USACO 2012 US Open, Bronze Division — Islands

Tác giả: Brian Dean, 2012.

Một sự thật ít người biết về loài bò là chúng rất thích giải đố! Nhân dịp sinh nhật Bessie, Farmer John tặng cô một câu đố cơ khí thú vị để giải. Câu đố gồm ba vật thể rắn, mỗi vật thể được tạo thành từ các ô vuông đơn vị \(1 \times 1\) dán với nhau. Mỗi vật thể là một hình "liên thông", theo nghĩa là ta có thể đi từ một ô vuông bất kỳ của vật thể đến bất kỳ ô vuông nào khác trên cùng vật thể bằng cách bước qua các ô thuộc vật thể theo hướng bắc, nam, đông hoặc tây.

Một vật thể có thể được di chuyển bằng cách trượt nó lặp đi lặp lại một đơn vị về phía bắc, nam, đông hoặc tây. Mục tiêu của câu đố là di chuyển các vật thể sao cho chúng tách rời nhau, tức là các hình chữ nhật bao của chúng không giao nhau. Với hình dạng và vị trí của ba vật thể, nhiệm vụ của bạn là giúp Bessie xác định liệu có thể tách chúng ra hay không. Một cấu hình không thể tách rời được gọi là bị khóa.

Lưu ý: Những chương trình không làm gì ngoài việc đoán ngẫu nhiên dữ liệu ra có thể bị loại và nhận số điểm bằng không.

Dữ liệu vào

• Dòng 1 chứa ba số nguyên \(N1\), \(N2\) và \(N3\), cách nhau bởi dấu cách, lần lượt mô tả số ô vuông đơn vị tạo nên vật thể 1, 2 và 3.
• Các dòng từ 2 đến \(1+N1\): Mỗi dòng mô tả vị trí \((x,y)\) của góc tây nam của một ô vuông thuộc vật thể 1. Mọi tọa độ đều nằm trong khoảng từ 0 đến 9.
• Các dòng từ \(2+N1\) đến \(1+N1+N2\): Mỗi dòng mô tả vị trí \((x,y)\) của góc tây nam của một ô vuông thuộc vật thể 2. Mọi tọa độ đều nằm trong khoảng từ 0 đến 9.
• Các dòng từ \(2+N1+N2\) đến \(1+N1+N2+N3\): Mỗi dòng mô tả vị trí \((x,y)\) của góc tây nam của một ô vuông thuộc vật thể 3. Mọi tọa độ đều nằm trong khoảng từ 0 đến 9.

Dữ liệu ra

• Dòng 1: In ra 1 nếu có thể tách các vật thể khỏi nhau, hoặc 0 nếu chúng bị khóa.

Ví dụ

12 3 5
0 0
1 0
2 0
3 0
3 1
0 1
0 2
0 3
0 4
1 4
2 4
3 4
2 1
2 2
1 2
2 3
3 3
4 3
4 4
4 2

1

Nguồn

USACO 2012 US Open, Bronze Division — Unlocking Blocks

Tác giả: Brian Dean, 2012.