| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P145PROI - ROUND 5I - Mật khẩu |
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
| Được gửi lên bởi: | adm |
| Ngày: | 2014-03-05 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2023-10-27 07:13:20
// O(2*n)~O(n) #include <bits/stdc++.h> using namespace std; typedef long long ll; void solve() { //initialize string s; cin>>s; ll S=0,n=s.size(),l=0; vector<ll>s1(n+1,0),s2(n+1,0),s3(n+1,0); //solve if(n<5) cout<<0; else { for(ll i=1;i<=n;i++) { s1[i]=s1[i-1]; s2[i]=s2[i-1]; s3[i]=s3[i-1]; if(s[i-1]>='a' && s[i-1]<='z') s1[i]++; if(s[i-1]>='A' && s[i-1]<='Z') s2[i]++; if(s[i-1]>='0' && s[i-1]<='9') s3[i]++; } for(ll i=6;i<=n;i++) { ll x=s1[i]-s1[l],y=s2[i]-s2[l],z=s3[i]-s3[l]; //cout<<x<<" "<<y<<" "<<z<<'\n'; while(x && y && z && (i-l)>=6) { l++; x=s1[i]-s1[l],y=s2[i]-s2[l],z=s3[i]-s3[l]; } S+=l; //cout<<l<<" "; } cout<<S; } } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); if(fopen("MATKHAU.inp","r")) { freopen("MATKHAU.inp","r",stdin); freopen("MATKHAU.out","w",stdout); } solve(); } |
|
|
2017-08-20 19:33:25 Con Bò Huyền Thoại
https://kienthuc24h.com/p145proi-ptit-spoj-round-5i-mat-khau/ |
|
|
2017-08-06 19:07:51
P145PROI: https://e16cn-ptit.blogspot.com/2017/12/p145proi-round-5i-mat-khau.html Last edit: 2017-12-14 00:23:15 |
|
|
2016-03-30 04:18:26
FUNCTION KT: BOOLEAN; begin if (dem['1']*dem['2']*dem['3']=0) or (d>c-5) then exit(false); if (dem['1']*dem['2']*dem['3']<>0) and (d<=c-5) then exit(true); end; ////////////////////////////////////////////////// PROCEDURE GIAI; begin kq:=0; d:=1;c:=0; fillchar(dem,sizeof(dem),0); while c<=n do begin if not kt then begin if c=n then exit; inc(c); inc(dem[s[c]]); end; if kt then begin kq:=kq+n-c+1; dec(dem[s[d]]); inc(d); end; end; end; |
|
|
2015-10-10 03:44:16 Anh Vu
sao không có ngôn ngữ pascal nhỉ? |
|
|
2015-05-05 18:45:53 Nguyễn Vĩnh Thịnh
ec nhầm Last edit: 2015-05-05 18:49:30 |
|
|
2015-05-03 17:33:17 Con Bò Huyền Thoại
Last edit: 2017-08-20 19:33:31 |
|
|
2014-12-20 16:17:02 X-Dante
để ý solve = long long :v |
|
|
2014-05-16 17:33:35 Trần Vãn Dương D10CN2
O(N)Bài này dùng quy hoạch động |
