#include <string> #include <vector> #include <algorithm> #include <cmath> #include <set> #include <map> #include <cstdio> #include <sstream> #include <iostream> #include <cstring> #define REP(i,x,v)for(int i=x;i<=v;i++) #define REPD(i,x,v)for(int i=x;i>=v;i--) #define FOR(i,v)for(int i=0;i<v;i++) #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define pb push_back #define sz size() #define mp make_pair #define fi first #define se second #define ll long long #define IN(x,y) ((y).find((x))!=(y).end()) #define LOLDBG #ifdef LOLDBG #define DBG(vari) cout<<#vari<<" = "<<vari<<endl; #define DBG2(v1,v2) cout<<(v1)<<" - "<<(v2)<<endl; #else #define DBG(vari) #define DBG2(v1,v2) #endif #define CZ(x) scanf("%d",&(x)); #define CZ2(x,y) scanf("%d%d",&(x),&(y)); #define ALL(x) (x).begin(),(x).end() #include <random> using namespace std; typedef pair<int,int> pii; typedef vector<int> vi; template<typename T,typename TT> ostream &operator<<(ostream &s,pair<T,TT> t) {return s<<"("<<t.first<<","<<t.second<<")";} template<typename T> ostream &operator<<(ostream &s,vector<T> t){s<<"{";FOR(i,t.size())s<<t[i]<<(i==t.size()-1?"":",");return s<<"}"<<endl; } int sam[333]; bool is_good(string s) { int n=s.sz; FOR(i,n-2) { if (sam[i]==sam[i+1] && sam[i+1]==sam[i+2]) return 0; } return 1; } ll count_bad_slow(string s) { int n=s.sz; ll cnt = 0; FOR(i,n+1)FOR(j,i) { if (!is_good(s.substr(j,i-j))) cnt++; } return cnt; } ll count_bad(string s) { int last_bad = -1; int cnt_bad = 0; ll n = s.sz; ll res = n*(n+1)/2; ll good = 0; FOR(i,n) { if (i==0) cnt_bad=1; else { if (sam[s[i]]==sam[s[i-1]]) cnt_bad++; else cnt_bad=1; } if (cnt_bad>=3) last_bad = i-2; good += (i-last_bad); } return res-good; } int main2() { mt19937 rng(1234); FOR(sggd,10000000) { string s; int n=1+rng()%10; FOR(i,n) s+='a'+rng()%26; if (count_bad(s)!=count_bad_slow(s)) { DBG(s); DBG(count_bad(s)); DBG(count_bad_slow(s)); return 0; } } } int main() { ios_base::sync_with_stdio(0); string samo = "aeiouy"; FOR(i,samo.sz) sam[samo[i]] = 1; string s; cin>>s; cout<<count_bad(s)<<"\n"; return 0; }
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | #include <string> #include <vector> #include <algorithm> #include <cmath> #include <set> #include <map> #include <cstdio> #include <sstream> #include <iostream> #include <cstring> #define REP(i,x,v)for(int i=x;i<=v;i++) #define REPD(i,x,v)for(int i=x;i>=v;i--) #define FOR(i,v)for(int i=0;i<v;i++) #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define pb push_back #define sz size() #define mp make_pair #define fi first #define se second #define ll long long #define IN(x,y) ((y).find((x))!=(y).end()) #define LOLDBG #ifdef LOLDBG #define DBG(vari) cout<<#vari<<" = "<<vari<<endl; #define DBG2(v1,v2) cout<<(v1)<<" - "<<(v2)<<endl; #else #define DBG(vari) #define DBG2(v1,v2) #endif #define CZ(x) scanf("%d",&(x)); #define CZ2(x,y) scanf("%d%d",&(x),&(y)); #define ALL(x) (x).begin(),(x).end() #include <random> using namespace std; typedef pair<int,int> pii; typedef vector<int> vi; template<typename T,typename TT> ostream &operator<<(ostream &s,pair<T,TT> t) {return s<<"("<<t.first<<","<<t.second<<")";} template<typename T> ostream &operator<<(ostream &s,vector<T> t){s<<"{";FOR(i,t.size())s<<t[i]<<(i==t.size()-1?"":",");return s<<"}"<<endl; } int sam[333]; bool is_good(string s) { int n=s.sz; FOR(i,n-2) { if (sam[i]==sam[i+1] && sam[i+1]==sam[i+2]) return 0; } return 1; } ll count_bad_slow(string s) { int n=s.sz; ll cnt = 0; FOR(i,n+1)FOR(j,i) { if (!is_good(s.substr(j,i-j))) cnt++; } return cnt; } ll count_bad(string s) { int last_bad = -1; int cnt_bad = 0; ll n = s.sz; ll res = n*(n+1)/2; ll good = 0; FOR(i,n) { if (i==0) cnt_bad=1; else { if (sam[s[i]]==sam[s[i-1]]) cnt_bad++; else cnt_bad=1; } if (cnt_bad>=3) last_bad = i-2; good += (i-last_bad); } return res-good; } int main2() { mt19937 rng(1234); FOR(sggd,10000000) { string s; int n=1+rng()%10; FOR(i,n) s+='a'+rng()%26; if (count_bad(s)!=count_bad_slow(s)) { DBG(s); DBG(count_bad(s)); DBG(count_bad_slow(s)); return 0; } } } int main() { ios_base::sync_with_stdio(0); string samo = "aeiouy"; FOR(i,samo.sz) sam[samo[i]] = 1; string s; cin>>s; cout<<count_bad(s)<<"\n"; return 0; } |