USACO 2012 - Tháng 2 - Hạng Đồng

Farmer John có một sợi dây dài \(L\) (\(1 \le L \le 10\,000\)), dùng cho nhiều công việc khác nhau quanh trang trại. Trên dây có \(N\) nút thắt ở những vị trí đôi một khác nhau (\(1 \le N \le 100\)), trong đó có một nút tại mỗi đầu dây.

FJ nhận thấy có một số vị trí mà ông có thể gập sợi dây ngược lên chính nó sao cho tất cả các nút trên hai đoạn dây đối diện trùng khít với nhau:

Hãy giúp FJ đếm số điểm gập có tính chất này. Được phép gập ngay tại một nút thắt, ngoại trừ không được gập tại một trong hai đầu dây; các nút thừa ở phía dài hơn của nếp gập không gây trở ngại (nghĩa là các nút chỉ cần trùng nhau trong vùng có hai đoạn dây đối diện nhau). FJ mỗi lần chỉ xét một nếp gập duy nhất; may thay, ông không bao giờ gập nhiều lần.

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(N\) và \(L\), cách nhau bởi dấu cách.
• Các dòng từ 2 đến \(1+N\): mỗi dòng chứa một số nguyên trong đoạn \(0 \ldots L\), chỉ vị trí của một nút thắt. Hai trong số các dòng này luôn là 0 và \(L\).

Dữ liệu ra

In số vị trí gập hợp lệ.

Ví dụ

5 10
0
10
6
2
4

4

Nguồn

USACO 2012 February Contest, Bronze - Rope Folding: https://usaco.org/index.php?page=viewproblem2&cpid=112

Tác giả: Brian Dean, 2012.

Farmer John đã mua một chiếc máy mới có khả năng trồng cỏ trong bất kỳ vùng hình chữ nhật nào của trang trại được “căn theo trục” (tức là có các cạnh thẳng đứng và nằm ngang). Đáng tiếc, một ngày nọ máy gặp trục trặc và trồng cỏ không chỉ trong một mà trong \(N\) (\(1 \le N \le 10\)) vùng hình chữ nhật khác nhau, một số vùng thậm chí có thể chồng lấn.

Với các vùng hình chữ nhật đã được trồng cỏ, hãy giúp FJ tính tổng diện tích trang trại hiện được cỏ bao phủ.

Dữ liệu vào

• Dòng 1 chứa số nguyên \(N\).
• Các dòng từ 2 đến \(1+N\): mỗi dòng chứa bốn số nguyên \(x_1\), \(y_1\), \(x_2\), \(y_2\) cách nhau bởi dấu cách, xác định một vùng hình chữ nhật có góc trên bên trái là \((x_1,y_1)\) và góc dưới bên phải là \((x_2,y_2)\). Mọi tọa độ đều nằm trong đoạn \(-10\,000 \ldots 10\,000\).

Dữ liệu ra

In tổng diện tích được cỏ bao phủ.

Ví dụ

2
0 5 4 1
2 4 6 2

20

Nguồn

USACO 2012 February Contest, Bronze - Overplanting (Bronze): https://usaco.org/index.php?page=viewproblem2&cpid=113

Tác giả: Brian Dean, 2012.

Đàn bò đã trở nên say mê một trò chơi chữ mới có tên “Moo”. Trò chơi được chơi bởi một nhóm bò đứng thành một hàng dài, trong đó lần lượt mỗi con bò chịu trách nhiệm đọc thật nhanh một chữ cái cụ thể. Con bò đầu tiên mắc lỗi sẽ thua.

Dãy chữ cái trong Moo về nguyên tắc có thể kéo dài mãi mãi. Dãy bắt đầu như sau:

m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o

Cách mô tả tốt nhất cho dãy là dùng đệ quy: gọi \(S(0)\) là dãy 3 ký tự m o o. Sau đó, dãy dài hơn \(S(k)\) được tạo bằng cách lấy một bản sao của \(S(k-1)\), tiếp theo là m o ... o với \(k+2\) chữ o, rồi thêm một bản sao khác của \(S(k-1)\). Ví dụ:

S(0) = "m o o"
S(1) = "m o o m o o o m o o"
S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"

Như bạn có thể thấy, quá trình này cuối cùng tạo nên một chuỗi dài vô hạn, và đây chính là chuỗi ký tự được dùng trong trò chơi Moo.

Bessie cảm thấy mình rất thông minh và muốn dự đoán ký tự thứ \(N\) của chuỗi này là m hay o. Hãy giúp cô!

Dữ liệu vào

Dòng 1 chứa một số nguyên duy nhất \(N\) (\(1 \le N \le 10^9\)).

Dữ liệu ra

Dòng duy nhất của dữ liệu ra chứa một ký tự duy nhất, là m hoặc o.

Ví dụ

11

m

Nguồn

USACO 2012 February Contest, Bronze - Moo: https://usaco.org/index.php?page=viewproblem2&cpid=114

Tác giả: Brian Dean, 2012.