trang chủ / đề bài / icpcwf12_f

Chùm chìa khóa

Đề bài

Mô tả

Adam mang theo một chùm chìa khóa gắn trên các vòng khóa, một số vòng có thể móc vào nhau. Đây là loại vòng khóa xoắn thông thường, nên có thể gắn một chìa vào vòng hoặc tháo một chìa ra khỏi vòng bằng cách luồn chìa dọc theo vòng xoắn. Tương tự, có thể móc hai vòng vào nhau hoặc tách chúng ra. Adam muốn đưa một số chìa cho Brenda. Vì thao tác với chìa và vòng thường rất phiền (và hại móng tay), Adam muốn tìm cách làm sao cho số thao tác với chìa và với vòng là ít nhất.

Mỗi lần gắn một chìa, tháo một chìa, móc hai vòng hoặc tách hai vòng được tính là một thao tác. Vì thao tác với hai vòng dễ hơn nhiều so với luồn một chìa, trước hết ta muốn số lần gắn và tháo chìa là ít nhất. Trong các cách có cùng số thao tác chìa ít nhất, cần tìm cách có ít lần móc và tách vòng nhất.

Khi mọi thao tác hoàn tất, Adam và Brenda mỗi người phải mang đúng một nhóm liên thông gồm các vòng và chìa. Ngoại lệ duy nhất là khi một trong hai người không có chìa nào: khi đó người này không cần vòng nào. Mỗi chìa phải được gắn vào đúng một vòng. Một số vòng (nhưng không phải chìa) có thể bị coi là thừa và được để riêng, không thuộc hai nhóm trên.

Hình dưới mô tả cấu hình ban đầu gồm bốn chìa trên ba vòng (ví dụ 1; vòng là hình tròn, chìa là hình chữ nhật, chìa của Brenda tô màu). Adam muốn đưa cho Brenda hai chìa N và R. Có thể làm việc này bằng hai thao tác chìa (tháo A khỏi vòng a và gắn vào vòng c) và một thao tác vòng (tách vòng b khỏi vòng c):

dot
graph {
  rankdir=LR;
  node [shape=circle];
  a -- b; b -- c;
  A [shape=box]; B [shape=box];
  N [shape=box, color=red]; R [shape=box, color=red];
  a -- A; a -- N; b -- R; c -- B;
}

Cấu hình sau khi thực hiện: nhóm a, b mang N, R cho Brenda; vòng c mang A, B cho Adam.

dot
graph {
  rankdir=LR;
  node [shape=circle];
  a -- b;
  A [shape=box]; B [shape=box];
  N [shape=box, color=red]; R [shape=box, color=red];
  a -- N; b -- R; c -- A; c -- B;
}

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test, đọc tới hết file. Mỗi bộ test gồm một hoặc nhiều dòng, mỗi dòng là một xâu gồm hai chữ cái. Chữ thường (a đến z) là các vòng khóa, chữ hoa (A đến Z) là các chìa. Hai chữ cái trên một dòng cho biết hoặc một chìa đang gắn vào một vòng, hoặc hai vòng đang móc vào nhau. Mỗi bộ test kết thúc bằng một dòng chứa chữ số 0.

Các chìa từ A đến M thuộc về Adam (ở lại với Adam), các chìa từ N đến Z được đưa cho Brenda.

Không có dòng nào chứa hai chữ hoa. Không cặp chữ cái nào xuất hiện quá một lần trong cùng một bộ test. Mỗi chìa gắn vào đúng một vòng. Các vòng không tạo thành "chu trình" (tách bất kỳ hai vòng đang móc nhau nào cũng làm tăng số nhóm liên thông). Mọi chìa và vòng tồn tại đều được nhắc tới ít nhất một lần.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test, tiếp theo là số ít nhất các thao tác gắn/tháo chìa và số ít nhất các thao tác móc/tách vòng, theo định dạng trong ví dụ.

Nếu không có cách nào chia chìa như yêu cầu, in ra số thứ tự của bộ test và từ impossible thay cho hai số nguyên.

Ràng buộc

  • Có nhiều nhất 26 vòng (a đến z) và nhiều nhất 26 chìa (A đến Z).
  • Các vòng móc với nhau tạo thành một rừng (không có chu trình); mỗi chìa gắn vào đúng một vòng.

Ví dụ

Input Output Giải thích
ab
bc
aA
aN
Rb
cB
0
aA
bB
Cc
0
aA
aZ
0
aA
bB
cC
xX
yY
ax
xb
by
yc
0
Case 1: 2 1
Case 2: 0 2
Case 3: impossible
Case 4: 0 7
Bộ 1 là cấu hình trong hình. Bộ 2: Brenda không nhận chìa nào; chỉ cần móc ba vòng rời nhau của Adam thành một nhóm (2 thao tác). Bộ 3: chỉ có một vòng mang chìa của cả hai người nên không thể chia. Bộ 4: tách cả 4 chỗ móc của dãy a−x−b−y−c, rồi móc a−b, b−c cho Adam và x−y cho Brenda, tổng 7 thao tác vòng.
aA
bZ
0
aA
bB
0
Case 1: 0 0
Case 2: 0 1
Bộ 1: hai vòng rời nhau, mỗi người đã có đúng một vòng của mình. Bộ 2: chỉ Adam có chìa, cần móc hai vòng vào nhau.

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