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 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.

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

const   fi='';
        nmax=15000;
type
        data=longint;
var
        f:text;
        A:array[1..nmax] of int64;
        S:array[1..nmax] of string;
        Leg:array[0..11] of data;

        n,test:data;

procedure sort(l,r: longint);
      var
         i,j: longint;
                y,x:int64;
                z:string;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while a[i]<x do
            inc(i);
           while x<a[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                z:=s[i];
                s[i]:=s[j];
                s[j]:=z;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

function tknp(x:string; u,v:data):data;
var     dau,cuoi,giua:data;
begin
        dau:=u;
        cuoi:=v;
        while dau<=cuoi do
                begin
                        giua:=(dau+cuoi) div 2;
                        if s[giua]=x then
                                exit(giua)
                        else
                                if s[giua]>x then
                                        cuoi:=giua-1
                                else
                                        dau:=giua+1;
                end;
        exit(0);
end;

procedure xuli;
var     i,j:data;
        vtmin,er,x,k:data;

begin
        sort(1,n);
        for vtmin:=1 to 10 do
                if leg[vtmin]<>0 then
                        break;

        for i:=2 to 10 do
                begin
                        leg[i]:=leg[i-1]+leg[i];
                end;

        for i:=1 to n do
                begin
                        for j:=vtmin to length(s[i]) do
                                begin
                                        k:=tknp(copy(s[i],1,j),leg[j-1]+1,leg[j]);
                                        if (k<>0) and (k<>i) then
                                                begin
                                                        writeln('NO');
                                                        exit;
                                                end;
                                end;
                end;
        writeln('YES');
end;

procedure docfile;
var     i,k,er:data;
begin
        assign(f,fi); reset(f);
        readln(f,test);
        for k:=1 to test do
                begin
                        fillchar(leg,sizeof(leg),0);
                        readln(f,n);
                        for i:=1 to n do
                                begin
                                        readln(f,s[i]);
                                        val(s[i],a[i],er);
                                        inc(leg[length(s[i])]);
                                end;
                        xuli;
                end;
        close(f);
end;

begin
        docfile;
end.