1373.md (9564B)
1 Source: https://codeforces.com/blog/entry/79376 2 3 [1373A - Donut Shops](/contest/1373/problem/A "Educational Codeforces Round 90 (Rated for Div. 2)") 4 5 Idea: [Roms](/profile/Roms "Master Roms") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (pikmike)** 12 13 ``` 14 for tc in range(int(input())): 15 a, b, c = map(int, input().split()) 16 print(1 if a < c else -1, end=" ") 17 print(b if c < a * b else -1) 18 ``` 19 20 [1373B - 01 Game](/contest/1373/problem/B "Educational Codeforces Round 90 (Rated for Div. 2)") 21 22 Idea: [Roms](/profile/Roms "Master Roms") 23 24 **Tutorial** 25 26 Tutorial is loading... 27 28 **Solution (Roms)** 29 30 ``` 31 for _ in range(int(input())): 32 s = input() 33 print('DA' if min(s.count('0'), s.count('1')) % 2 == 1 else 'NET') 34 ``` 35 36 [1373C - Pluses and Minuses](/contest/1373/problem/C "Educational Codeforces Round 90 (Rated for Div. 2)") 37 38 Idea: [Roms](/profile/Roms "Master Roms") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Solution (Roms)** 45 46 ``` 47 for _ in range(int(input())): 48 s = input() 49 cur, mn, res = 0, 0, len(s) 50 for i in range(len(s)): 51 cur += 1 if s[i] == '+' else -1 52 if cur < mn: 53 mn = cur 54 res += i + 1 55 56 print(res) 57 ``` 58 59 [1373D - Maximum Sum on Even Positions](/contest/1373/problem/D "Educational Codeforces Round 90 (Rated for Div. 2)") 60 61 Idea: [vovuh](/profile/vovuh "Master vovuh") 62 63 **Tutorial** 64 65 Tutorial is loading... 66 67 **Solution (vovuh)** 68 69 ``` 70 #include <bits/stdc++.h> 71 72 using namespace std; 73 74 int main() { 75 #ifdef _DEBUG 76 freopen("input.txt", "r", stdin); 77 // freopen("output.txt", "w", stdout); 78 #endif 79 80 int t; 81 cin >> t; 82 while (t--) { 83 int n; 84 cin >> n; 85 vector<int> a(n); 86 for (auto &it : a) cin >> it; 87 vector<vector<long long>> dp(n + 1, vector<long long>(3)); 88 for (int i = 0; i < n; ++i) { 89 dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + (i & 1 ? 0 : a[i])); 90 if (i + 2 <= n) dp[i + 2][1] = max(dp[i + 2][1], max(dp[i][0], dp[i][1]) + (i & 1 ? a[i] : a[i + 1])); 91 dp[i + 1][2] = max(dp[i + 1][2], max({dp[i][0], dp[i][1], dp[i][2]}) + (i & 1 ? 0 : a[i])); 92 } 93 cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl; 94 } 95 96 return 0; 97 } 98 ``` 99 100 [1373E - Sum of Digits](/contest/1373/problem/E "Educational Codeforces Round 90 (Rated for Div. 2)") 101 102 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 103 104 **Tutorial** 105 106 Tutorial is loading... 107 108 **Solution 1 (BledDest)** 109 110 ``` 111 #include<bits/stdc++.h> 112 113 using namespace std; 114 115 int n, k; 116 117 bool decimalLess(const string& s, const string& t) 118 { 119 if(s.size() != t.size()) 120 return s.size() < t.size(); 121 for(int i = 0; i < s.size(); i++) 122 if(s[i] != t[i]) 123 return s[i] < t[i]; 124 return false; 125 } 126 127 void upd(string& ans, const string& cur) 128 { 129 if(ans == "-1" || decimalLess(cur, ans)) 130 ans = cur; 131 } 132 133 void read() 134 { 135 cin >> n >> k; 136 } 137 138 void solve() 139 { 140 string ans = "-1"; 141 for(int i = 0; i <= 9; i++) 142 { 143 int cnt9 = n / 9; 144 if(i + k < 10) 145 cnt9 = 0; 146 for(int j = 0; j <= cnt9; j++) 147 { 148 if(i + k >= 10 && j == 0) 149 continue; 150 int curSum = (i + (i + k)) * (k + 1) / 2; 151 if(j != 0) 152 { 153 int cntBefore = 10 - i; 154 int cntAfter = k + 1 - cntBefore; 155 curSum = (i + 9) * cntBefore / 2 + cntBefore * 9 * (j - 1) + (1 + cntAfter) * cntAfter / 2; 156 } 157 curSum = n - curSum; 158 if(curSum < 0 || curSum % (k + 1) != 0) 159 continue; 160 string curNum = {char('0' + i)}; 161 for(int z = 0; z < j - 1; z++) 162 curNum += "9"; 163 int maxNum = 9; 164 if(i + k >= 10) 165 maxNum = 8; 166 curSum /= (k + 1); 167 while(curSum != 0) 168 { 169 int d = min(curSum, maxNum); 170 maxNum = 9; 171 curSum -= d; 172 curNum.push_back(char('0' + d)); 173 } 174 reverse(curNum.begin(), curNum.end()); 175 upd(ans, curNum); 176 } 177 } 178 cout << ans << endl; 179 } 180 181 int main() 182 { 183 int t; 184 cin >> t; 185 for(int i = 0; i < t; i++) 186 { 187 read(); 188 solve(); 189 } 190 } 191 ``` 192 193 **Solution 2 (pikmike)** 194 195 ``` 196 def get(s): 197 return str(s % 9) + '9' * (s // 9) 198 199 for tc in range(int(input())): 200 n, k = map(int, input().split()) 201 k += 1 202 bst = 10**100 203 for d in range(10): 204 ends = 0 205 for i in range(k): 206 ends += (d + i) % 10 207 if ends > n: 208 continue 209 if d + k > 10: 210 for cnt in range(12): 211 s = 9 * cnt * (10 - d) 212 if s > n - ends: 213 break 214 for nd in range(9): 215 ns = s + (10 - d) * nd + (k - (10 - d)) * (nd + 1) 216 if ns > n - ends: 217 break 218 if (n - ends - ns) % k == 0: 219 bst = min(bst, int(get((n - ends - ns) // k) + str(nd) + '9' * cnt + str(d))) 220 elif (n - ends) % k == 0: 221 bst = min(bst, int(get((n - ends) // k) + str(d))) 222 print(-1 if bst == 10**100 else bst) 223 ``` 224 225 [1373F - Network Coverage](/contest/1373/problem/F "Educational Codeforces Round 90 (Rated for Div. 2)") 226 227 Idea: [adedalic](/profile/adedalic "International Master adedalic") 228 229 **Tutorial** 230 231 Tutorial is loading... 232 233 **Solution 1 (adedalic)** 234 235 ``` 236 #include<bits/stdc++.h> 237 238 using namespace std; 239 240 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 241 #define sz(a) int((a).size()) 242 243 #define x first 244 #define y second 245 246 typedef long long li; 247 typedef pair<int, int> pt; 248 249 const int INF = int(1e9); 250 const li INF64 = li(1e18); 251 252 int n; 253 vector<int> a, b; 254 255 inline bool read() { 256 if(!(cin >> n)) 257 return false; 258 a.resize(n); 259 fore(i, 0, n) 260 cin >> a[i]; 261 b.resize(n); 262 fore(i, 0, n) 263 cin >> b[i]; 264 return true; 265 } 266 267 struct func { 268 int minx, mink, maxk; 269 func() : minx(0), mink(0), maxk(0) {} 270 func(int minx, int mink, int maxk) : minx(minx), mink(mink), maxk(maxk) {} 271 }; 272 273 func getFunc(int a, int b) { 274 if (a <= b) 275 return func(0, b - a, b); 276 else 277 return func(a - b, 0, b); 278 } 279 280 func merge(func a, func b) { 281 if (a.minx == -1 || b.minx == -1) 282 return func(-1, -1, -1); 283 284 if (a.maxk < b.minx) 285 return func(-1, -1, -1); 286 if (a.mink >= b.minx) 287 return func(a.minx, min(b.maxk, b.mink + (a.mink - b.minx)), min(b.maxk, b.mink + (a.maxk - b.minx))); 288 else { 289 int add = b.minx - a.mink; 290 return func(a.minx + add, b.mink, min(b.maxk, b.mink + (a.maxk - b.minx))); 291 } 292 } 293 294 inline void solve() { 295 func total = getFunc(a[0], b[0]); 296 fore(i, 1, n) 297 total = merge(total, getFunc(a[i], b[i])); 298 299 if (total.minx != -1 && total.minx <= total.mink) 300 cout << "YES\n"; 301 else 302 cout << "NO\n"; 303 } 304 305 int main() { 306 #ifdef _DEBUG 307 freopen("input.txt", "r", stdin); 308 int tt = clock(); 309 #endif 310 ios_base::sync_with_stdio(false); 311 cin.tie(0), cout.tie(0); 312 cout << fixed << setprecision(15); 313 314 int tc; cin >> tc; 315 316 while(tc--) { 317 read(); 318 solve(); 319 320 #ifdef _DEBUG 321 cerr << "TIME = " << clock() - tt << endl; 322 tt = clock(); 323 #endif 324 } 325 return 0; 326 } 327 ``` 328 329 **Solution 2 (Ne0n25)** 330 331 ``` 332 #include <bits/stdc++.h> 333 334 using namespace std; 335 336 typedef long long li; 337 const int N = 1000 * 1000 + 13; 338 339 int n; 340 int a[N], b[N]; 341 342 void solve() { 343 scanf("%d", &n); 344 for (int i = 0; i < n; ++i) scanf("%d", &a[i]); 345 for (int i = 0; i < n; ++i) scanf("%d", &b[i]); 346 347 li need = 0, add = 0, extra = 2e9; 348 for (int i = n - 1; i >= 0; --i) { 349 if (b[i] < need) { 350 puts("NO"); 351 return; 352 } 353 354 li val = b[i] - a[i]; 355 li to_add = min(extra, max(0LL, val - need)); 356 add += to_add; 357 extra = min(extra - to_add, b[i] - need - to_add); 358 need = max(0LL, need - val); 359 } 360 361 puts(add >= need ? "YES" : "NO"); 362 } 363 364 int main() { 365 int t; 366 scanf("%d", &t); 367 for (int i = 0; i < t; ++i) 368 solve(); 369 } 370 ``` 371 372 [1373G - Pawns](/contest/1373/problem/G "Educational Codeforces Round 90 (Rated for Div. 2)") 373 374 Idea: [Roms](/profile/Roms "Master Roms") and [BledDest](/profile/BledDest "International Grandmaster BledDest") 375 376 **Tutorial** 377 378 Tutorial is loading... 379 380 **Solution (Roms)** 381 382 ``` 383 #include <bits/stdc++.h> 384 385 using namespace std; 386 387 const int N = int(2e5) + 9; 388 389 int n, k; 390 int m; 391 int t[8 * N]; 392 int add[8 * N]; 393 int cnt[2 * N]; 394 395 void push(int v, int l, int r) { 396 if (r - l != 1 && add[v] != 0) { 397 t[v * 2 + 1] += add[v]; 398 t[v * 2 + 2] += add[v]; 399 add[v * 2 + 1] += add[v]; 400 add[v * 2 + 2] += add[v]; 401 add[v] = 0; 402 } 403 } 404 405 void upd(int v, int l, int r, int L, int R, int x) { 406 if (L >= R) return; 407 if(l == L && r == R) { 408 t[v] += x; 409 add[v] += x; 410 return; 411 } 412 413 push(v, l, r); 414 int mid = (l + r) / 2; 415 upd(v * 2 + 1, l, mid, L, min(R, mid), x); 416 upd(v * 2 + 2, mid, r, max(L, mid), R, x); 417 t[v] = max(t[v * 2 + 1], t[v * 2 + 2]); 418 } 419 420 void upd(int l, int r, int x) { 421 upd(0, 0, n + n, l, r, x); 422 } 423 424 int get(int v, int l, int r, int L, int R) { 425 if (L >= R) return 0; 426 if (l == L && r == R) return t[v]; 427 428 push(v, l, r); 429 int mid = (l + r) >> 1; 430 return max(get(v * 2 + 1, l, mid, L, min(R, mid)) 431 , get(v * 2 + 2, mid, r, max(L, mid), R)); 432 } 433 434 int get(int l, int r) { 435 return get(0, 0, n + n, l, r); 436 } 437 438 int getAns(set <int> &smx) { 439 if (smx.empty()) return 0; 440 return max(0, get(0, *smx.rbegin() + 1) - n); 441 } 442 443 void build(int v, int l, int r) { 444 if (r - l == 1) { 445 t[v] = l; 446 return; 447 } 448 449 int mid = (l + r) >> 1; 450 build(v * 2 + 1, l, mid); 451 build(v * 2 + 2, mid, r); 452 t[v] = max(t[v * 2 + 1], t[v * 2 + 2]); 453 } 454 455 int main(){ 456 scanf("%d %d %d", &n, &k, &m); 457 458 build(0, 0, n + n); 459 set <pair<int, int> > s; 460 set <int> smx; 461 for (int i = 0; i < m; ++i) { 462 int x, y; 463 scanf("%d %d", &x, &y); 464 int pos = abs(x - k) + y - 1; 465 pair <int, int> p = make_pair(x, y); 466 if (s.count(p)) { 467 --cnt[pos]; 468 if (cnt[pos] == 0) smx.erase(pos); 469 upd(0, pos + 1, -1); 470 s.erase(p); 471 } else { 472 ++cnt[pos]; 473 if (cnt[pos] == 1) smx.insert(pos); 474 upd(0, pos + 1, 1); 475 s.insert(p); 476 } 477 478 printf("%d\n", getAns(smx)); 479 } 480 return 0; 481 } 482 ```