P145PROI PTIT spoj – ROUND 5I – Mật khẩu
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P145PROI/ 1. Đề bài P145PROI PTIT spoj Một xâu ký tự được gọi là mật khẩu “an toàn” nếu xâu có độ dài ít nhất bằng 6 và xâu chứa ít nhất một chữ cái in hoa , một chữ cái thường , một chữ số . Ví dụ, ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/P145PROI/
1. Đề bài P145PROI PTIT spoj
Một xâu ký tự được gọi là mật khẩu “an toàn” nếu xâu có độ dài ít nhất bằng 6 và xâu chứa ít nhất một chữ cái in hoa , một chữ cái thường , một chữ số .
Ví dụ, ‘a1B2C3’, ‘tinHoc6’ là hai mật khẩu “an toàn”. Còn ‘a1B2C’, ’a1b2c3’, ‘A1B2C3’, ‘tinHoc’ đều không phải là mật khẩu “an toàn”.
Một lần, Tí nhìn thấy một xâu S, chỉ gồm các loại ký tự: chữ cái in hoa, chữ cái thường và chữ số. Tí muốn tự kiểm tra khả năng đoán nhận mật khẩu bằng cách đếm xem có bao nhiêu cặp chỉ số (i, j) thỏa mãn điều kiện: 1 ≤ i < j ≤ length(S) và xâu con gồm các ký tự liên tiếp từ i đến j của S là mật khẩu “an toàn”.
Cho xâu S, các hãy tính số lượng cặp chỉ số (i, j) thỏa mãn điều kiện nêu trên.
Input
Một dòng chứa xâu S có độ dài <= 10^6.
Output
In ra một số nguyên duy nhất là số cặp chỉ số (i, j) tìm được.
Example
Test 1:
Input:
abc3456789PQ
Output:
6
Test 2:
Input:
abc123
Output:
0
2. Code tham khảo P145PROI PTIT spoj O(n)
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 | program bt; uses math; const fi='; nmax=1000000; var f:text; S:ansistring; n:longint; L:array[1..nmax+1,'1'..'3'] of longint; procedure docfile; var c:char; begin assign(f,fi); reset(f); s:='; while not eoln(f) do begin read(f,c); case c of 'A'..'Z': s:=s+'3'; 'a'..'z': s:=s+'2'; '0'..'9': s:=s+'1'; end; end; close(f); n:=length(s); end; procedure taoL; var i:longint; j:char; begin for j:='1' to '3' do L[n+1,j]:=n+1; for i:=n downto 1 do begin L[i,'1']:=L[i+1,'1']; L[i,'2']:=L[i+1,'2']; L[i,'3']:=L[i+1,'3']; for j:='1' to '3' do if s[i]=j then L[i,j]:=i; end; end; procedure xuli; var i:longint; dem:int64; begin dem:=0; for i:=1 to n-5 do dem:=dem+n-max(max(i+5,L[i,'1']),max(L[i,'2'],L[i,'3']))+1; writeln(dem); end; begin docfile; taoL; xuli; // readln; end. |
