//Autor: Mateusz Wasylkiewicz //Zawody: Potyczki Algorytmiczne 2018 //Strona: http://potyczki.mimuw.edu.pl/ //Zadanie: Jezyk polski, runda 1B //Czas: Theta(WEJSCIE) #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL, LL> PII; #define FOR(x, a, b) for (LL x = (a); x <= (b); x++) #define REP(x, n) for (LL x = 0; x < (n); x++) #define SIZE(x) LL((x).size()) #define ST first #define ND second const LL MAX = 200100, K = 26; const string samogloski = "aeiouy"; LL n, trojka_roz; bool samogloska[K]; PII trojka[MAX]; string s; void wczytaj_dane() { cin >> s; n = SIZE(s); } inline LL numer(char z) { return LL(z) - LL('a'); } void wypelnij_samogloska() { fill(samogloska, samogloska + K, false); REP(i, SIZE(samogloski)) samogloska[numer(samogloski[i])] = true; } void wypelnij_trojka() { trojka_roz = 0; trojka[trojka_roz++] = PII(0, 1); bool ostatni = samogloska[numer(s[0])]; LL pocz = 0, licz = 1; FOR(i, 1, n - 1) { if (samogloska[numer(s[i])] != ostatni) { if (licz >= 3) trojka[trojka_roz++] = PII(pocz, i - 1); ostatni = samogloska[numer(s[i])]; pocz = i; licz = 0; } licz++; } if (licz >= 3) trojka[trojka_roz++] = PII(pocz, n - 1); trojka[trojka_roz++] = PII(n - 2, n - 1); } inline LL liczba_podslow(LL a, LL b) { LL d = b - a + 1; return d * (d + 1) / 2; } LL rozwiaz() { LL wynik = liczba_podslow(0, n - 1); FOR(i, 0, trojka_roz - 2) wynik -= liczba_podslow(trojka[i].ND - 1, trojka[i + 1].ST + 1); FOR(i, 1, trojka_roz - 2) wynik -= 2 * (trojka[i].ND - trojka[i].ST) - 5; return wynik; } void zrob_test() { wczytaj_dane(); wypelnij_samogloska(); wypelnij_trojka(); cout << rozwiaz() << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); zrob_test(); 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 | //Autor: Mateusz Wasylkiewicz //Zawody: Potyczki Algorytmiczne 2018 //Strona: http://potyczki.mimuw.edu.pl/ //Zadanie: Jezyk polski, runda 1B //Czas: Theta(WEJSCIE) #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL, LL> PII; #define FOR(x, a, b) for (LL x = (a); x <= (b); x++) #define REP(x, n) for (LL x = 0; x < (n); x++) #define SIZE(x) LL((x).size()) #define ST first #define ND second const LL MAX = 200100, K = 26; const string samogloski = "aeiouy"; LL n, trojka_roz; bool samogloska[K]; PII trojka[MAX]; string s; void wczytaj_dane() { cin >> s; n = SIZE(s); } inline LL numer(char z) { return LL(z) - LL('a'); } void wypelnij_samogloska() { fill(samogloska, samogloska + K, false); REP(i, SIZE(samogloski)) samogloska[numer(samogloski[i])] = true; } void wypelnij_trojka() { trojka_roz = 0; trojka[trojka_roz++] = PII(0, 1); bool ostatni = samogloska[numer(s[0])]; LL pocz = 0, licz = 1; FOR(i, 1, n - 1) { if (samogloska[numer(s[i])] != ostatni) { if (licz >= 3) trojka[trojka_roz++] = PII(pocz, i - 1); ostatni = samogloska[numer(s[i])]; pocz = i; licz = 0; } licz++; } if (licz >= 3) trojka[trojka_roz++] = PII(pocz, n - 1); trojka[trojka_roz++] = PII(n - 2, n - 1); } inline LL liczba_podslow(LL a, LL b) { LL d = b - a + 1; return d * (d + 1) / 2; } LL rozwiaz() { LL wynik = liczba_podslow(0, n - 1); FOR(i, 0, trojka_roz - 2) wynik -= liczba_podslow(trojka[i].ND - 1, trojka[i + 1].ST + 1); FOR(i, 1, trojka_roz - 2) wynik -= 2 * (trojka[i].ND - trojka[i].ST) - 5; return wynik; } void zrob_test() { wczytaj_dane(); wypelnij_samogloska(); wypelnij_trojka(); cout << rozwiaz() << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); zrob_test(); return 0; } |