Túi giấy
Đề bài
Mô tả
Origami, nghệ thuật gấp giấy, thường dùng đến các "túi" giấy, đặc biệt trong những mô hình phức tạp gồm nhiều tờ giấy, khi một mép của tờ này cần được nhét vào một túi của tờ khác. Trong bài này, bạn cần đếm số túi của một tờ giấy hình vuông đã được gấp phẳng. Một túi là một khe hở (nằm giữa hai mặt giấy) có thể tiếp cận được từ biên của tờ giấy đã gấp. Lưu ý rằng một khe hở tiếp cận được có thể tạo ra nhiều túi, vì mỗi cạnh mở của nó tính là một túi. Hình 1 là một ví dụ. Để ý rằng khe hở "ở giữa" (giữa lớp giấy thứ hai và thứ ba) đóng góp vào tổng số túi.

Hình 1: Các túi. Một túi ở bên trái, ba túi ở cạnh trên, ba túi ở bên phải.
Giả sử ban đầu tờ giấy nằm trên một mặt phẳng và không bao giờ bị nhấc hẳn khỏi mặt phẳng đó. Mọi nếp gấp đều nằm ngang hoặc thẳng đứng. Các nếp gấp chỉ nằm trên các đường gấp cách đều nhau, có đường theo mỗi chiều. Trên tờ giấy vuông ban đầu (chưa gấp), các đường gấp và các cạnh được đánh số từ trên xuống dưới và từ trái sang phải như trong Hình 2. Mỗi lần gấp thu nhỏ đường bao của tờ giấy đã gấp thành một hình chữ nhật nhỏ hơn; lần gấp cuối cùng cho ra một hình vuông cạnh một đơn vị. Mỗi lần gấp được mô tả bằng một đường gấp và một hướng. Chẳng hạn, 2 U nghĩa là gấp mép dưới lên trên theo đường gấp ngang số ; 1 L nghĩa là gấp mép phải sang trái theo đường gấp dọc số (xem Hình 2). Sau vài lần gấp, các đường gấp có thể trùng nhau (chẳng hạn các đường và trong Hình 2). Khi đó có thể dùng số nào cũng được để chỉ lần gấp theo đường đó (nên trong Hình 2, sau lần gấp đầu tiên, 1 D và 3 D là hai lệnh tương đương). Số túi được đếm trên biên của hình vuông một đơn vị cuối cùng. Một nếp gấp đã tạo thì không thể mở ra. Mọi nếp gấp đi xuyên qua tất cả các lớp giấy từ trên xuống dưới; bỏ qua độ dày của giấy.

Hình 2: Dãy lệnh 2 U, 1 L.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên và . là số đường gấp ngang (bằng số đường gấp dọc) của tờ giấy vuông. Các đường gấp được đánh số từ trên xuống dưới và từ trái sang phải. là số lần gấp.
Tiếp theo là mô tả lần gấp. Mỗi mô tả gồm một số nguyên là số hiệu đường gấp và một hướng, là một trong các chữ U, D, L, R (lên, xuống, trái, phải), cách nhau bởi khoảng trắng. Trước và sau mỗi mô tả cũng có khoảng trắng (dấu cách hoặc xuống dòng).
Kết quả cuối cùng của mỗi bộ test là một hình vuông cạnh một đơn vị.
Sau bộ test cuối cùng là một dòng chứa hai số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự của bộ test và số túi của hình vuông một đơn vị cuối cùng, theo đúng định dạng trong ví dụ.
Ràng buộc
- , .
- ; lệnh
U,Ddùng đường gấp ngang, lệnhL,Rdùng đường gấp dọc. - Mỗi lần gấp theo một đường gấp nằm hẳn bên trong hình chữ nhật hiện tại; phần bị gấp có thể dài hơn phần còn lại.
- Sau đúng lần gấp, tờ giấy là một hình vuông cạnh một đơn vị.
- Mỗi file có không quá bộ test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 2 1 R 1 U 3 5 2 U 1 L 3 D 3 R 2 L 0 0 |
Case 1: 7 pockets Case 2: 17 pockets |
Bộ 1 là Hình 1: gấp nửa trái sang phải rồi gấp nửa dưới lên, được lớp; có túi bên trái, túi ở cạnh trên, túi bên phải và không có túi nào ở cạnh dưới. Bộ 2 bắt đầu bằng hai lần gấp trong Hình 2. |
| 2 4 1 L 2 U 1 U 2 R 4 7 4 U 3 D 3 L 2 L 1 R 4 U 1 D 0 0 |
Case 1: 11 pockets Case 2: 20 pockets |
Ví dụ tự thêm. Bộ 1: lệnh 1 L gấp phần bên phải rộng đơn vị sang trái, phủ lên phần bên trái rộng đơn vị và chìa ra ngoài đơn vị; khi đó đường dọc số nằm ngay trên mép trái ban đầu, ở giữa hình chữ nhật rộng đơn vị, nên lần gấp cuối 2 R hợp lệ. |
Bình luận