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.
| INPUT | OUTPUT | |
| 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | 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. |
