trang chủ / đề bài / icpcwf14_d

Chiến lược trò chơi

Đề bài

Mô tả

Alice và Bob chơi một trò chơi trên bàn cờ. Bàn cờ được chia thành các vị trí đánh nhãn a, b, c, d, ... và hai người dùng một quân cờ để đánh dấu vị trí hiện tại. Mỗi lượt chơi gồm hai bước:

  1. Alice chọn. Tùy theo vị trí hiện tại, Alice có các lựa chọn khác nhau, mỗi lựa chọn là một tập các vị trí. Alice chọn một tập S trong các tập vị trí có sẵn.
  2. Bob chọn. Bob chọn một vị trí p thuộc tập S mà Alice vừa chọn ở bước 1, rồi di chuyển quân cờ tới vị trí p. Đây là vị trí bắt đầu của lượt tiếp theo.

Trước lượt đầu tiên, mỗi người độc lập chọn một vị trí và công bố khi trò chơi bắt đầu. Vị trí của Bob là nơi trò chơi bắt đầu. Alice thắng nếu cô có thể buộc Bob di chuyển quân cờ tới vị trí mà cô đã chọn. Để trò chơi thêm thú vị, hai người thỏa thuận rằng Bob sẽ trả cho Alice một khoản tiền nếu anh thua, nhưng Alice phải trả cho Bob một khoản tiền sau mỗi lượt. Vì vậy trò chơi kết thúc khi quân cờ tới vị trí của Alice hoặc khi Alice hết tiền.

Cả hai đều chơi tối ưu: Alice luôn chọn lựa chọn dẫn tới chiến thắng của mình nếu có thể, còn Bob luôn cố gắng ngăn Alice thắng.

Với mọi cặp vị trí bắt đầu và vị trí đích, Alice muốn bạn xác định cô có thể thắng hay không, và nếu có thì sau bao nhiêu lượt.

Dữ liệu vào

Dòng đầu tiên chứa số vị trí n. Các vị trí được đánh nhãn bằng n chữ cái thường đầu tiên của bảng chữ cái tiếng Anh.

n dòng tiếp theo, mỗi dòng ứng với một vị trí p, theo thứ tự bảng chữ cái. Dòng của vị trí p mô tả các lựa chọn của Alice tại p: đầu tiên là số lựa chọn m, tiếp theo là m xâu đôi một khác nhau, mỗi xâu ứng với một lựa chọn. Mỗi xâu liệt kê các vị trí mà Bob có thể đi tới nếu Alice chọn lựa chọn đó: xâu có ít nhất 1 ký tự, các ký tự (ứng với các vị trí hợp lệ trên bàn cờ) được sắp theo thứ tự bảng chữ cái và không có ký tự nào lặp lại.

Dữ liệu ra

Với mỗi vị trí p theo thứ tự bảng chữ cái, in ra một dòng. Trên dòng đó, với mỗi vị trí q theo thứ tự bảng chữ cái, in ra số lượt nhỏ nhất mà Alice chắc chắn đưa được quân cờ tới vị trí q khi trò chơi bắt đầu ở vị trí p, hoặc −1 nếu Alice không thể chắc chắn tới được q từ p.

Ràng buộc

  • 1≤n≤25.
  • 1≤m<2n với mỗi vị trí.
  • Tổng số lựa chọn trong toàn bộ dữ liệu không vượt quá 106.

Ví dụ

Input Output Giải thích
2
2 ab b
1 b
0 1
-1 0
Từ a, Alice chọn tập b nên Bob buộc phải đi tới b: tới b sau 1 lượt. Từ b chỉ có tập b, quân cờ không bao giờ rời b, nên không tới được a.
3
1 b
2 b a
2 ab ac
0 1 -1
1 0 -1
2 2 0
Không lựa chọn nào tại a hay b chứa c, nên từ a, b không tới được c. Từ c tới a: Alice chọn ab; nếu Bob đi a thì đã tới, nếu Bob đi b thì lượt sau Alice chọn a, tổng cộng 2 lượt.

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