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

Những chú bò của Farmer John rất hào hứng khi biết Tết Nguyên đán vừa được tổ chức, mở đầu năm Sửu, một năm luôn được loài bò yêu thích.

Mười hai con giáp của lịch Trung Quốc lặp theo chu kỳ 12 năm: Sửu, Dần, Mão, Thìn, Tỵ, Ngọ, Mùi, Thân, Dậu, Tuất, Hợi, Tý, rồi lại đến Sửu.

Bessie tự hào rằng cô sinh vào một năm Sửu từ nhiều năm trước. Bạn của cô là Elsie muốn biết mình sinh cách Bessie bao nhiêu năm. Hãy suy ra điều đó từ quan hệ giữa năm sinh của một số con bò trong trang trại.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\) (\(1\le N\le100\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa một câu tám từ mô tả quan hệ giữa năm sinh của hai con bò, có một trong hai dạng:

Mildred born in previous Dragon year from Bessie
Mildred born in next Dragon year from Bessie

Từ cuối cùng là tên một con bò trong trang trại, hoặc là Bessie, hoặc là một con bò đã được nhắc đến ở dòng trước. Từ đầu tiên là tên một con bò không phải Bessie và chưa từng được nhắc đến trong dữ liệu vào. Mọi tên bò dài không quá 10 ký tự và chỉ gồm các chữ cái từ a đến z hoặc từ A đến Z.

Từ thứ năm là một trong 12 con giáp tiếng Anh đã liệt kê ở trên. Từ thứ tư là previous hoặc next. Ví dụ, câu Mildred born in previous Dragon year from Bessie nghĩa là Mildred sinh vào năm Thìn gần năm sinh của Bessie nhất nhưng phải sớm hơn nghiêm ngặt, không được trùng năm.

Dữ liệu ra

In số năm chênh lệch giữa năm sinh của Bessie và Elsie. Dữ liệu bảo đảm có thể xác định giá trị này.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

4
Mildred born in previous Dragon year from Bessie
Gretta born in previous Monkey year from Mildred
Elsie born in next Ox year from Gretta
Paulina born in next Dog year from Bessie

12

Nguồn

USACO 2021 February Contest, Bronze - Year of the Cow: https://usaco.org/index.php?page=viewproblem2&cpid=1107

Tác giả: Brian Dean.

Đồng cỏ của Farmer John được xem là một lưới lớn gồm các ô vuông hai chiều. Ban đầu, đồng cỏ trống.

Farmer John lần lượt thêm \(N\) con bò vào đồng cỏ (\(1\le N\le10^5\)). Con bò thứ \(i\) chiếm một ô \((x_i,y_i)\) khác mọi ô đã có bò (\(0\le x_i,y_i\le1000\)).

Một con bò được gọi là "thoải mái" nếu có đúng ba con bò khác kề với nó theo phương ngang hoặc dọc. Farmer John muốn đếm số bò thoải mái trong trang trại. Với mỗi \(i\) trong đoạn \(1\ldots N\), hãy cho biết tổng số bò thoải mái sau khi thêm con bò thứ \(i\).

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên, cách nhau bởi dấu cách, là tọa độ \((x,y)\) của ô có một con bò. Bảo đảm mọi ô này đôi một khác nhau.

Dữ liệu ra

Dòng thứ \(i\) chứa tổng số bò thoải mái sau khi thêm \(i\) con bò đầu tiên vào đồng cỏ.

Phân nhóm

• Các test 1-4 thỏa mãn \(N\le400\).
• Các test 5-12 không có ràng buộc bổ sung.

Ví dụ

8
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2

0
0
0
1
0
0
1
2

Nguồn

USACO 2021 February Contest, Bronze - Comfortable Cows: https://usaco.org/index.php?page=viewproblem2&cpid=1108

Tác giả: Benjamin Qi.

Hàng rào bao quanh đồng cỏ lớn nhất của Farmer John đã xuống cấp, và cuối cùng ông quyết định thay bằng một hàng rào mới.

Không may, khi Farmer John đang bố trí hàng rào mới, một con ong lớn đuổi ông chạy quanh đồng cỏ, khiến hàng rào đi theo một đường khá bất thường. Đường đi của hàng rào được mô tả bằng một xâu ký tự, mỗi ký tự là N (bắc), E (đông), S (nam) hoặc W (tây), và biểu thị một đoạn hàng rào dài 1 mét. Ví dụ, xâu NESW nghĩa là hàng rào đi về phía bắc 1 mét, sang đông 1 mét, xuống nam 1 mét, rồi sang tây 1 mét để trở về điểm xuất phát.

Hàng rào kết thúc tại vị trí bắt đầu. Đây là điểm duy nhất được đường đi ghé qua nhiều hơn một lần, và điểm xuất phát chỉ được ghé lại đúng một lần ở cuối. Vì vậy, hàng rào thực sự bao quanh một vùng liên thông duy nhất của đồng cỏ, dù vùng này có thể có hình dạng khá lạ.

Farmer John muốn biết đường ông dựng hàng rào đi theo chiều kim đồng hồ, nghĩa là vùng được bao nằm bên phải khi ta đi theo xâu, hay ngược chiều kim đồng hồ, nghĩa là vùng được bao nằm bên trái.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\) (\(1\le N\le20\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa một xâu có độ dài từ 4 đến 100, mô tả một đường đi của hàng rào.

Dữ liệu ra

Với mỗi đường đi trong \(N\) đường đi, in CW nếu nó theo chiều kim đồng hồ hoặc CCW nếu nó ngược chiều kim đồng hồ.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

2
NESW
WSSSEENWNEESSENNNNWWWS

CW
CCW

*>*
^ v
@<*

*<*<*<*
v     ^
*<@     *
v       ^

* *>*>* *
v ^   v ^
* *<* * *
v   ^ v ^
*>*>* *>*

Nguồn

USACO 2021 February Contest, Bronze - Clockwise Fence: https://usaco.org/index.php?page=viewproblem2&cpid=1109

Tác giả: Brian Dean.