GOODFRIE spoj PTIT - Good friends

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

Nội dung bài viết

1. Đề bài GOODFRIE spoj PTIT
2. Hướng dẫn GOODFRIE spoj PTIT
3. Code tham khảo GOODFRIE spoj PTIT

1. Đề bài GOODFRIE spoj PTIT

Trong một lớp học, cô giáo xếp hạng N học sinh theo thứ tự điểm số từ cao xuống thấp. Hai học sinh sẽ là bạn nếu thứ tự của họ là gần nhau, tức là khác biệt giữa thứ tự không quá K. Ví dụ: nếu K = 1, thì chỉ có 2 học sinh ở trước và sau danh sách là bạn của 1 học sinh. Thêm nữa, hai học sinh gọi là bạn tốt nếu họ là bạn và tên của họ có cùng độ dài.

Viết chương trình tính số các cặp bạn tốt trong lớp.

Input

Dòng đầu chứ N (3<=N<=300 000) và K (1<= K <=N).

N dòng tiếp theo, mỗi dòng chứa tên một học sinh theo danh sách xếp hạng (từ 2 đến 20 chữ cái tiếng Anh in hoa).

Output

Số cặp bạn tốt.

Example

Input:

4 2

IVA

IVO

TOM

4 2
IVA
IVO
ANA
TOM

Output:
5
Input:
6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY

Output:
2

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

bài này tư tưởng giống bài Đặt trạm phủ sóng – Olympic 30/4/2015 tin học 10 các bạn có thể tham khảo.

3. Code tham khảo GOODFRIE spoj PTIT

CONST   FI='';
        nmax=400000;
type    data=longint;
var
        f:text;
        A:array[-nmax-1..2*nmax+1] of byte;
        n,k:data;
        res:array[0..20] of real;

procedure docfile;
var     i:data;
        tmp:string;
begin
        assign(f,fi); reset(f);
        readln(f,n,k);
        for i:=1 to n do
                begin
                        readln(f,tmp);
                        a[i]:=length(tmp);
                end;
        close(f);
end;

procedure xuli;
var     i,j:data;
        kq:real;
begin
        kq:=0;
        for i:=-k-50 to 0 do
                a[i]:=0;
        for i:=n+1 to k+50 do
                A[i]:=0;
        fillchar(res,sizeof(res),0);
        // tinh truoc nguoi thu nhat
        res[0]:=k;
        for i:=2 to 1+k do
                res[a[i]]:=res[a[i]]+1;
        kq:=res[a[1]];
        // tinh tiep theo
        for i:=2 to n do
                begin
                        res[a[i]]:=res[a[i]]-1;
                        res[a[i-1]]:=res[a[i-1]]+1;
                        res[a[i-k-1]]:=res[a[i-k-1]]-1;
                        res[a[i+k]]:=res[a[i+k]]+1;
                        kq:=kq+res[a[i]];
                end;
        writeln(round(kq) div 2);
end;

begin
        docfile;
        xuli;
end.

CONST FI='';

nmax=400000;

type data=longint;

var

f:text;

A:array[-nmax-1..2*nmax+1] of byte;

n,k:data;

res:array[0..20] of real;

procedure docfile;

var i:data;

tmp:string;

begin

assign(f,fi); reset(f);

readln(f,n,k);

for i:=1 to n do

begin

readln(f,tmp);

a[i]:=length(tmp);

end;

close(f);

end;

procedure xuli;

var i,j:data;

kq:real;

begin

kq:=0;

for i:=-k-50 to 0 do

a[i]:=0;

for i:=n+1 to k+50 do

A[i]:=0;

fillchar(res,sizeof(res),0);

// tinh truoc nguoi thu nhat

res[0]:=k;

for i:=2 to 1+k do

res[a[i]]:=res[a[i]]+1;

kq:=res[a[1]];

// tinh tiep theo

for i:=2 to n do

begin

res[a[i]]:=res[a[i]]-1;

res[a[i-1]]:=res[a[i-1]]+1;

res[a[i-k-1]]:=res[a[i-k-1]]-1;

res[a[i+k]]:=res[a[i+k]]+1;

kq:=kq+res[a[i]];

end;

writeln(round(kq) div 2);

end;

begin

docfile;

xuli;

end.

GOODFRIE spoj PTIT – Good friends

1. Đề bài GOODFRIE spoj PTIT

Input

Output

Example

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

3. Code tham khảo GOODFRIE spoj PTIT

Bài viết liên quan

Trả lời Hủy