1690.md (6621B)
1 Source: https://codeforces.com/blog/entry/103658 2 3 [1690A - Print a Pedestal (Codeforces logo?)](/contest/1690/problem/A "Codeforces Round 797 (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 <bits/stdc++.h> 15 16 using namespace std; 17 18 #define forn(i, n) for (int i = 0; i < int(n); i++) 19 #define sz(v) (int)v.size() 20 #define all(v) v.begin(),v.end() 21 #define eb emplace_back 22 23 24 25 void solve() { 26 int n; 27 cin >> n; 28 for (int a = 3; a < n; a++) { 29 int c = (n - a) / 2; 30 int b = n - a - c; 31 if (c > 1 && b+1 < a) { 32 c--; 33 b++; 34 } 35 if (a > b && b > c) { 36 cout << b << ' ' << a << ' ' << c << endl; 37 return; 38 } 39 } 40 } 41 42 int main() { 43 int t; 44 cin >> t; 45 46 forn(tt, t) { 47 solve(); 48 } 49 } 50 ``` 51 52 [1690B - Array Decrements](/contest/1690/problem/B "Codeforces Round 797 (Div. 3)") 53 54 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 55 56 **Tutorial** 57 58 Tutorial is loading... 59 60 **Solution** 61 62 ``` 63 #include<bits/stdc++.h> 64 65 #define forn(i, n) for (int i = 0; i < int(n); i++) 66 67 using namespace std; 68 const int inf = 1e9 + 7; 69 70 bool equals(vector<int>&a, vector<int>&b, int n){ 71 int dif = inf; 72 forn(i, n){ 73 if(b[i] != 0) dif = min(dif, a[i] - b[i]); 74 } 75 if(dif < 0) return false; 76 if(dif == inf) return true; 77 forn(i, n){ 78 if(a[i] - b[i] > dif) return false; 79 if(b[i] != 0 && a[i] - b[i] < dif) return false; 80 } 81 return true; 82 } 83 84 void solve(){ 85 int n; 86 cin >> n; 87 vector<int>a(n), b(n); 88 forn(i, n) cin >> a[i]; 89 forn(i, n) cin >> b[i]; 90 cout << (equals(a, b, n) ? "YES\n" : "NO\n"); 91 92 } 93 94 int main(){ 95 int t; 96 cin >> t; 97 while(t--){ 98 solve(); 99 } 100 } 101 ``` 102 103 [1690C - Restoring the Duration of Tasks](/contest/1690/problem/C "Codeforces Round 797 (Div. 3)") 104 105 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 106 107 **Tutorial** 108 109 Tutorial is loading... 110 111 **Solution** 112 113 ``` 114 #include <bits/stdc++.h> 115 116 using namespace std; 117 118 typedef long long ll; 119 120 #define forn(i, n) for (int i = 0; i < int(n); i++) 121 122 123 void solve() { 124 int n; 125 cin >> n; 126 int s[n]; 127 int f[n]; 128 for (int i = 0; i < n; ++i) { 129 cin >> s[i]; 130 } 131 132 for (int i = 0; i < n; ++i) { 133 cin >> f[i]; 134 } 135 int curTime = 0; 136 int d[n]; 137 for (int i = 0; i < n; ++i) { 138 curTime = max(curTime, s[i]); 139 d[i] = f[i] - curTime; 140 curTime = f[i]; 141 } 142 for (auto now: d) { 143 cout << now << " "; 144 } 145 cout << '\n'; 146 } 147 int main() { 148 int tests; 149 cin >> tests; 150 forn(tt, tests) { 151 solve(); 152 } 153 } 154 ``` 155 156 [1690D - Black and White Stripe](/contest/1690/problem/D "Codeforces Round 797 (Div. 3)") 157 158 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 159 160 **Tutorial** 161 162 Tutorial is loading... 163 164 **Solution** 165 166 ``` 167 #include <bits/stdc++.h> 168 169 using namespace std; 170 171 #define forn(i, n) for (int i = 0; i < int(n); i++) 172 173 int main() { 174 int t; 175 cin >> t; 176 forn(tt, t) { 177 int n, k; 178 cin >> n >> k; 179 string s; 180 cin >> s; 181 vector<int> w(n + 1); 182 for (int i = 1; i <= n; i++) 183 w[i] = w[i - 1] + int(s[i - 1] == 'W'); 184 int result = INT_MAX; 185 for (int i = k; i <= n; i++) 186 result = min(result, w[i] - w[i - k]); 187 cout << result << endl; 188 } 189 } 190 ``` 191 192 [1690E - Price Maximization](/contest/1690/problem/E "Codeforces Round 797 (Div. 3)") 193 194 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), [Aris](/profile/Aris "Expert Aris") 195 196 **Tutorial** 197 198 Tutorial is loading... 199 200 **Solution** 201 202 ``` 203 #include<bits/stdc++.h> 204 #define len(s) (int)s.size() 205 using namespace std; 206 using ll = long long; 207 208 void solve(){ 209 int n, k; 210 cin >> n >> k; 211 vector<ll>a(n); 212 ll sum = 0; 213 for(int i = 0; i < n; i++) { 214 cin >> a[i]; 215 sum += a[i] / k; 216 a[i] = a[i] % k; 217 } 218 sort(a.begin(), a.end(), [] (int x, int y){ 219 return x > y; 220 }); 221 222 for(int i = 0, j = n - 1; i < j; i++, j--){ 223 while(a[i] + a[j] < k && i < j) j--; 224 if(i == j) break; 225 sum++; 226 } 227 cout << sum << endl; 228 } 229 230 int main(){ 231 int t; 232 cin >> t; 233 while(t--){ 234 solve(); 235 } 236 return 0; 237 } 238 ``` 239 240 [1690F - Shifting String](/contest/1690/problem/F "Codeforces Round 797 (Div. 3)") 241 242 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 243 244 **Tutorial** 245 246 Tutorial is loading... 247 248 **Solution** 249 250 ``` 251 def gcd(a, b): 252 if b == 0: 253 return a; 254 return gcd(b, a % b) 255 256 257 def shift(s): 258 for i in range(1, len(s) + 1): 259 if s == s[i:] + s[:i]: 260 return i 261 262 263 def solve(): 264 n = int(input()) 265 s = input() 266 p = [int(x)-1 for x in input().split()] 267 used = [False] * n 268 ans = 1 269 i = 0 270 while i < n: 271 ss = '' 272 while not used[i]: 273 ss += s[i] 274 used[i] = True 275 i = p[i]; 276 i += 1 277 if len(ss) == 0: 278 continue 279 ln = shift(ss) 280 ans = ans * ln // gcd(ans, ln) 281 print(ans) 282 283 284 t = int(input()) 285 for _ in range(t): 286 solve() 287 ``` 288 289 [1690G - Count the Trains](/contest/1690/problem/G "Codeforces Round 797 (Div. 3)") 290 291 Idea: [Aris](/profile/Aris "Expert Aris") 292 293 **Tutorial** 294 295 Tutorial is loading... 296 297 **Solution** 298 299 ``` 300 #include<bits/stdc++.h> 301 302 using namespace std; 303 304 int main() { 305 ios_base::sync_with_stdio(0); 306 cin.tie(0); 307 cout.tie(0); 308 int t; 309 cin >> t; 310 while (t--) { 311 int n, m; 312 cin >> n >> m; 313 vector<int> a(n); 314 set<int> tmp; 315 for (int i = 0; i < n; i++) { 316 cin >> a[i]; 317 if (tmp.empty() || a[i] < a[*tmp.rbegin()]) { 318 tmp.insert(i); 319 } 320 } 321 for (int i = 0; i < m; i++) { 322 int j, d; 323 cin >> j >> d; 324 j--; 325 a[j] -= d; 326 auto it = tmp.upper_bound(j); 327 if (it != tmp.begin()) { 328 it = prev(it); 329 if (*it == j || a[*it] > a[j]) { 330 tmp.insert(j); 331 } 332 } else { 333 tmp.insert(j); 334 } 335 while (1) { 336 it = tmp.upper_bound(j); 337 if (it != tmp.end() && a[*it] >= a[j]) { 338 tmp.erase(it); 339 } else { 340 break; 341 } 342 } 343 cout << (int) tmp.size() << " "; 344 } 345 cout << '\n'; 346 } 347 } 348 ```