Nguồn đề bài: http://www.spoj.com/PTIT/problems/GOODFRIE/
Nội dung bài viết
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
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
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 | 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. |
Bài viết liên quan
- P146PROG spoj PTIT – Cuộc thi ăn socola
- P145PROD spoj PTIT – Diện tích hình tròn
- P142PROC spoj PTIT – Tập chơi cờ vua
- P141SUMB spoj PTIT – ROUND 1B – Hoán vị
- P134SUMF spoj PTIT – SUM4 F – Sàng nguyên tố
- P132SUMD spoj PTIT – SUM2 D – Thực hiện phép tính
- P131SUMH spoj PTIT – SUM1 H – KANGUROO
- BCPOW spoj PTIT – Lũy thừa
- Giải đề ACM PTIT round 3 2015
- Ước chung lớn nhất, bội chung nhỏ nhất (Cơ bản)