trang chủ / đề bài / icpcwf08_i

Nghi phạm mật khẩu

Đề bài

Mô tả

Bạn là thiên tài máy tính của tổ chức bí mật mang tên Sneaky Underground Smug Perpetrators of Evil Crimes and Thefts (SUSPECT). Mục tiêu của phi vụ tội ác mới nhất của SUSPECT là kẻ thù lớn nhất của họ, Câu lạc bộ Cảnh sát Thông minh Khó tả (ICPC), và mọi thứ đã sẵn sàng. Mọi thứ, trừ một điều nhỏ: mật khẩu bí mật của hệ thống máy tính chính của ICPC.

Mật khẩu chỉ gồm các chữ cái thường từ a đến z. Hơn nữa, qua nhiều lần quan sát lén lút, bạn đã xác định được độ dài của mật khẩu, cùng với một vài xâu con (có thể chồng lên nhau) của mật khẩu, nhưng bạn không biết chính xác chúng xuất hiện ở đâu trong mật khẩu.

Ví dụ, giả sử bạn biết mật khẩu dài 10 ký tự và đã quan sát được các xâu con hello và world. Khi đó mật khẩu phải là helloworld hoặc worldhello.

Câu hỏi là những thông tin này có đủ để thu hẹp số mật khẩu có thể xuống một con số hợp lý hay không. Để trả lời, hãy viết chương trình xác định số mật khẩu có thể (tức là số xâu độ dài N gồm các chữ cái thường chứa mọi xâu con đã biết) và, nếu có không quá 42 mật khẩu, in ra tất cả chúng.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên N và M lần lượt là độ dài mật khẩu và số xâu con đã biết. Tiếp theo là M dòng, mỗi dòng chứa một xâu con đã biết, gồm từ 1 đến 10 chữ cái thường a-z.

Sau bộ test cuối cùng là một dòng chứa hai số 0.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự của bộ test (bắt đầu từ 1) và Y suspects, trong đó Y là số mật khẩu có thể của bộ test đó (luôn viết suspects, kể cả khi Y=1). Nếu số mật khẩu không quá 42, in tiếp tất cả các mật khẩu có thể theo thứ tự từ điển, mỗi mật khẩu trên một dòng. Làm theo đúng định dạng trong ví dụ.

Ràng buộc

  • 1≤N≤25, 0≤M≤10.
  • Mỗi xâu con đã biết gồm từ 1 đến 10 chữ cái thường; các xâu con có thể trùng nhau, có thể dài hơn N.
  • Dữ liệu đảm bảo số mật khẩu có thể của mỗi bộ test không vượt quá 1015.
  • Mỗi file có không quá 100 bộ test và tổng các giá trị 2M của các bộ test trong một file không quá 8192.

Ví dụ

Input Output Giải thích
10 2
hello
world
10 0
4 1
icpc
0 0
Case 1: 2 suspects
helloworld
worldhello
Case 2: 141167095653376 suspects
Case 3: 1 suspects
icpc
Bộ test 1 là ví dụ trong đề. Bộ test 2: không có ràng buộc nào, có 2610 mật khẩu, nhiều hơn 42 nên không in danh sách. Bộ test 3: chỉ có icpc.
3 2
ab
ba
3 3
ab
ab
b
2 1
abc
7 0
1 0
0 0
Case 1: 2 suspects
aba
bab
Case 2: 52 suspects
Case 3: 0 suspects
Case 4: 8031810176 suspects
Case 5: 26 suspects
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
Bộ test 1: hai xâu con chồng lên nhau. Bộ test 2: xâu con ab xuất hiện hai lần trong danh sách, còn b nằm trong ab; mật khẩu có dạng ab? hoặc ?ab, tổng cộng 26+26=52. Bộ test 3: xâu con dài hơn mật khẩu nên không có mật khẩu nào. Bộ test 4: 267 mật khẩu, vượt kiểu số nguyên 32 bit. Bộ test 5: 26 mật khẩu, không quá 42 nên in hế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