trang chủ / đề bài / icpcwf06_f

Lắp đồng hồ

Đề bài

Mô tả

Ở Quảng trường Phố Cổ thành phố Praha có một chiếc Đồng hồ Thiên văn tuyệt đẹp, được chế tạo vào năm 1410. Suốt nhiều thế kỷ, nghệ thuật của người thợ đồng hồ là dùng các bánh răng để nối một trục quay với tốc độ đã biết sang các trục khác, cho đến khi, nhờ tổ hợp bánh răng thích hợp, có hai trục quay đúng tốc độ để biểu diễn kim phút và kim giờ.

Hãy viết chương trình nhận vào tốc độ của trục đầu vào và một bộ bánh răng, rồi tìm cách nối các bánh răng để tạo ra một chiếc đồng hồ có kim giờ và kim phút. Bạn được dùng bao nhiêu trục tuỳ ý, nhưng mỗi trục chỉ được gắn tối đa ba bánh răng. Mọi bánh răng trên cùng một trục quay cùng tốc độ. Nếu một bánh răng có T1 răng đang quay với tốc độ R1 ăn khớp với một bánh răng khác có T2 răng thì bánh răng thứ hai quay với tốc độ −R1·T1T2. Lời giải phải có hai trục: một trục phút quay theo chiều kim đồng hồ với tốc độ một vòng mỗi giờ, và một trục giờ quay theo chiều kim đồng hồ với tốc độ một vòng mỗi mười hai giờ. Không bắt buộc phải dùng hết các bánh răng.

Dữ liệu vào

Dữ liệu gồm nhiều bộ thử, mỗi bộ thử nằm trên một dòng. Mỗi dòng bắt đầu bằng số nguyên N (3≤N≤6) là số bánh răng có sẵn. Tiếp theo là số nguyên R (−3600≤R≤3600, R≠0) là tốc độ quay của trục đầu vào, tức số vòng trục đó quay được trong 24 giờ (số dương là quay theo chiều kim đồng hồ, số âm là quay ngược chiều kim đồng hồ). Sau R là N mô tả bánh răng. Mỗi mô tả là một cặp: một ký tự là tên của bánh răng, tiếp theo là số nguyên T (6≤T≤120) là số răng của bánh răng đó. Các tên và số trên một dòng cách nhau bởi dấu cách.

Sau bộ thử 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ộ thử, in một dòng chứa số thứ tự của bộ thử như trong ví dụ. Nếu lắp được đồng hồ từ bộ bánh răng đã cho thì sau dòng này là hai dòng nữa, một dòng cho kim phút và một dòng cho kim giờ. Ngược lại, dòng chứa số thứ tự bộ thử phải kết thúc bằng các từ IS IMPOSSIBLE như trong ví dụ.

Dòng cho kim phút bắt đầu bằng Minutes:, theo sau là một sơ đồ cho biết trục đầu vào được nối qua một dãy bánh răng tới trục phút như thế nào. Sơ đồ là một dãy các trục, cách nhau bởi dấu gạch ngang. Mỗi trục được biểu diễn bằng một hoặc hai ký tự:

  • Ký tự thứ nhất là tên bánh răng bị dẫn: bánh răng trên trục này ăn khớp với một bánh răng trên trục đứng trước. Với trục đầu vào, dùng dấu sao (*) để thể hiện rằng không có bánh răng bị dẫn.
  • Ký tự thứ hai là tên bánh răng dẫn: bánh răng trên trục này ăn khớp với một bánh răng trên trục đứng sau. Bánh răng bị dẫn và bánh răng dẫn có thể là cùng một bánh răng, khi đó trục được biểu diễn bằng một ký tự duy nhất là tên bánh răng này.
  • Trục cuối cùng của sơ đồ là trục phút, được biểu diễn bằng một chữ cái duy nhất là tên bánh răng bị dẫn của nó.

Dòng cho kim giờ bắt đầu bằng Hours: và ba dấu cách (để thẳng cột với dòng kim phút), theo sau là sơ đồ nối trục đầu vào tới trục giờ, cùng định dạng với sơ đồ kim phút.

Mỗi bánh răng chỉ được xuất hiện một lần trong chiếc đồng hồ. Tuy nhiên, sơ đồ kim phút và sơ đồ kim giờ có thể có chung một phần đầu. Một bánh răng trong phần đầu chung sẽ xuất hiện trong cả sơ đồ kim phút lẫn sơ đồ kim giờ. Cũng vì lý do đó, một trục có thể được dùng trong cả hai sơ đồ. Nếu một trục được dùng trong cả hai sơ đồ thì mô tả của nó trong hai sơ đồ có thể giống hoặc khác nhau. Chẳng hạn, một trục chỉ có một bánh răng tên A sẽ được biểu diễn là A trong cả hai sơ đồ. Mặt khác, một trục có ba bánh răng tên A, B và C có thể được biểu diễn là AB trong sơ đồ kim phút (nếu B là bánh răng dẫn trong sơ đồ đó) và AC trong sơ đồ kim giờ (nếu C là bánh răng dẫn trong sơ đồ đó).

Các dòng sau đây là những dòng ra hợp lệ:

  • Hours: *A-BC-D: trục đầu vào có một bánh răng, ăn khớp với một trục trung gian có hai bánh răng, trục này ăn khớp với trục giờ có một bánh răng.
  • Minutes: *A-B-C: trục đầu vào có một bánh răng, ăn khớp với một trục trung gian có một bánh răng, trục này ăn khớp với trục phút có một bánh răng.
  • Minutes: *: sơ đồ không cần bánh răng nào vì trục đầu vào đã quay đúng tốc độ của trục phút.

Nếu có nhiều cách lắp đồng hồ từ các bánh răng đã cho, hãy in lời giải dùng ít trục nhất. Nếu có nhiều lời giải cùng số trục ít nhất, in lời giải dùng ít bánh răng nhất. Nếu vẫn còn nhiều lời giải cùng số trục và số bánh răng ít nhất, in lời giải có chuỗi mô tả nhỏ nhất theo thứ tự từ điển. Chuỗi mô tả của một lời giải là sơ đồ kim phút nối tiếp sơ đồ kim giờ, sau khi bỏ hết các dấu sao và dấu gạch ngang. Ví dụ, lời giải có sơ đồ kim phút là *A-B và sơ đồ kim giờ là *A-BC-D-E có chuỗi mô tả là ABABCDE.

In một dòng trống giữa hai bộ thử liên tiếp.

Ràng buộc

  • 3≤N≤6; −3600≤R≤3600, R≠0; 6≤T≤120.
  • Tên các bánh răng là chữ cái Latinh in hoa, đôi một khác nhau trong cùng một bộ thử.
  • Mỗi file có từ 1 đến 100 bộ thử (không tính dòng 0 cuối cùng).
  • Với mỗi bộ thử lắp được đồng hồ, chỉ có đúng một cặp sơ đồ (kim phút, kim giờ) vừa dùng ít trục nhất, vừa dùng ít bánh răng nhất, vừa có chuỗi mô tả nhỏ nhất.

Ví dụ

Input Output Giải thích
6 40 P 7 Q 84 R 50 A 40 B 30 C 14
6 40 P 7 Q 84 R 45 A 40 B 30 C 14
0
Trial 1
Minutes: *B-A-R
Hours: *B-A-RP-C-Q

Trial 2 IS IMPOSSIBLE
Bộ 1: trục đầu vào quay 40 vòng mỗi ngày. Bánh răng B (30 răng) dẫn bánh răng A (40 răng): trục của A quay −40·30/40=−30. Bánh răng A dẫn tiếp R (50 răng): trục của R quay 30·40/50=24 vòng mỗi ngày, đó là trục phút. Trên trục phút gắn thêm P (7 răng) dẫn C (14 răng): −24·7/14=−12; rồi C dẫn Q (84 răng): 12·14/84=2 vòng mỗi ngày, đó là trục giờ. Ba trục đầu (trục đầu vào, trục A, trục R) dùng chung cho cả hai sơ đồ.
4 24 A 6 B 36 C 10 D 20
4 -24 B 8 W 8 G 32 Z 96
3 5 A 10 B 20 C 30
0
Trial 1
Minutes: *
Hours: *A-BC-D

Trial 2
Minutes: *B-W
Hours: *B-Z

Trial 3 IS IMPOSSIBLE
Ví dụ tự thêm. Bộ 1: trục đầu vào đã quay 24 vòng mỗi ngày nên chính nó là trục phút; trục giờ: −24·6/36=−4, rồi 4·10/20=2. Bộ 2: bánh răng B trên trục đầu vào dẫn cả W (24 vòng mỗi ngày) lẫn Z (2 vòng mỗi ngày). Bộ 3: không có cách lắp nào.

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