1766.md (7931B)
1 Source: https://codeforces.com/blog/entry/110066 2 3 [1766A - Extremely Round](/contest/1766/problem/A "Educational Codeforces Round 139 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 def check(x): 15 s = str(x) 16 cnt = 0 17 for c in s: 18 if c != '0': 19 cnt += 1 20 return cnt == 1 21 22 a = [] 23 for i in range(1, 1000000): 24 if check(i): 25 a.append(i) 26 t = int(input()) 27 for i in range(t): 28 n = int(input()) 29 ans = 0 30 for x in a: 31 if x <= n: 32 ans += 1 33 print(ans) 34 ``` 35 36 [1766B - Notepad#](/contest/1766/problem/B "Educational Codeforces Round 139 (Rated for Div. 2)") 37 38 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 39 40 **Tutorial** 41 42 Tutorial is loading... 43 44 **Solution (awoo)** 45 46 ``` 47 for _ in range(int(input())): 48 n = int(input()) 49 s = input() 50 cur = {} 51 for i in range(n - 1): 52 t = s[i:i+2] 53 if t in cur: 54 if cur[t] < i - 1: 55 print("YES") 56 break 57 else: 58 cur[t] = i 59 else: 60 print("NO") 61 ``` 62 63 [1766C - Hamiltonian Wall](/contest/1766/problem/C "Educational Codeforces Round 139 (Rated for Div. 2)") 64 65 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 66 67 **Tutorial** 68 69 Tutorial is loading... 70 71 **Solution (awoo)** 72 73 ``` 74 for _ in range(int(input())): 75 n = int(input()) 76 s = [input() for i in range(2)] 77 pos = -1 78 for i in range(n): 79 if s[0][i] != s[1][i]: 80 pos = i 81 if pos == -1: 82 print("YES") 83 continue 84 ok = True 85 cur = 0 if s[0][pos] == 'B' else 1 86 for i in range(pos + 1, n): 87 if s[cur][i] == 'W': 88 ok = False 89 if s[cur ^ 1][i] == 'B': 90 cur ^= 1 91 cur = 0 if s[0][pos] == 'B' else 1 92 for i in range(pos - 1, -1, -1): 93 if s[cur][i] == 'W': 94 ok = False 95 if s[cur ^ 1][i] == 'B': 96 cur ^= 1 97 print("YES" if ok else "NO") 98 ``` 99 100 [1766D - Lucky Chains](/contest/1766/problem/D "Educational Codeforces Round 139 (Rated for Div. 2)") 101 102 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 103 104 **Tutorial** 105 106 Tutorial is loading... 107 108 **Solution (adedalic)** 109 110 ``` 111 #include<bits/stdc++.h> 112 113 using namespace std; 114 115 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 116 #define sz(a) int((a).size()) 117 118 typedef long long li; 119 120 const int INF = int(1e9); 121 const int N = int(1e7) + 5; 122 123 int mind[N]; 124 125 void precalc() { 126 fore (i, 0, N) 127 mind[i] = i; 128 129 for (int p = 2; p < N; p++) { 130 if (mind[p] != p) 131 continue; 132 for (int d = 2 * p; d < N; d += p) 133 mind[d] = min(mind[d], p); 134 } 135 } 136 137 int x, y; 138 139 inline bool read() { 140 if(!(cin >> x >> y)) 141 return false; 142 return true; 143 } 144 145 vector<int> getPrimes(int v) { 146 vector<int> ps; 147 while (v > 1) { 148 if (ps.empty() || ps.back() != mind[v]) 149 ps.push_back(mind[v]); 150 v /= mind[v]; 151 } 152 return ps; 153 } 154 155 inline void solve() { 156 int d = y - x; 157 if (d == 1) { 158 cout << -1 << '\n'; 159 return; 160 } 161 162 int r = INF; 163 for (int p : getPrimes(d)) 164 r = min(r, ((x + p - 1) / p) * p); 165 cout << r - x << '\n'; 166 } 167 168 int main() { 169 #ifdef _DEBUG 170 freopen("input.txt", "r", stdin); 171 int tt = clock(); 172 #endif 173 ios_base::sync_with_stdio(false); 174 cin.tie(0), cout.tie(0); 175 cout << fixed << setprecision(15); 176 177 precalc(); 178 179 int t; cin >> t; 180 while (t--) { 181 read(); 182 solve(); 183 184 #ifdef _DEBUG 185 cerr << "TIME = " << clock() - tt << endl; 186 tt = clock(); 187 #endif 188 } 189 return 0; 190 } 191 ``` 192 193 [1766E - Decomposition](/contest/1766/problem/E "Educational Codeforces Round 139 (Rated for Div. 2)") 194 195 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 196 197 **Tutorial** 198 199 Tutorial is loading... 200 201 **Solution (BledDest)** 202 203 ``` 204 #include<bits/stdc++.h> 205 206 using namespace std; 207 208 const int N = 300043; 209 210 int n; 211 int v[N]; 212 map<vector<int>, long long> dp[N]; 213 214 pair<int, vector<int>> go(vector<int> a, int x) 215 { 216 if(x == 0) 217 return {1, a}; 218 else 219 { 220 bool f = false; 221 for(int i = 0; i < a.size() && !f; i++) 222 if((a[i] & x) > 0) 223 { 224 f = true; 225 a[i] = x; 226 } 227 int c = 0; 228 if(!f) 229 { 230 c = 1; 231 a.push_back(x); 232 } 233 return {c, a}; 234 } 235 } 236 237 long long calc(int i, vector<int> a) 238 { 239 if(i == n) return 0ll; 240 if(dp[i].count(a)) return dp[i][a]; 241 auto p = go(a, v[i]); 242 return (dp[i][a] = p.first * 1ll * (n - i) + calc(i + 1, p.second)); 243 } 244 245 int main() 246 { 247 scanf("%d", &n); 248 for(int i = 0; i < n; i++) scanf("%d", &v[i]); 249 long long ans = 0; 250 for(int i = 0; i < n; i++) 251 ans += calc(i, vector<int>(0)); 252 printf("%lld\n", ans); 253 } 254 ``` 255 256 [1766F - MCF](/contest/1766/problem/F "Educational Codeforces Round 139 (Rated for Div. 2)") 257 258 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 259 260 **Tutorial** 261 262 Tutorial is loading... 263 264 **Solution (BledDest)** 265 266 ``` 267 #include <bits/stdc++.h> 268 269 using namespace std; 270 271 const int N = 243; 272 273 struct edge 274 { 275 int y, c, w, f; 276 edge() {}; 277 edge(int y, int c, int w, int f) : y(y), c(c), w(w), f(f) {}; 278 }; 279 280 vector<edge> e; 281 vector<int> g[N]; 282 283 int rem(int x) 284 { 285 return e[x].c - e[x].f; 286 } 287 288 void add_edge(int x, int y, int c, int w) 289 { 290 g[x].push_back(e.size()); 291 e.push_back(edge(y, c, w, 0)); 292 g[y].push_back(e.size()); 293 e.push_back(edge(x, 0, -w, 0)); 294 } 295 296 int n, m, s, t, v; 297 298 pair<int, long long> MCMF() 299 { 300 int flow = 0; 301 long long cost = 0; 302 while(true) 303 { 304 vector<long long> d(v, (long long)(1e18)); 305 vector<int> p(v, -1); 306 vector<int> pe(v, -1); 307 queue<int> q; 308 vector<bool> inq(v); 309 q.push(s); 310 inq[s] = true; 311 d[s] = 0; 312 while(!q.empty()) 313 { 314 int k = q.front(); 315 q.pop(); 316 inq[k] = false; 317 for(auto ei : g[k]) 318 { 319 if(rem(ei) == 0) continue; 320 int to = e[ei].y; 321 int w = e[ei].w; 322 if(d[to] > d[k] + w) 323 { 324 d[to] = d[k] + w; 325 p[to] = k; 326 pe[to] = ei; 327 if(!inq[to]) 328 { 329 inq[to] = true; 330 q.push(to); 331 } 332 } 333 } 334 } 335 if(p[t] == -1 || d[t] >= 0) break; 336 flow++; 337 cost += d[t]; 338 int cur = t; 339 while(cur != s) 340 { 341 e[pe[cur]].f++; 342 e[pe[cur] ^ 1].f--; 343 cur = p[cur]; 344 } 345 } 346 return make_pair(flow, cost); 347 } 348 349 void no_answer() 350 { 351 cout << "Impossible" << endl; 352 exit(0); 353 } 354 355 int main() 356 { 357 cin >> n >> m; 358 vector<int> excess_flow(n, 0); 359 vector<int> orc(m); 360 for(int i = 0; i < m; i++) 361 { 362 int x, y, c, w; 363 cin >> x >> y >> c >> w; 364 orc[i] = c; 365 --x; 366 --y; 367 add_edge(x, y, c / 2, w); 368 if(c % 2 == 1) 369 { 370 excess_flow[x]--; 371 excess_flow[y]++; 372 } 373 } 374 s = n; 375 t = n + 1; 376 v = n + 2; 377 int total_excess = 0; 378 if(excess_flow[0] % 2 == -1) 379 { 380 excess_flow[0]--; 381 excess_flow[n - 1]++; 382 } 383 for(int i = 0; i < n; i++) 384 { 385 if(excess_flow[i] % 2 != 0) 386 no_answer(); 387 int val = abs(excess_flow[i]) / 2; 388 if(excess_flow[i] > 0) 389 { 390 total_excess += val; 391 add_edge(s, i, val, -int(1e9)); 392 } 393 if(excess_flow[i] < 0) 394 { 395 add_edge(i, t, val, -int(1e9)); 396 } 397 } 398 add_edge(s, 0, 100000, 0); 399 add_edge(n - 1, t, 100000, 0); 400 auto ans = MCMF(); 401 bool good_answer = true; 402 for(int x = 0; x < e.size(); x++) 403 if(e[x].w == -int(1e9) && rem(x) != 0) 404 good_answer = false; 405 if(!good_answer) 406 no_answer(); 407 cout << "Possible" << endl; 408 for(int i = 0; i < 2 * m; i += 2) 409 { 410 if(i) cout << " "; 411 cout << e[i].f * 2 + orc[i / 2] % 2; 412 } 413 cout << endl; 414 } 415 ```