1660.md (6109B)
1 Source: https://codeforces.com/blog/entry/101526 2 3 [1660A - Vasya and Coins](/contest/1660/problem/A "Codeforces Round 780 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <iostream> 15 #include <vector> 16 #include <algorithm> 17 #include <set> 18 19 using namespace std; 20 21 int main() { 22 int t; 23 cin >> t; 24 for (int it = 0; it < t; ++it) { 25 int a, b; 26 cin >> a >> b; 27 cout << (a == 0 ? 1 : a + 2 * b + 1) << '\n'; 28 } 29 return 0; 30 } 31 ``` 32 33 [1660B - Vlad and Candies](/contest/1660/problem/B "Codeforces Round 780 (Div. 3)") 34 35 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 36 37 **Tutorial** 38 39 Tutorial is loading... 40 41 **Solution** 42 43 ``` 44 t = int(input()) 45 for _ in range(t): 46 n = int(input()) 47 a = [int(x) for x in input().split()] 48 a.sort() 49 if n == 1: 50 if a[0] > 1: 51 print("NO") 52 else: 53 print("YES") 54 continue 55 if a[-2] + 1 < a[-1]: 56 print("NO") 57 else: 58 print("YES") 59 ``` 60 61 [1660C - Get an Even String](/contest/1660/problem/C "Codeforces Round 780 (Div. 3)") 62 63 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 64 65 **Tutorial** 66 67 Tutorial is loading... 68 69 **Solution** 70 71 ``` 72 #include<bits/stdc++.h> 73 using namespace std; 74 int sz = 26; 75 76 void solve(){ 77 string s; 78 cin >> s; 79 int m = 0, n = (int)s.size(); 80 vector<bool>prev(sz, false); 81 for(auto &i : s){ 82 if(prev[i - 'a']){ 83 m += 2; 84 for(int j = 0; j < sz; j++) prev[j] = false; 85 } 86 else prev[i - 'a'] = true; 87 } 88 89 cout << n - m << endl; 90 } 91 92 int main(){ 93 int t; 94 cin >> t; 95 while (t--){ 96 solve(); 97 } 98 } 99 ``` 100 101 [1660D - Maximum Product Strikes Back](/contest/1660/problem/D "Codeforces Round 780 (Div. 3)") 102 103 Idea: [Aris](/profile/Aris "Candidate Master Aris") 104 105 **Tutorial** 106 107 Tutorial is loading... 108 109 **Solution** 110 111 ``` 112 #include <bits/stdc++.h> 113 114 using namespace std; 115 116 #define forn(i, n) for (int i = 0; i < int(n); i++) 117 #define sz(v) (int)v.size() 118 119 120 void solve() { 121 int n; cin >> n; 122 vector<int> a(n); 123 124 forn(i, n) 125 cin >> a[i]; 126 int ans = 0; 127 int ap = n, as = 0; 128 for(int i = 0, l = -1; i <= n; i++) { 129 if (i == n || a[i] == 0) { 130 int cnt = 0; 131 bool neg = false; 132 int left = -1, right = -1; 133 int cl = 0, cr = 0; 134 for (int j = l+1; j < i; j++) { 135 neg ^= a[j] < 0; 136 if (a[j] < 0) { 137 right = j; 138 cr = 0; 139 } 140 141 if (abs(a[j]) == 2) { 142 cnt++, cr++; 143 if (left == -1) cl++; 144 } 145 146 if (a[j] < 0 && left == -1) { 147 left = j; 148 } 149 } 150 if (neg) { 151 if (cnt - cl > cnt - cr) { 152 right = i; 153 cnt -= cl; 154 } else { 155 left = l; 156 cnt -= cr; 157 } 158 } else { 159 left = l, right = i; 160 } 161 if (ans < cnt) { 162 ans = cnt; 163 ap = left + 1, as = n - right; 164 } 165 166 l = i; 167 } 168 } 169 cout << ap << ' ' << as << endl; 170 } 171 172 int main() { 173 int t; 174 cin >> t; 175 176 forn(tt, t) { 177 solve(); 178 } 179 } 180 ``` 181 182 [1660E - Matrix and Shifts](/contest/1660/problem/E "Codeforces Round 780 (Div. 3)") 183 184 Idea: [myav](/profile/myav "Pupil myav"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 185 186 **Tutorial** 187 188 Tutorial is loading... 189 190 **Solution** 191 192 ``` 193 #include <bits/stdc++.h> 194 195 using namespace std; 196 197 #define forn(i, n) for (int i = 0; i < int(n); i++) 198 #define sz(v) (int)v.size() 199 #define all(v) v.begin(),v.end() 200 #define eb emplace_back 201 202 const int INF = INT_MAX >> 1; 203 204 void solve() { 205 int n; cin >> n; 206 int cnt1 = 0; 207 vector<int> cnt (n, 0); 208 for (int i = 0; i < n; i++) { 209 string s; cin >> s; 210 for (int j = 0, k = (n - i) % n; j < n; j++, k = (k + 1 == n ? 0 : k + 1)) if (s[j] == '1') { 211 cnt1++; 212 cnt[k]++; 213 } 214 } 215 int ans = INF; 216 for (int i = 0; i < sz(cnt); i++) { 217 ans = min(ans, cnt1 - cnt[i] + (n - cnt[i])); 218 } 219 cout << ans << endl; 220 } 221 222 int main() { 223 int t; 224 cin >> t; 225 226 forn(tt, t) { 227 solve(); 228 } 229 } 230 ``` 231 232 [1660F1 - Promising String (easy version)](/contest/1660/problem/F1 "Codeforces Round 780 (Div. 3)") 233 234 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 235 236 **Tutorial** 237 238 Tutorial is loading... 239 240 **Solution** 241 242 ``` 243 tst = int(input()) 244 for _ in range(tst): 245 n = int(input()) 246 s = input() 247 b = [0 for i in range(n+1)] 248 bal = n 249 b[0] = bal 250 ans = 0 251 for i in range(1,n+1): 252 if s[i-1] == '+': 253 bal += 1 254 else: 255 bal -= 1 256 b[i] = bal 257 for j in range(i): 258 if b[j] >= b[i] and (b[j] - b[i]) % 3 == 0: 259 ans += 1 260 print(ans) 261 ``` 262 263 [1660F2 - Promising String (hard version)](/contest/1660/problem/F2 "Codeforces Round 780 (Div. 3)") 264 265 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 266 267 **Tutorial** 268 269 Tutorial is loading... 270 271 **Solution** 272 273 ``` 274 tst = int(input()) 275 for _ in range(tst): 276 n = int(input()) 277 s = input() 278 f = [0 for i in range(3)] 279 cur_bal = n 280 cnt_bal = [0 for i in range(2 * n + 1)] 281 cnt_bal[cur_bal] += 1 282 f[cur_bal % 3] += 1 283 ans = 0 284 for i in range(n): 285 #print(f) 286 #print(cur_bal, ans) 287 new_bal = cur_bal 288 if s[i] == '-': 289 new_bal -= 1 290 f[new_bal % 3] += cnt_bal[new_bal] 291 ans += f[new_bal % 3] 292 cnt_bal[new_bal] += 1 293 f[new_bal % 3] += 1 294 else: 295 f[new_bal % 3] -= cnt_bal[new_bal] 296 new_bal += 1 297 ans += f[new_bal % 3] 298 cnt_bal[new_bal] += 1 299 f[new_bal % 3] += 1 300 cur_bal = new_bal 301 print(ans) 302 ```