trang chủ / đề bài / icpcwf18_i

Đếm tam giác

Đề bài

Mô tả

Trong chuyến đi tới Bắc Kinh, bạn mang theo rất nhiều sách đố, trong đó có nhiều câu đố kiểu như sau: có bao nhiêu hình tam giác trong hình dưới đây?

Hình: minh họa ví dụ 2.

Những câu đố này giữ được sự hứng thú của bạn một lúc, nhưng rồi bạn nhanh chóng chán chúng và bắt đầu nghĩ xem có thể giải chúng bằng thuật toán như thế nào. Biết đâu một bài như vậy sẽ thật sự xuất hiện trong kỳ thi năm nay. Và đoán xem? Hôm nay là ngày may mắn của bạn!

Bức hình được vẽ trên một lưới tam giác đều: các đỉnh nằm thành r hàng, các hàng kề nhau lệch nhau nửa bước; các cạnh có thể có là cạnh nằm ngang nối hai đỉnh kề nhau trên cùng một hàng, và cạnh chéo nối một đỉnh với một trong hai đỉnh gần nhất ở hàng kề trên hoặc kề dưới. Hãy đếm số tam giác (với mọi kích thước) được tạo thành bởi các cạnh trong hình, tức là số tam giác mà cả ba cạnh đều được vẽ kín bằng các cạnh của lưới.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên r và c cho biết kích thước bức hình, trong đó r là số hàng đỉnh và c là số cột.

Tiếp theo là 2r−1 dòng, mỗi dòng có không quá 2c−1 ký tự. Các dòng lẻ chứa các đỉnh của lưới (biểu diễn bằng ký tự x thường) cùng không hoặc nhiều cạnh nằm ngang, còn các dòng chẵn chứa không hoặc nhiều cạnh chéo. Cụ thể, các dòng có số thứ tự 4k+1 có đỉnh ở các vị trí 1,5,9,13,…, còn các dòng có số thứ tự 4k+3 có đỉnh ở các vị trí 3,7,11,15,… (đánh số dòng của bức hình và vị trí ký tự từ 1). Mọi đỉnh có thể có đều xuất hiện trong dữ liệu vào (xem cách biểu diễn hình trên ở ví dụ 2).

Cạnh nằm ngang nối hai đỉnh kề nhau được biểu diễn bằng ba dấu gạch ngang ---. Cạnh chéo được biểu diễn bằng một ký tự gạch chéo xuôi / hoặc gạch chéo ngược \. Các ký tự cạnh được đặt chính xác ở giữa hai đỉnh tương ứng. Mọi ký tự khác đều là dấu cách. Lưu ý rằng nếu một dòng có thể có khoảng trắng ở cuối thì khoảng trắng đó có thể bị lược bỏ.

Dữ liệu ra

In ra số tam giác (với mọi kích thước) được tạo thành bởi các cạnh của lưới trong bức hình.

Ràng buộc

  • 1≤r≤3000.
  • 1≤c≤6000.

Ví dụ

Input Output Giải thích
3 3
x---x
 \ /
  x
 / \
x   x
1 Năm đỉnh, bốn cạnh chéo và một cạnh nằm ngang ở hàng trên. Chỉ có một tam giác: tam giác chúc đỉnh xuống tạo bởi cạnh ngang phía trên và hai cạnh chéo nối xuống đỉnh ở giữa. Hai cạnh chéo phía dưới không tạo thêm tam giác vì hàng dưới không có cạnh ngang. Trong bảng, dấu cách được giữ nguyên vị trí.
4 10
x   x---x---x   x
     \ /   / \
  x   x---x   x   x
     / \ / \   \
x   x---x---x---x
   /   / \   \ / \
  x---x---x---x---x
12 Đây là bức hình ở hình minh họa: có 12 tam giác, gồm 7 tam giác cạnh 1 (4 tam giác đỉnh hướng lên, 3 tam giác đỉnh hướng xuống), 4 tam giác cạnh 2 và 1 tam giác cạnh 3 (đỉnh trên cùng ở hàng đầu, đáy là hàng cuối).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0