#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; } |
English