trang chủ / đề bài / icpcwf08_f

Bảo tàng Glenbow

Đề bài

Mô tả

Bảo tàng Glenbow nổi tiếng ở Calgary là bảo tàng lớn nhất miền Tây Canada, với các hiện vật trải dài từ nghệ thuật, lịch sử văn hóa đến khoáng vật học. Một khu trưng bày hoàn toàn mới đang được lên kế hoạch, dành cho những lập trình viên xuất sắc giống như bạn. Đáng tiếc là vì thiếu chỗ, bảo tàng sẽ phải xây một tòa nhà hoàn toàn mới và chuyển sang đó.

Kích thước và sức chứa của tòa nhà mới khác với tòa nhà cũ. Nhưng mặt bằng của cả hai tòa nhà đều là các đa giác trực giao. Một đa giác trực giao là một đa giác mà mọi góc trong đều bằng 90∘ hoặc 270∘. Nếu ký hiệu góc 90∘ là R (Right, góc vuông) và góc 270∘ là O (Obtuse, góc tù) thì một xâu chỉ gồm các ký tự R và O có thể mô tả sơ lược một đa giác trực giao. Ví dụ, hình chữ nhật (Hình 1) là đa giác trực giao đơn giản nhất, và nó được mô tả bởi RRRR (các góc được liệt kê theo chiều ngược chiều kim đồng hồ, bắt đầu từ một đỉnh bất kỳ). Tương tự, đa giác hình chữ thập (Hình 2) có thể được mô tả bởi dãy RRORRORRORRO, RORRORRORROR hoặc ORRORRORRORR. Các dãy này được gọi là các xâu góc.

Hình 1: Hình chữ nhật.

Hình 2: Đa giác hình chữ thập.

Tất nhiên, một xâu góc không xác định hoàn toàn hình dạng của đa giác: nó không cho biết gì về độ dài các cạnh. Và có những xâu góc không thể mô tả bất kỳ đa giác trực giao hợp lệ nào (ví dụ RRROR). Phức tạp hơn nữa, không phải đa giác trực giao nào cũng là mặt bằng chấp nhận được cho bảo tàng. Bảo tàng chứa nhiều hiện vật quý giá, và các hiện vật này phải được canh gác. Vì lý do chi phí, mỗi tầng không thể có nhiều hơn một người gác. Vì vậy, một mặt bằng là chấp nhận được chỉ khi có một vị trí bên trong tầng mà từ đó một người gác có thể nhìn thấy toàn bộ tầng. Tương tự, một xâu góc là chấp nhận được chỉ khi nó mô tả ít nhất một đa giác chấp nhận được. Lưu ý rằng đa giác hình chữ thập ở Hình 2 có thể được canh gác bởi một người đứng ở chính giữa, nên nó chấp nhận được. Do đó xâu góc RRORRORRORRO là chấp nhận được, mặc dù nó cũng mô tả những đa giác khác mà một người gác không thể canh gác hết.

Hãy giúp các nhà thiết kế tòa nhà mới xác định có bao nhiêu xâu góc chấp nhận được có độ dài cho trước.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Mỗi bộ test là một dòng chứa một số nguyên dương L (1≤L≤1000), là độ dài mong muốn của xâu góc. Dữ liệu kết thúc bằng một dòng chứa duy nhất số 0.

Dữ liệu ra

Với mỗi bộ test, in một dòng gồm số thứ tự bộ test (bắt đầu từ 1) và số lượng xâu góc chấp nhận được có độ dài đã cho. Định dạng theo đúng ví dụ.

Ràng buộc

  • 1≤L≤1000.
  • Mỗi file có không quá 104 bộ test.

Ví dụ

Input Output Giải thích
4
6
0
Case 1: 1
Case 2: 6
Độ dài 4: chỉ có RRRR. Độ dài 6: các xâu RRRRRO, RRRROR, RRRORR, RRORRR, RORRRR, ORRRRR (đa giác hình chữ L).
1
2
3
5
8
0
Case 1: 0
Case 2: 0
Case 3: 0
Case 4: 0
Case 5: 20
Không có xâu góc chấp nhận được nào có độ dài 1, 2, 3 hoặc 5.

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