Hydron

UOI_III_stage_I_task_B

Feb 10th, 2022 (edited)
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.22 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll; /// Заміняємо long long на ll, бо по-перше, так менше писати, а по-друге я привик писати ll скрізь і тепер просто впадлу виправляти написаний код :)
  6.  
  7. int main(){
  8.     ll n; string s;
  9.     cin >> n >> s;
  10.     /**
  11.     По суті, коло означає, що після останнього елемента рядка іде перший.
  12.     Тобто, йдучи по колу, ми будемо нескінченну кількість разів проходити по нашому рядку.
  13.     Але нам не потрібна нескінченність (Бо це трохи довго:) )
  14.     Натомість, помітимо, що відповідь не може бути більшою ніж довжина рядка (Ну бо ти не зможеш обрати підрядок довший, ніж увесь рядок)
  15.     Отже, нам достатньо виписати заданий рядок двічі (Бо таким чином ми зможемо починаючи з кожної позиції рядка побудувати підрядок довжини n)
  16.     **/
  17.     s += s; /// Дописали до кінця радка його ж (Наприклад, "abcd" -> "abcdabcd")
  18.  
  19.     /**
  20.     Тепер рішаємо задачу не для кола, а для рядка
  21.     Нам тре найти найдовший підрядок такий, шо для кожного <i> : s[i] == s[i-1]+1
  22.     Для кожного символу будемо пробувати дописувати його до найдовшого такого підрядка, який закінчується на попередньому символі.
  23.     **/
  24.     ll answer = 1, current_length = 1;
  25.     for (ll i=1; i<s.length(); i++){
  26.         if (s[i] == char(s[i-1] + 1)) current_length ++; /// Якщо можемо дописати - довжина ++
  27.         else current_length = 1; /// Інакше довжина знову 1
  28.         answer = max(answer, current_length);
  29.     }
  30.     cout << answer << '\n';
  31.     return 0;
  32. }
  33.  
Add Comment
Please, Sign In to add comment