02/10/2018, 14:24

BCTELEPH spoj PTIT – Danh sách điện thoại nhất quán

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCTELEPH/ 1. Đề bài BCTELEPH spoj PTIT Cho một danh sách các số điện thoại, hãy xác định danh sách này có số điện thoại nào là phần trước của số khác hay không? Nếu không thì danh sách này được gọi là nhất quán. Giả sử một danh sách ...

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCTELEPH/

1. Đề bài BCTELEPH spoj PTIT

Cho một danh sách các số điện thoại, hãy xác định danh sách này có số điện thoại nào là phần trước của số khác hay không? Nếu không thì danh sách này được gọi là nhất quán. Giả sử một danh sách có chứa các số điện thoại sau:

–          Số khẩn cấp:  911

–          Số củ- a Alice: 97625999

–          Số của Bob:   91125426

Trong trường hợp này, ta không thể gọi cho Bob vì tổng đài sẽ kết nối bạn với đường dây khẩn cấp ngay khi bạn quay 3 số đầu trong số của Bob, vì vậy danh sách này là không nhất quán.

 Dữ liệu vào

Dòng đầu tiên chứa một số nguyên 1 ≤ t ≤ 40 là số lượng bộ test. Mỗi bộ test sẽ bắt đầu với số lượng số điện thoại n được ghi trên một dòng, 1 ≤ n ≤ 10000. Sau đó là n dòng, mỗi dòng ghi duy nhất 1 số điện thoại. Một số điện thoại là một dãy không quá 10 chữ số. 

Dữ liệu ra

Với mỗi bộ dữ liệu vào, in ra “YES” nếu danh sách nhất quán và “NO” trong trường hợp ngược lại.

INPUTOUTPUT
23

911

97625999

91125426

5

113

12340

123440

12345

98346 

NOYES

2. Hướng dẫn BCTELEPH spoj PTIT

Mình sẽ hướng dẫn các bạn làm bài này bằng cách thô nhất. với mỗi test độ phức tạp sẽ là O(10*N log2 N)

Ý tưởng: bạn nhập các SĐT ở dạng xâu, và đầu tiên bạn sẽ sắp xếp các xâu đó.

với mỗi xâu A[i] bạn sẽ dùng chặt nhị phân tìm xem có xâu nào giống xâu S ko, với S là xâu được cắt ra từ xâu A[i] (từ A[i][1]->a[i][j] , với j=2..length(a[i])).

Nếu chặt nhị phân mà tìm thấy tức là nó không nhất quán, và ngược lại.

3. Code tham khảo BCTELEPH spoj PTIT

0