USACO 2020 - Tháng 12 - Hạng Vàng

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 USACO 2021 - Replication 100 (p) 4.0s 512M
2 USACO 2021 - Bovine Genetics 100 (p) 4.0s 512M
3 USACO 2021 - Square Pasture 100 (p) 4.0s 512M

1. USACO 2021 - Replication

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Sau khi xem quá nhiều video kỹ thuật "tự làm" trên mạng, Farmer John đã vô tình thả một rô-bốt có khả năng tự nhân bản vào trang trại!

Trang trại được biểu diễn bằng một lưới \(N\times N\) (\(3\le N\le 1000\)), trong đó mỗi ô hoặc trống hoặc chứa đá, và mọi ô trên biên đều chứa đá. Một số ô không có đá được đánh dấu là vị trí có thể đặt rô-bốt ban đầu.

Farmer John đặt rô-bốt ban đầu tại một trong các vị trí có thể xuất phát. Trong mỗi giờ tiếp theo, mọi bản sao của rô-bốt di chuyển phối hợp theo cùng một hướng: bắc, nam, đông hoặc tây.

Sau mỗi \(D\) giờ (\(1\le D\le 10^9\)), mọi bản sao đều nhân bản. Khi một rô-bốt tại ô \((x,y)\) nhân bản, nó tạo các bản sao mới tại \((x+1,y)\), \((x-1,y)\), \((x,y+1)\) và \((x,y-1)\); rô-bốt ban đầu vẫn ở \((x,y)\). Theo thời gian, nhiều rô-bốt có thể cùng chiếm một ô.

Nếu một lần di chuyển hoặc nhân bản khiến bất kỳ rô-bốt nào đi vào ô đá, tất cả rô-bốt lập tức ngừng hoạt động. Do biên trang trại toàn là đá, cuối cùng các rô-bốt chắc chắn phải ngừng.

Hãy giúp đàn bò tìm số ô trống có thể chứa một rô-bốt tại một thời điểm nào đó.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(D\), cách nhau bởi dấu cách. Mỗi dòng trong \(N\) dòng tiếp theo chứa \(N\) ký tự. Mỗi ký tự là ., S hoặc #; . và S đều biểu thị ô trống, trong đó S đánh dấu một vị trí có thể xuất phát, còn # biểu thị đá.

Mọi ký tự ở hàng đầu, hàng cuối, cột đầu và cột cuối đều là #.

Dữ liệu ra

In số ô có thể chứa một rô-bốt tại một thời điểm nào đó.

Phân nhóm

  • Các test 4-5 thỏa mãn \(D=10^9\).
  • Các test 6-8 thỏa mãn \(D=1\).
  • Các test 9-12 thỏa mãn \(N\le 100\).
  • Các test 13-20 không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
10 1
##########
#........#
#S.......#
#........#
##########
#S....S..#
##########
##########
##########
##########
Output 
15
Giải thích

Trong các sơ đồ sau, x biểu thị một rô-bốt. Những vị trí có thể bị rô-bốt chiếm là:

##########
#xxx.....#
#xxxx....#
#xxx.....#
##########
#xx..xxx.#
##########
##########
##########
##########

Một chuỗi sự kiện có thể xảy ra như sau: FJ đặt rô-bốt tại vị trí xuất phát trên cùng bên trái; rô-bốt đi sang phải một ô; rô-bốt nhân bản; tất cả rô-bốt đi sang phải một ô. Lần nhân bản tiếp theo sẽ khiến một bản sao đi vào đá nên quá trình kết thúc.

##########    ##########    ##########    ##########
#........#    #........#    #.x......#    #..x.....#
#x.......#    #.x......#    #xxx.....#    #.xxx....#
#........#    #........#    #.x......#    #..x.....#
########## -> ########## -> ########## -> ##########
#........#    #........#    #........#    #........#
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########

Ví dụ 2

Input 
10 2
##########
#.#......#
#.#......#
#S.......#
#.#......#
#.#......#
##########
##########
##########
##########
Output 
28
Giải thích

Những vị trí có thể bị rô-bốt chiếm là:

##########
#x#.xxx..#
#x#xxxxx.#
#xxxxxxxx#
#x#xxxxx.#
#x#.xxx..#
##########
##########
##########
##########

Ví dụ 3

Input 
10 2
##########
#.S#.....#
#..#.....#
#S.......#
#..#.....#
#..#.....#
##########
##########
##########
##########
Output 
10
Giải thích

Những vị trí có thể bị rô-bốt chiếm là:

##########
#xx#.....#
#xx#.....#
#xxx.....#
#xx#.....#
#x.#.....#
##########
##########
##########
##########

Nguồn

USACO 2020 December Contest, Gold - Replication: https://usaco.org/index.php?page=viewproblem2&cpid=1065

Tác giả: Benjamin Qi.

2. USACO 2021 - Bovine Genetics

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Sau khi giải trình tự bộ gen của đàn bò, Farmer John chuyển sang chỉnh sửa gen! Một bộ gen được biểu diễn bằng một xâu chỉ gồm các ký tự A, C, G và T. Độ dài tối đa của một bộ gen mà Farmer John xét là \(10^5\).

Farmer John bắt đầu với một bộ gen và chỉnh sửa nó theo các bước sau:

  1. Tách bộ gen giữa mọi cặp ký tự liên tiếp giống nhau.
  2. Đảo ngược từng xâu con thu được.
  3. Ghép các xâu con đã đảo theo đúng thứ tự ban đầu.

Ví dụ, nếu FJ bắt đầu với bộ gen AGGCTTT, ông thực hiện:

AG | GCT | T | T
GA | TCG | T | T
GATCGTT

Không may, sau khi chỉnh sửa, máy tính của Farmer John gặp sự cố và ông mất trình tự bộ gen ban đầu. Hơn nữa, một số phần của bộ gen đã chỉnh sửa bị hỏng và được thay bằng dấu hỏi.

Cho trình tự của bộ gen đã chỉnh sửa, hãy giúp FJ xác định số bộ gen ban đầu có thể có, lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng duy nhất chứa một xâu không rỗng, trong đó mỗi ký tự là A, G, C, T hoặc ?.

Dữ liệu ra

In số bộ gen ban đầu có thể có, lấy modulo \(10^9+7\).

Phân nhóm

  • Trong các test 1-4, độ dài bộ gen không vượt quá \(10\).
  • Trong các test 5-11, độ dài bộ gen không vượt quá \(10^2\).
  • Trong các test 12-20, không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
?
Output 
4
Giải thích

Dấu hỏi có thể là một trong các ký tự A, G, C hoặc T.

Ví dụ 2

Input 
GAT?GTT
Output 
3
Giải thích

Ngoài AGGCTTT đã được mô tả ở trên, còn hai bộ gen ban đầu có thể có:

AGGATTT -> AG | GAT | T | T -> GA | TAG | T | T -> GATAGTT
TAGGTTT -> TAG | GT | T | T -> GAT | TG | T | T -> GATTGTT

Nguồn

USACO 2020 December Contest, Gold - Bovine Genetics: https://usaco.org/index.php?page=viewproblem2&cpid=1066

Tác giả: Benjamin Qi.

3. USACO 2021 - Square Pasture

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Đồng cỏ lớn nhất của Farmer John có thể được xem là một lưới lớn gồm các ô vuông hai chiều. Hiện có \(N\) con bò đứng trong một số ô của lưới (\(1\le N\le 200\)).

Farmer John muốn dựng một hàng rào bao quanh một vùng ô hình vuông. Các cạnh của hình vuông phải song song với các trục \(x\) và \(y\), và vùng này có thể nhỏ đến mức chỉ gồm một ô. Hãy giúp ông đếm số tập con bò phân biệt có thể được bao trong một vùng như vậy. Lưu ý rằng tập rỗng cũng được tính.

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ò. Mọi tọa độ \(x\) đôi một khác nhau và mọi tọa độ \(y\) cũng đôi một khác nhau. Tất cả các giá trị \(x\) và \(y\) nằm trong đoạn \(0\ldots 10^9\).

Mặc dù tọa độ các ô có bò đều không âm, vùng hình vuông được rào có thể kéo dài sang những ô mang tọa độ âm.

Dữ liệu ra

In số tập con bò mà FJ có thể bao bằng hàng rào. Có thể chứng minh rằng giá trị này vừa trong một số nguyên có dấu 32 bit.

Phân nhóm

  • Trong các test 1-5, mọi tọa độ của ô có bò đều nhỏ hơn \(20\).
  • Trong các test 6-10, \(N\le 20\).
  • Trong các test 11-20, không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
4
0 2
2 3
3 1
1 0
Output 
14
Giải thích

Có tổng cộng \(2^4\) tập con. FJ không thể dựng hàng rào chỉ bao các bò \(1\) và \(3\), hoặc chỉ các bò \(2\) và \(4\). Vì vậy, đáp án là \(2^4-2=16-2=14\).

Ví dụ 2

Input 
16
17 4
16 13
0 15
1 19
7 11
3 17
6 16
18 9
15 6
11 7
10 8
2 1
12 0
5 18
14 5
13 2
Output 
420

Nguồn

USACO 2020 December Contest, Gold - Square Pasture: https://usaco.org/index.php?page=viewproblem2&cpid=1067

Tác giả: Benjamin Qi.