trang chủ / đề bài / icpcwf08_a

Máy điều hòa không khí

Đề bài

Mô tả

Bạn là kỹ thuật viên của công ty Air Conditioning Machinery (ACM). Không may, khi đến chỗ khách hàng để lắp đặt đường ống điều hòa, bạn phát hiện mình sắp hết vật tư. Bạn chỉ còn sáu đoạn ống, và tất cả đều cùng một loại, gọi là "khúc nối" (elbow).

Bạn phải lắp một đường ống trong một không gian chật hẹp: một hình hộp chữ nhật có các cạnh là bội của một đơn vị độ dài. Hãy coi không gian này gồm một mảng các khối lập phương đơn vị. Mỗi khúc nối chiếm đúng bốn khối lập phương đơn vị, như Hình 1. Mỗi khối lập phương đơn vị bị chiếm bởi nhiều nhất một khúc nối. Mỗi khúc nối có đúng hai miệng ống, là các ô vuông màu xám của khúc nối trong Hình 1. Bạn có thể ghép các khúc nối thành đường ống dài hơn, nhưng đường ống phải nằm hoàn toàn trong không gian đã cho. Hình 2 là một cách nối hai khúc nối. Nhiệm vụ của bạn là nối một đầu vào với một đầu ra. Đầu vào và đầu ra nằm trên mặt ngoài của không gian, thẳng hàng với các khối lập phương đơn vị, như Hình 3. Để tiết kiệm chi phí, bạn phải hoàn thành việc này với số khúc nối ít nhất.

Hình 1: Một khúc nối (hai miệng ống là các ô xám).

Hình 2: Một cách nối hai khúc nối.

Hình 3: Đầu vào và đầu ra trên mặt ngoài của không gian.

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ười một giá trị cách nhau bởi dấu cách, lần lượt như sau.

  • Ba giá trị đầu là các số nguyên xmax, ymax, zmax cho biết kích thước của không gian theo các chiều x, y, z. Mỗi khối lập phương đơn vị trong không gian được xác định bởi tọa độ (x,y,z) với 1≤x≤xmax, 1≤y≤ymax, 1≤z≤zmax.
  • Ba giá trị tiếp theo là các số nguyên cho biết vị trí của đầu vào: tọa độ x, y, z của khối lập phương nối với đầu vào.
  • Giá trị tiếp theo là một xâu hai ký tự cho biết hướng của dòng khí đi vào, là một trong các mã +x, -x, +y, -y, +z, -z. Đầu vào nằm trên mặt của khối lập phương đón dòng khí theo hướng này. Ví dụ, nếu hướng đi vào là +y thì đầu vào nằm trên mặt của khối lập phương quay về hướng y âm.
  • Ba giá trị tiếp theo là các số nguyên cho biết vị trí của đầu ra: tọa độ x, y, z của khối lập phương nối với đầu ra.
  • Giá trị cuối cùng là một xâu hai ký tự cho biết hướng của dòng khí đi ra, dùng cùng các mã như trên. Đầu ra nằm trên mặt của khối lập phương mà dòng khí đi ra theo hướng này. Ví dụ, nếu hướng đi ra là +y thì đầu ra nằm trên mặt của khối lập phương quay về hướng y dương.

Dòng cuối cùng của dữ liệu chứa một số 0, đánh dấu kết thúc.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự bộ test (bắt đầu từ 1), sau đó là số khúc nối ít nhất cần dùng để nối đầu vào với đầu ra mà không ra ngoài không gian. Nếu không thể làm được với sáu khúc nối hiện có, in từ Impossible. Định dạng theo đúng ví dụ.

Ràng buộc

  • 1≤xmax,ymax,zmax≤20.
  • Khối lập phương của đầu vào và của đầu ra nằm trong không gian; mặt chứa đầu vào và mặt chứa đầu ra đều thuộc mặt ngoài của không gian.
  • Mỗi file có không quá 100 bộ test.

Ví dụ

Input Output Giải thích
5 4 3 3 1 1 +z 5 4 3 +x
5 4 3 3 1 1 +z 1 2 3 -x
0
Case 1: 2
Case 2: Impossible
Bộ 1: khúc nối thứ nhất chiếm (3,1,1), (3,1,2), (3,1,3), (3,2,3) và đưa khí ra theo hướng +y; khúc nối thứ hai chiếm (3,3,3), (3,4,3), (4,4,3), (5,4,3) và đưa khí ra theo hướng +x đúng tại đầu ra. Bộ 2: sáu khúc nối không đủ.
3 2 1 1 1 1 +y 3 2 1 +x
3 2 1 1 1 1 +y 3 2 1 +y
6 9 1 1 3 1 +x 6 9 1 +y
0
Case 1: 1
Case 2: Impossible
Case 3: 3
Bộ 1: một khúc nối chiếm (1,1,1), (1,2,1), (2,2,1), (3,2,1). Bộ 2: cùng khối đầu ra nhưng hướng ra +y thì không làm được. Bộ 3: ví dụ ba khúc nối chiếm lần lượt (1,3,1), (2,3,1), (2,4,1), (2,5,1); rồi (2,6,1), (2,7,1), (3,7,1), (4,7,1); rồi (5,7,1), (6,7,1), (6,8,1), (6,9,1).

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