1155.md (7329B)
1 Source: https://codeforces.com/blog/entry/66687 2 3 [1155A - Reverse a Substring](/contest/1155/problem/A "Educational Codeforces Round 63 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (Vovuh)** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 #ifdef _DEBUG 18 freopen("input.txt", "r", stdin); 19 // freopen("output.txt", "w", stdout); 20 #endif 21 22 int n; 23 string s; 24 cin >> n >> s; 25 26 for (int i = 1; i < int(s.size()); ++i) { 27 if (s[i] < s[i - 1]) { 28 cout << "YES" << endl; 29 cout << i << " " << i + 1 << endl; 30 return 0; 31 } 32 } 33 34 cout << "NO" << endl; 35 36 return 0; 37 } 38 ``` 39 40 [1155B - Game with Telephone Numbers](/contest/1155/problem/B "Educational Codeforces Round 63 (Rated for Div. 2)") 41 42 **Tutorial** 43 44 Tutorial is loading... 45 46 **Solution (Roms)** 47 48 ``` 49 #include<bits/stdc++.h> 50 51 using namespace std; 52 53 int n; 54 string s; 55 56 int main(){ 57 cin >> n >> s; 58 int cnt1 = (n - 11) / 2; 59 int cnt2 = cnt1; 60 string res = ""; 61 for(int i = 0; i < n; ++i){ 62 if(s[i] == '8'){ 63 if(cnt1 > 0) --cnt1; 64 else res += s[i]; 65 } 66 else{ 67 if(cnt2 > 0) --cnt2; 68 else res += s[i]; 69 } 70 } 71 72 if(res[0] == '8') cout << "YES\n"; 73 else cout << "NO\n"; 74 return 0; 75 } 76 ``` 77 78 [1155C - Alarm Clocks Everywhere](/contest/1155/problem/C "Educational Codeforces Round 63 (Rated for Div. 2)") 79 80 **Tutorial** 81 82 Tutorial is loading... 83 84 **Solution (Vovuh)** 85 86 ``` 87 #include <bits/stdc++.h> 88 89 using namespace std; 90 91 int main() { 92 #ifdef _DEBUG 93 freopen("input.txt", "r", stdin); 94 // freopen("output.txt", "w", stdout); 95 #endif 96 97 int n, m; 98 cin >> n >> m; 99 vector<long long> x(n), p(m); 100 for (int i = 0; i < n; ++i) { 101 cin >> x[i]; 102 } 103 for (int i = 0; i < m; ++i) { 104 cin >> p[i]; 105 } 106 107 long long g = x[1] - x[0]; 108 for (int i = 2; i < n; ++i) { 109 g = __gcd(g, x[i] - x[i - 1]); 110 } 111 112 for (int i = 0; i < m; ++i) { 113 if (g % p[i] == 0) { 114 cout << "YES" << endl; 115 cout << x[0] << " " << i + 1 << endl; 116 return 0; 117 } 118 } 119 120 cout << "NO" << endl; 121 122 return 0; 123 } 124 ``` 125 126 [1155D - Beautiful Array](/contest/1155/problem/D "Educational Codeforces Round 63 (Rated for Div. 2)") 127 128 **Tutorial** 129 130 Tutorial is loading... 131 132 **Solution (PikMike)** 133 134 ``` 135 #include <bits/stdc++.h> 136 137 using namespace std; 138 139 #define forn(i, n) for(int i = 0; i < int(n); i++) 140 141 typedef long long li; 142 143 const int N = 300 * 1000 + 13; 144 const li INF64 = 1e18; 145 146 int n, x; 147 int a[N]; 148 149 li dp[N][3][3]; 150 151 int main() { 152 scanf("%d%d", &n, &x); 153 forn(i, n) scanf("%d", &a[i]); 154 155 forn(i, n + 1) forn(j, 3) forn(k, 3) 156 dp[i][j][k] = -INF64; 157 158 dp[0][0][0] = 0; 159 forn(i, n + 1) forn(j, 3) forn(k, 3){ 160 if (k < 2) 161 dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k]); 162 if (j < 2) 163 dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k]); 164 if (i < n) 165 dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k] + (j == 1 ? a[i] : 0) * li(k == 1 ? x : 1)); 166 } 167 168 printf("%lld\n", dp[n][2][2]); 169 } 170 ``` 171 172 [1155E - Guess the Root](/contest/1155/problem/E "Educational Codeforces Round 63 (Rated for Div. 2)") 173 174 **Tutorial** 175 176 Tutorial is loading... 177 178 **Solution (adedalic)** 179 180 ``` 181 #include<bits/stdc++.h> 182 using namespace std; 183 184 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 185 #define sz(a) int((a).size()) 186 187 #define x first 188 #define y second 189 190 typedef long long li; 191 typedef long double ld; 192 typedef pair<int, int> pt; 193 194 const int MOD = 1000 * 1000 + 3; 195 196 int norm(int a) { 197 while(a >= MOD) a -= MOD; 198 while(a < 0) a += MOD; 199 return a; 200 } 201 int mul(int a, int b) { 202 return int(a * 1ll * b % MOD); 203 } 204 int binPow(int a, int k) { 205 int ans = 1; 206 while(k > 0) { 207 if(k & 1) 208 ans = mul(ans, a); 209 a = mul(a, a); 210 k >>= 1; 211 } 212 return ans; 213 } 214 int inv(int a) { 215 return binPow(a, MOD - 2); 216 } 217 218 int k = 10; 219 vector<int> f; 220 221 int main() { 222 f.resize(k + 1); 223 fore(i, 0, sz(f)) { 224 cout << "? " << i << endl; 225 cout.flush(); 226 cin >> f[i]; 227 } 228 229 vector< vector<int> > mat(sz(f), vector<int>(sz(f) + 1)); 230 fore(i, 0, sz(mat)) { 231 mat[i][0] = 1; 232 mat[i][sz(f)] = f[i]; 233 234 fore(j, 1, sz(mat[i]) - 1) 235 mat[i][j] = mul(mat[i][j - 1], i); 236 } 237 238 /* 239 fore(i, 0, sz(mat)) { 240 fore(j, 0, sz(mat[i])) 241 cerr << mat[i][j] << " "; 242 cerr << endl; 243 } 244 */ 245 246 fore(j, 0, sz(mat)) { 247 int nid = -1; 248 fore(i, j, sz(mat)) { 249 if(mat[i][j] != 0) { 250 nid = i; 251 break; 252 } 253 } 254 if(nid == -1) 255 continue; 256 257 swap(mat[j], mat[nid]); 258 fore(i, 0, sz(mat)) { 259 if(i == j) continue; 260 int cf = mul(mat[i][j], inv(mat[j][j])); 261 262 fore(cj, j, sz(mat[i])) 263 mat[i][cj] = norm(mat[i][cj] - mul(cf, mat[j][cj])); 264 } 265 } 266 267 vector<int> a(sz(f), 0); 268 fore(i, 0, sz(a)) { 269 if(mat[i][i] == 0) 270 continue; 271 a[i] = mul(mat[i][sz(a)], inv(mat[i][i])); 272 } 273 274 fore(x0, 0, MOD) { 275 int val = 0; 276 for(int i = sz(a) - 1; i >= 0; i--) 277 val = norm(mul(val, x0) + a[i]); 278 279 if(val == 0) { 280 cout << "! " << x0 << endl; 281 return 0; 282 } 283 } 284 285 cout << "! -1" << endl; 286 return 0; 287 } 288 ``` 289 290 [1155F - Delivery Oligopoly](/contest/1155/problem/F "Educational Codeforces Round 63 (Rated for Div. 2)") 291 292 **Tutorial** 293 294 Tutorial is loading... 295 296 **Solution (BledDest)** 297 298 ``` 299 #include<bits/stdc++.h> 300 using namespace std; 301 302 const int N = 14; 303 const int INF = int(1e9); 304 305 int dp[1 << N]; 306 int par[1 << N]; 307 int last[1 << N]; 308 pair<int, int> last_pair[1 << N]; 309 int dp2[N][N][1 << N]; 310 int lastv[N][N][1 << N]; 311 vector<int> bits[1 << N]; 312 313 int n; 314 int m; 315 vector<int> g[N]; 316 317 int main() 318 { 319 cin >> n >> m; 320 for(int i = 0; i < m; i++) 321 { 322 int x, y; 323 cin >> x >> y; 324 --x; 325 --y; 326 g[x].push_back(y); 327 g[y].push_back(x); 328 } 329 for(int i = 0; i < (1 << n); i++) 330 dp[i] = INF; 331 for(int i = 0; i < n; i++) 332 for(int j = 0; j < n; j++) 333 for(int z = 0; z < (1 << n); z++) 334 dp2[i][j][z] = INF; 335 for(int i = 0; i < n; i++) 336 for(auto x : g[i]) 337 { 338 dp2[i][x][0] = 1; 339 lastv[i][x][0] = i; 340 } 341 for(int mask = 0; mask < (1 << n); mask++) 342 for(int i = 0; i < n; i++) 343 for(int j = 0; j < n; j++) 344 { 345 if((mask & (1 << i)) || (mask & (1 << j)) || (i == j) || (dp2[i][j][mask] == INF)) 346 continue; 347 for(auto z : g[j]) 348 { 349 if(mask & (1 << z)) continue; 350 if(z == lastv[i][j][mask]) continue; 351 int nmask = mask ^ (1 << j); 352 if(dp2[i][z][nmask] == INF) 353 { 354 dp2[i][z][nmask] = 1; 355 lastv[i][z][nmask] = j; 356 } 357 } 358 } 359 for(int mask = 0; mask < (1 << n); mask++) 360 for(int j = 0; j < n; j++) 361 if(mask & (1 << j)) 362 bits[mask].push_back(j); 363 dp[1] = 0; 364 for(int mask = 0; mask < (1 << n); mask++) 365 for(int addmask = mask; addmask; addmask = (addmask - 1) & mask) 366 { 367 int lastmask = mask ^ addmask; 368 int cnt = __builtin_popcount(addmask) + 1; 369 if(dp[lastmask] + cnt >= dp[mask]) 370 continue; 371 bool f = false; 372 for(auto x : bits[lastmask]) 373 { 374 for(auto y : bits[lastmask]) 375 { 376 if(dp2[x][y][addmask] == 1) 377 { 378 dp[mask] = dp[lastmask] + cnt; 379 last_pair[mask] = make_pair(x, y); 380 last[mask] = addmask; 381 } 382 if(f) break; 383 } 384 if(f) break; 385 } 386 } 387 if(dp[(1 << n) - 1] == INF) 388 cout << -1 << endl; 389 else 390 { 391 cout << dp[(1 << n) - 1] << endl; 392 int cur = (1 << n) - 1; 393 while(cur != 1) 394 { 395 int lst = last[cur]; 396 int x = last_pair[cur].first; 397 int y = last_pair[cur].second; 398 cur ^= lst; 399 while(lst) 400 { 401 int ny = lastv[x][y][lst]; 402 cout << y + 1 << " " << ny + 1 << endl; 403 lst ^= (1 << ny); 404 y = ny; 405 } 406 cout << x + 1 << " " << y + 1 << endl; 407 } 408 } 409 } 410 ```