trang chủ / đề bài / icpcwf06_h

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 3 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ó N đườ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ố 2; 1 L nghĩa là gấp mép phải sang trái theo đường gấp dọc số 1 (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 1 và 3 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 N và K. N 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ố 1,2,…,N từ trên xuống dưới và từ trái sang phải. K là số lần gấp.

Tiếp theo là K mô tả lần gấp. Mỗi mô tả gồm một số nguyên C 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ố 0.

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

  • 1≤N≤64, 1≤K≤64.
  • 1≤C≤N; lệnh U, D dùng đường gấp ngang, lệnh L, R dù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 K 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á 100 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 4 lớp; có 1 túi bên trái, 3 túi ở cạnh trên, 3 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 2 đơn vị sang trái, phủ lên phần bên trái rộng 1 đơn vị và chìa ra ngoài 1 đơn vị; khi đó đường dọc số 2 nằm ngay trên mép trái ban đầu, ở giữa hình chữ nhật rộng 2 đơn vị, nên lần gấp cuối 2 R hợp lệ.

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