trang chủ / đề bài / icpcwf11_j

Kim tự tháp

Đề bài

Mô tả

Xây một kim tự tháp không quá khó nếu bạn có rất nhiều khối lập phương giống nhau. Trên một nền phẳng, bạn xếp, chẳng hạn, 10×10 khối thành một hình vuông. Đặt ở chính giữa phía trên hình vuông đó một hình vuông 9×9 khối. Cứ tiếp tục như vậy, cuối cùng bạn được một khối duy nhất, đó là đỉnh của kim tự tháp. Chiều cao của kim tự tháp này bằng độ dài cạnh đáy, trong ví dụ này là 10. Ta gọi đây là một kim tự tháp cao.

Nếu thấy kim tự tháp cao quá dốc, bạn có thể làm như sau. Trên hình vuông đáy 10×10, đặt một hình vuông 8×8, rồi một hình vuông 6×6, và cứ thế, kết thúc bằng một hình vuông đỉnh 2×2 (dĩ nhiên nếu cạnh đáy là số lẻ thì đỉnh là một khối duy nhất). Chiều cao của kim tự tháp này xấp xỉ một nửa độ dài cạnh đáy. Ta gọi đây là một kim tự tháp thấp.

Như vậy kim tự tháp cao có cạnh đáy k gồm k2+(k−1)2+…+12 khối và có chiều cao k; kim tự tháp thấp có cạnh đáy k gồm k2+(k−2)2+(k−4)2+… khối (tổng dừng ở 22 hoặc 12) và có chiều cao bằng số tầng của nó.

Ngày xửa ngày xưa (thật ra là rất xưa), có một vị pharaoh được thừa kế từ cha mình một số lượng lớn khối đá lập phương. Ông ra lệnh cho kiến trúc sư dùng toàn bộ số khối này để xây một kim tự tháp, không được thừa một khối nào. Kiến trúc sư nhã nhặn giải thích rằng không phải số khối nào cũng xây được một kim tự tháp. Với 10 khối có thể xây một kim tự tháp thấp cạnh đáy 3. Với 5 khối có thể xây một kim tự tháp cao cạnh đáy 2. Nhưng không có kim tự tháp nào dùng đúng 7 khối.

Pharaoh không vui, nhưng sau một hồi suy nghĩ ông đưa ra các yêu cầu mới:

  • Phải dùng hết tất cả các khối.
  • Được xây nhiều hơn một kim tự tháp, nhưng số kim tự tháp phải ít nhất có thể.
  • Các kim tự tháp phải đôi một khác nhau.
  • Mỗi kim tự tháp phải có chiều cao ít nhất 2.
  • Thỏa mãn các điều kiện trên, kim tự tháp lớn nhất phải lớn nhất có thể (tức là chứa nhiều khối nhất).
  • Thỏa mãn các điều kiện trên, kim tự tháp lớn thứ hai phải lớn nhất có thể.
  • Và cứ tiếp tục như vậy...

Vẽ hình trên cát mất khá nhiều thời gian, cuối cùng kiến trúc sư cũng tìm ra phương án tốt nhất.

Hãy viết chương trình xác định cách đáp ứng các yêu cầu của pharaoh khi biết số khối lập phương.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test, mỗi bộ trên một dòng. Mỗi bộ test là một số nguyên c cho biết số khối lập phương hiện có.

Sau bộ test cuối cùng là một dòng chứa duy nhất số 0.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự của bộ test, theo sau là các kim tự tháp cần xây, theo đúng định dạng Case i: ... của ví dụ. Các kim tự tháp được liệt kê theo thứ tự từ lớn nhất đến nhỏ nhất. Mỗi kim tự tháp được ghi bằng độ dài cạnh đáy, theo sau là chữ L nếu là kim tự tháp thấp hoặc chữ H nếu là kim tự tháp cao. Nếu hai kim tự tháp khác nhau có cùng số khối thì liệt kê kim tự tháp cao trước. In impossible nếu không thể đáp ứng các yêu cầu của pharaoh.

Ràng buộc

  • 1≤c≤106.

Ví dụ

Input Output Giải thích
29
28
0
Case 1: 3H 3L 2H
Case 2: impossible
Bộ 1: 29=14+10+5 (cao cạnh 3: 9+4+1; thấp cạnh 3: 9+1; cao cạnh 2: 4+1); không có cách nào dùng một hoặc hai kim tự tháp. Bộ 2: không có cách nào dùng đúng 28 khối.
5
4
10
213
1000000
0
Case 1: 2H
Case 2: impossible
Case 3: 3L
Case 4: 7L 5H 5L 4L 3H 2H
Case 5: 142H 42H 38L
Bộ 2: kim tự tháp thấp cạnh 2 chỉ có một tầng 2×2 (chiều cao 1) nên không được dùng. Bộ 4: 213=84+55+35+20+14+5, cần tới 6 kim tự tháp.

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