nq1s788

проверка на а-хорошесть

Aug 4th, 2026
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <set>
  6. #include <map>
  7.  
  8. #define fi first
  9. #define se second
  10. #define pb push_back
  11.  
  12. typedef long long ll;
  13.  
  14. using namespace std;
  15.  
  16. string s;
  17.  
  18. bool test(int l, int r, char c) { ///передаем границы подстроки, если передавать строку то оч много памяти уйдет на создание копий
  19.     if (r - l == 1) { ///выход из рекурсии, если длина 1 то просто проверяем что в ней нужный символ
  20.         return (s[l] == c);
  21.     }
  22.     int cnt_c = 0;
  23.     int m = (l + r) / 2;
  24.     for (int i = l; i < m; i++) { ///считаем кол-во букв c в левой половине
  25.         if (s[i] == c) cnt_c++;
  26.     }
  27.     if (cnt_c == m - l) { //если левая из c тогда проверяем что правая c+1 хорошая
  28.         return test(m, r, c+1);
  29.     }
  30.     cnt_c = 0;
  31.     for (int i = m; i < r; i++) { ///считаем кол-во букв c в правой половине
  32.         if (s[i] == c) cnt_c++;
  33.     }
  34.     if (cnt_c == r - m) { //если правая из c тогда проверяем что правая c+1 хорошая
  35.         return test(l, m, c+1);
  36.     }
  37.     return false;
  38. }
  39.  
  40. int main() {
  41.     cin >> s;
  42.     if (test(0, (int)s.size(), 'a')) cout << "YES" << endl;
  43.     else cout << "NO" << endl;
  44.     return 0;
  45. }
Advertisement
Add Comment
Please, Sign In to add comment