JOI 2024 - Garden 2

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 2100 (p) Thời gian: 4.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Vườn JOI có dạng hình vuông, được chia thành \(N\) hàng và \(N\) cột ô vuông. Ô ở hàng thứ \(i\) từ trên xuống và cột thứ \(j\) từ trái sang được gọi là ô \((i,j)\) (\(1 \le i,j \le N\)).

Đất trong vườn không tốt lắm, nên mỗi ô chỉ có thể trồng tối đa một bông hoa thuộc một màu nhất định. Cụ thể, ô \((i,j)\) chỉ có thể trồng hoa đỏ nếu \(A_{i,j}\) là R, hoa vàng nếu là Y, và hoa xanh dương nếu là B.

Để khu vườn đẹp hơn khi chụp ảnh từ trên không, ông K, người quản lý khu vườn, dự định trồng hoa theo quy trình sau:

  1. Chọn số nguyên \(r\) biểu diễn kích thước, thỏa mãn \(0 \le r \le (N-1)/2\).
  2. Chọn ô trung tâm \((x,y)\), thỏa mãn \(r+1 \le x \le N-r\) và \(r+1 \le y \le N-r\).
  3. Với mỗi \(d\) từ \(0\) đến \(r\), chọn màu \(c_d\) là đỏ, vàng hoặc xanh dương.
  4. Với mỗi ô \((x',y')\), đặt \(d = |x'-x| + |y'-y|\), trong đó \(|t|\) là giá trị tuyệt đối của \(t\). Nếu \(d \le r\), trồng một bông hoa màu \(c_d\) tại ô đó; nếu \(d > r\), không trồng hoa tại ô đó.

Việc trồng hoa phải phù hợp với màu hoa mà từng ô cho phép. Cho kích thước khu vườn và màu hoa có thể trồng ở mỗi ô, hãy viết chương trình tìm số bông hoa nhiều nhất mà ông K có thể trồng.

Dữ liệu vào

Dòng thứ nhất chứa số nguyên \(N\).

Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa xâu gồm \(N\) ký tự \(A_{i,1}A_{i,2}\ldots A_{i,N}\), không có dấu cách giữa các ký tự.

Dữ liệu ra

In ra trên một dòng số bông hoa nhiều nhất mà ông K có thể trồng.

Ràng buộc

  • \(3 \le N \le 3500\).
  • \(A_{i,j}\) là R, Y hoặc B với mọi \(1 \le i \le N\), \(1 \le j \le N\).
  • \(N\) là số nguyên.

Phân nhóm

Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.

  1. (4 điểm) \(N = 3\).
  2. (13 điểm) \(N \le 50\).
  3. (17 điểm) \(N \le 800\).
  4. (14 điểm) Có không quá \(5\) ô \((i,j)\) với \(1 \le i \le N\), \(1 \le j \le N\) mà \(A_{i,j}\) khác R.
  5. (16 điểm) Với mọi \(1 \le i \le N-1\), \(1 \le j \le N-1\), có ít nhất \(3\) giá trị bằng R trong bốn giá trị \(A_{i,j}\), \(A_{i,j+1}\), \(A_{i+1,j}\), \(A_{i+1,j+1}\).
  6. (36 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
3
RYR
YBY
BYY
Output 
5
Giải thích

Chọn \(r=1\), \((x,y)=(2,2)\), \(c_0\) là xanh dương và \(c_1\) là vàng thì có thể trồng \(5\) bông hoa như hình dưới đây. Màu nền của mỗi ô biểu diễn màu hoa có thể trồng tại ô đó. Trong hình, 黄 chỉ hoa vàng và 青 chỉ hoa xanh dương.

Không có cách trồng từ \(6\) bông hoa trở lên, nên in ra \(5\).

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(1, 2, 3, 6\).

Ví dụ 2

Input 
9
YYRYBBBYR
BYYRRBYBB
RBRRBRBBY
RYRBRYRBR
YYBRYYYRB
RRYBRYRBR
RBYRBRBRB
BRYYRBBBR
RBBBYBRRY
Output 
25
Giải thích

Chọn \(r=3\), \((x,y)=(5,6)\), \(c_0\) và \(c_1\) là vàng, \(c_2\) là đỏ, \(c_3\) là xanh dương thì có thể trồng \(25\) bông hoa như hình dưới đây. Màu nền của mỗi ô biểu diễn màu hoa có thể trồng tại ô đó. Trong hình, 赤 chỉ hoa đỏ, 黄 chỉ hoa vàng và 青 chỉ hoa xanh dương.

Không có cách trồng từ \(26\) bông hoa trở lên, nên in ra \(25\).

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 3, 6\).

Ví dụ 3

Input 
6
RBYRBY
BYRBYR
YRBYRB
RBYRBY
BYRBYR
YRBYRB
Output 
1
Giải thích

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 3, 6\).

Ví dụ 4

Input 
20
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRBRRRRRRRRRRRRYRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRYRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRYRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRBR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRR
Output 
85
Giải thích

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 3, 4, 5, 6\).

Ví dụ 5

Input 
10
RRRRRRRRRR
RYRRRRRRRR
RRRRYRRRRR
RBRRRRRRRR
RRRRRRRRYR
RBRRRRRRRR
RRRRBRRRRR
RBRRRRRRRR
RRRRRRRRYR
RRRRRRRRRR
Output 
25
Giải thích

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 3, 5, 6\).

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: