USACO 2016 - Tháng 1 - Hạng Bạch Kim

Bessie đang xây một pháo đài cùng cô bạn Elsie. Giống như mọi pháo đài tốt, nó cần bắt đầu bằng một bộ khung chắc chắn. Bessie muốn dựng một bộ khung có dạng đường viền hình chữ nhật rộng một mét, rồi xây pháo đài lên trên đó.

Bessie đã chọn sẵn địa điểm xây pháo đài: một mảnh đất kích thước \(N\) mét nhân \(M\) mét (\(1\le N,M\le200\)). Đáng tiếc, địa điểm này có một số vùng đầm lầy không thể dùng để đỡ bộ khung. Hãy giúp Bessie xác định diện tích lớn nhất mà pháo đài có thể bao phủ (diện tích hình chữ nhật được bộ khung nâng đỡ), sao cho bộ khung không nằm trên bất kỳ vùng đầm lầy nào.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).

\(N\) dòng tiếp theo, mỗi dòng chứa \(M\) ký tự, tạo thành một lưới mô tả địa điểm. Ký tự . biểu thị cỏ bình thường, còn X biểu thị một ô đầm lầy.

Dữ liệu ra

In một số nguyên biểu thị diện tích lớn nhất mà pháo đài của Bessie có thể bao phủ.

Ví dụ

5 6
......
..X..X
X..X..
......
..X...

16

.ffff.
.fX.fX
Xf.Xf.
.ffff.
..X...

Nguồn

USACO 2016 January Contest, Platinum - Fort Moo: https://usaco.org/index.php?page=viewproblem2&cpid=600

Tác giả: Nathan Pinsker.

Farmer John khá đáng tin cậy trong mọi khía cạnh quản lý trang trại, ngoại trừ một điều: ông cực kỳ tệ trong việc cắt cỏ đúng lúc. Thực tế, mỗi ngày ông chỉ xoay xở di chuyển được máy cắt cỏ một lần. Vào ngày 1, ông bắt đầu tại vị trí \((x_1,y_1)\); vào ngày \(d\), ông cắt cỏ dọc theo một đoạn thẳng đến vị trí \((x_d,y_d)\), di chuyển theo chiều ngang hoặc chiều dọc trên bản đồ hai chiều của trang trại; nghĩa là \(x_d=x_{d-1}\) hoặc \(y_d=y_{d-1}\). FJ luân phiên giữa chuyển động ngang và dọc trong những ngày liên tiếp.

FJ tiến triển chậm đến mức một phần cỏ ông đã cắt có thể mọc lại trước khi ông hoàn tất toàn bộ công việc. Bất kỳ phần cỏ nào được cắt vào ngày \(d\) sẽ mọc lại vào ngày \(d+T\), nên nếu đường cắt của FJ giao với một đường ông đã cắt ít nhất \(T\) ngày trước, ông sẽ cắt cỏ tại cùng một điểm thêm lần nữa. Trong nỗ lực sửa đổi chiến lược cắt cỏ tồi tệ của mình, FJ muốn đếm số lần điều này xảy ra.

Hãy đếm số lần đường cắt của FJ giao với một đoạn trước đó mà cỏ trên đó đã mọc lại. Bạn chỉ được tính các giao điểm "vuông góc", được định nghĩa là điểm chung của một đoạn ngang và một đoạn dọc nhưng không phải đầu mút của bất kỳ đoạn nào trong hai đoạn.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(2\le N\le100\,000\)) và \(T\) (\(1\le T\le N\), \(T\) chẵn).

\(N\) dòng tiếp theo mô tả vị trí của máy cắt cỏ vào các ngày \(1\ldots N\). Dòng thứ \(i\) trong số này chứa hai số nguyên \(x_i\) và \(y_i\) (các số nguyên không âm, mỗi số không vượt quá \(1\,000\,000\,000\)).

Dữ liệu ra

In số giao điểm được mô tả ở trên, nơi FJ cắt lại một điểm cỏ đã mọc lại sau lần cắt trước.

Ví dụ

7 4
0 10
10 10
10 5
3 5
3 12
6 12
6 3

1

Lưu ý: Bài này có giới hạn được mở rộng: 5 giây cho mỗi trường hợp kiểm thử (10 giây đối với Python và Java) và 512 MB bộ nhớ.

Nguồn

USACO 2016 January Contest, Platinum - Mowing the Field: https://usaco.org/index.php?page=viewproblem2&cpid=601

Tác giả: Chad Waters và Brian Dean.

Farmer John đã lắp một chiếc máy vắt sữa hiện đại mới trong chuồng, nhưng nó tiêu thụ nhiều điện đến mức thỉnh thoảng làm mất điện! Việc này xảy ra thường xuyên đến nỗi Bessie đã ghi nhớ bản đồ chuồng, giúp cô dễ tìm lối ra hơn trong bóng tối. Tuy nhiên, cô tò mò về ảnh hưởng của việc mất điện đến khả năng nhanh chóng thoát khỏi chuồng. Chẳng hạn, cô muốn biết mình có thể phải đi xa hơn bao nhiêu để tìm được lối ra trong bóng tối.

Chuồng được mô tả bởi một đa giác đơn (không tự cắt) có các đỉnh nguyên \((x_1,y_1)\ldots(x_n,y_n)\) được liệt kê theo chiều kim đồng hồ. Các cạnh luân phiên nằm ngang (song song với trục \(x\)) và thẳng đứng (song song với trục \(y\)); cạnh đầu tiên có thể thuộc một trong hai loại. Lối ra nằm tại \((x_1,y_1)\). Bessie bắt đầu ở bên trong chuồng tại một đỉnh nào đó \((x_i,y_i)\) với \(i>1\). Cô chỉ có thể đi quanh chu vi chuồng theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ và có thể đổi hướng mỗi khi đến một đỉnh. Mục tiêu của cô là đi quãng đường ngắn nhất để đến lối ra. Khi đèn sáng, điều này tất nhiên khá dễ: từ vị trí hiện tại, cô sẽ đi đến lối ra theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, tùy hướng nào ngắn hơn.

Một ngày nọ, đèn tắt khiến Bessie hoảng sợ và quên mất mình đang đứng ở đỉnh nào. May thay, cô vẫn nhớ chính xác bản đồ chuồng, nên có thể xác định vị trí bằng cách đi quanh chuồng và dùng xúc giác. Mỗi khi đứng tại một đỉnh (kể cả đỉnh ban đầu), cô có thể cảm nhận đó là một chỗ rẽ trái hay rẽ phải và biết được đỉnh ấy có phải lối ra hay không. Khi đi dọc một cạnh của chuồng, sau khi đi hết cạnh đó cô có thể xác định chính xác độ dài của nó. Nói chung, Bessie sẽ dùng một chiến lược để dò đường quanh đỉnh xuất phát cho đến khi có đủ thông tin để xác định mình đang ở đâu. Khi đó, cô có thể dễ dàng tìm đường đến lối ra với quãng đường còn lại nhỏ nhất.

Hãy giúp Bessie xác định mức tăng nhỏ nhất có thể của quãng đường cô phải đi trong trường hợp xấu nhất (xét mọi đỉnh xuất phát có thể) khi đi trong bóng tối so với khi chuồng được chiếu sáng, với giả định cô di chuyển theo một chiến lược tối ưu trong mỗi trường hợp. Một chiến lược "tối ưu" cho trường hợp không có ánh sáng là chiến lược làm nhỏ nhất mức tăng trong trường hợp xấu nhất này.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(4\le N\le200\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên mô tả các điểm \((x_i,y_i)\) theo thứ tự chiều kim đồng hồ quanh chuồng. Các số nguyên này nằm trong khoảng \(-100\,000\ldots100\,000\).

Dữ liệu ra

In mức tăng nhỏ nhất có thể trong trường hợp xấu nhất mà theo đó quãng đường tối ưu của Bessie trong bóng tối dài hơn quãng đường tối ưu của cô trong chuồng sáng, trong đó trường hợp xấu nhất được xét trên mọi đỉnh mà Bessie có thể xuất phát.

Ví dụ

4
0 0
0 10
1 10
1 0

2

Nguồn

USACO 2016 January Contest, Platinum - Lights Out: https://usaco.org/index.php?page=viewproblem2&cpid=602

Tác giả: Brian Dean.