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ụ, ‘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)

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.