trang chủ / đề bài / icpc24_mb_i

Thay thế

Đề bài

Mô tả

Alice vừa phát triển một ngôn ngữ hoạt động trên các ký tự là các số tự nhiên nhỏ hơn Z. Cô có một tập gồm n luật biến đổi, mỗi luật có dạng x→y1,y2,…,yk (với 2≤x<Z; 0≤yi<Z): thay một ký tự x trong dãy bằng dãy y1,y2,…,yk. Mỗi luật có thể được áp dụng nhiều lần, và quá trình chỉ dừng khi thu được một dãy nhị phân (chỉ gồm các số 0 và 1). Ví dụ, với các luật:

  • 3→2,3
  • 3→2,4,6
  • 2→0,0,1
  • 4→1
  • 6→4,0,4

cô có thể biến đổi dãy 1,2,3,4 như sau: 1,2,3,4→1,2,2,3,4→1,2,2,3,1→1,2,2,2,4,6,1→1,0,0,1,0,0,1,0,0,1,1,1,0,1,1.

Bob có một tập gồm m dãy nhị phân. Hãy giúp Alice: xuất phát từ một số duy nhất, tìm dãy nhị phân ngắn nhất có thể tạo ra mà không có đoạn con liên tiếp nào trùng với một dãy trong tập của Bob.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên Z,n,m (0≤Z−2≤n≤100; 0≤m≤50).
  • Mỗi dòng trong n dòng tiếp theo mô tả một luật dạng x k y1 y2 … yk (2≤x<Z, k≥1, 0≤yi<Z). Tổng các k của mọi luật không vượt quá 100. Có thể có số x không có luật nào; khi đó từ x không tạo được dãy nhị phân nào.
  • Mỗi dòng trong m dòng tiếp theo mô tả một dãy nhị phân của Bob dạng k b1 b2 … bk (k≥1, bi∈{0,1}). Tổng các k của mọi dãy không vượt quá 50.

Dữ liệu ra

In ra Z−2 dòng, dòng thứ i chứa độ dài của dãy nhị phân ngắn nhất mà Alice có thể tạo ra khi xuất phát từ số a=i+1, sao cho không có đoạn con liên tiếp nào của nó trùng với một dãy của Bob. Nếu không có dãy hữu hạn nào thỏa mãn, in ra 0. Dữ liệu đảm bảo nếu tồn tại dãy hữu hạn thỏa mãn thì tồn tại một dãy như vậy có độ dài không vượt quá 264−1.

Ràng buộc

  • 0≤Z−2≤n≤100, 0≤m≤50
  • 2≤x<Z, 0≤yi<Z, k≥1, tổng k của các luật ≤100
  • bi∈{0,1}, tổng độ dài các dãy của Bob ≤50

Ví dụ

Input Output Giải thích
7 5 3
3 2 2 3
3 3 2 4 6
2 3 0 0 1
4 1 1
6 3 4 0 4
3 0 0 0
3 1 1 1
4 0 1 0 1
3
0
1
0
3
Ví dụ của đề gốc, dãy của Bob là 000, 111, 0101. Từ 2 được 0,0,1; từ 4 được 1; từ 6 được 1,0,1. Mọi dãy hữu hạn tạo từ 3 đều chứa một dãy của Bob (ví dụ 3→2,4,6 cho 0011101, chứa 111); số 5 không có luật nào.
4 4 2
2 1 0
2 2 3 3
3 2 1 1
3 2 2 1
1 0
2 1 1
0
0
Ví dụ bổ sung, tính bằng lời giải mẫu. Mọi dãy tạo từ 2 hoặc 3 đều chứa ký tự 0 hoặc hai ký tự 1 liền 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