1360.md (6636B)
1 Source: https://codeforces.com/blog/entry/77846 2 3 All problems were invented by [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") and developed by me, [Stepavly](/profile/Stepavly "Master Stepavly"), and [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"). 4 5 [1360A - Minimal Square](/contest/1360/problem/A "Codeforces Round 644 (Div. 3)") 6 7 **Editorial** 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 20 int solve(int a, int b) { 21 int side = min(max(a * 2, b), max(a, b * 2)); 22 return side * side; 23 } 24 25 int main(int argc, char* argv[]) { 26 int t; 27 cin >> t; 28 forn(tt, t) { 29 int a, b; 30 cin >> a >> b; 31 cout << solve(a, b) << endl; 32 } 33 } 34 ``` 35 36 [1360B - Honest Coach](/contest/1360/problem/B "Codeforces Round 644 (Div. 3)") 37 38 **Editorial** 39 40 Tutorial is loading... 41 42 **Solution** 43 44 ``` 45 #include <bits/stdc++.h> 46 using namespace std; 47 48 int main() { 49 int test; 50 cin >> test; 51 52 for (int tt = 0; tt < test; tt++) { 53 int n; 54 cin >> n; 55 56 vector<int> a(n); 57 58 for (int &x : a) { 59 cin >> x; 60 } 61 62 sort(a.begin(), a.end()); 63 64 int result = a[n - 1] - a[0]; 65 66 for (int i = 0; i < n; i++) { 67 for (int j = i + 1; j < n; j++) { 68 result = min(result, a[j] - a[i]); 69 } 70 } 71 72 cout << result << endl; 73 } 74 75 return 0; 76 } 77 ``` 78 79 [1360C - Similar Pairs](/contest/1360/problem/C "Codeforces Round 644 (Div. 3)") 80 81 **Editorial** 82 83 Tutorial is loading... 84 85 **Solution** 86 87 ``` 88 #include <bits/stdc++.h> 89 90 using namespace std; 91 using ld = long double; 92 using ll = long long; 93 94 void solve() { 95 int n; 96 cin >> n; 97 vector<int> v(n); 98 int a = 0, b = 0; 99 for (int &e : v) { 100 cin >> e; 101 if (e % 2 == 0) { 102 a++; 103 } else { 104 b++; 105 } 106 } 107 if (a % 2 != b % 2) { 108 cout << "NO\n"; 109 } else { 110 if (a % 2 == 0) { 111 cout << "YES\n"; 112 } else { 113 for (int i = 0; i < n; i++) { 114 for (int j = i + 1; j < n; j++) { 115 if (v[i] % 2 != v[j] % 2 && abs(v[i] - v[j]) == 1) { 116 cout << "YES\n"; 117 return; 118 } 119 } 120 } 121 cout << "NO\n"; 122 } 123 } 124 } 125 126 int main() { 127 int t; 128 cin >> t; 129 while (t--) { 130 solve(); 131 } 132 } 133 ``` 134 135 [1360D - Buying Shovels](/contest/1360/problem/D "Codeforces Round 644 (Div. 3)") 136 137 **Editorial** 138 139 Tutorial is loading... 140 141 **Solution** 142 143 ``` 144 #include <bits/stdc++.h> 145 using namespace std; 146 147 int main() { 148 int test; 149 cin >> test; 150 151 for (int tt = 0; tt < test; tt++) { 152 int n, k; 153 cin >> n >> k; 154 155 int ans = n; 156 157 for (int j = 1; j * j <= n; j++) { 158 if (n % j == 0) { 159 if (j <= k) { 160 ans = min(ans, n / j); 161 } 162 163 if (n / j <= k) { 164 ans = min(ans, j); 165 } 166 } 167 } 168 169 cout << ans << endl; 170 } 171 172 return 0; 173 } 174 ``` 175 176 [1360E - Polygon](/contest/1360/problem/E "Codeforces Round 644 (Div. 3)") 177 178 **Editorial** 179 180 Tutorial is loading... 181 182 **Solution** 183 184 ``` 185 #include <bits/stdc++.h> 186 187 using namespace std; 188 189 bool a[50][50]; 190 191 int main() { 192 int tests; 193 cin >> tests; 194 while (tests--) { 195 int n; 196 cin >> n; 197 for (int i = 0; i < n; ++i) { 198 for (int j = 0; j < n; ++j) { 199 char c; 200 cin >> c; 201 a[i][j] = c - '0'; 202 } 203 } 204 205 bool ans = true; 206 for (int i = n - 2; i >= 0; --i) { 207 for (int j = n - 2; j >= 0; --j) { 208 if (a[i][j] && !a[i + 1][j] && !a[i][j + 1]) { 209 ans = false; 210 } 211 } 212 } 213 214 cout << (ans ? "YES" : "NO") << endl; 215 } 216 } 217 ``` 218 219 [1360F - Spy-string](/contest/1360/problem/F "Codeforces Round 644 (Div. 3)") 220 221 **Editorial** 222 223 Tutorial is loading... 224 225 **Solution** 226 227 ``` 228 #include <bits/stdc++.h> 229 230 using namespace std; 231 using ld = long double; 232 using ll = long long; 233 234 void solve() { 235 int n, m; 236 cin >> n >> m; 237 vector<string> v(n); 238 for (int i = 0; i < n; i++) { 239 cin >> v[i]; 240 } 241 string ans = v[0]; 242 for (int j = 0; j < m; j++) { 243 char save = ans[j]; 244 for (char d = 'a'; d <= 'z'; d++) { 245 ans[j] = d; 246 bool flag = true; 247 for (int z = 0; z < n; z++) { 248 int cntErrors = 0; 249 for (int c = 0; c < m; c++) { 250 if (v[z][c] != ans[c]) { 251 cntErrors++; 252 } 253 } 254 if (cntErrors > 1) { 255 flag = false; 256 break; 257 } 258 } 259 if (flag) { 260 cout << ans << endl; 261 return; 262 } 263 } 264 ans[j] = save; 265 } 266 cout << "-1" << endl; 267 } 268 269 int main() { 270 int t; 271 cin >> t; 272 while (t--) { 273 solve(); 274 } 275 } 276 ``` 277 278 [1360G - A/B Matrix](/contest/1360/problem/G "Codeforces Round 644 (Div. 3)") 279 280 **Editorial** 281 282 Tutorial is loading... 283 284 **Solution** 285 286 ``` 287 #include <bits/stdc++.h> 288 using namespace std; 289 290 int main() { 291 int test; 292 cin >> test; 293 294 for (int tt = 0; tt < test; tt++) { 295 int h, w, a, b; 296 cin >> h >> w >> a >> b; 297 298 if (h * a != w * b) { 299 cout << "NO" << endl; 300 continue; 301 } 302 303 vector<vector<int>> result(h, vector<int>(w, 0)); 304 305 int shift = 0; 306 307 for (shift = 1; shift < w; shift++) { 308 if (shift * h % w == 0) { 309 break; 310 } 311 } 312 313 for (int i = 0, dx = 0; i < h; i++, dx += shift) { 314 for (int j = 0; j < a; j++) { 315 result[i][(j + dx) % w] = 1; 316 } 317 } 318 319 cout << "YES" << endl; 320 321 for (int i = 0; i < h; i++) { 322 for (int j = 0; j < w; j++) { 323 cout << result[i][j]; 324 } 325 326 cout << endl; 327 } 328 } 329 330 return 0; 331 } 332 ``` 333 334 [1360H - Binary Median](/contest/1360/problem/H "Codeforces Round 644 (Div. 3)") 335 336 **Editorial** 337 338 Tutorial is loading... 339 340 **Solution** 341 342 ``` 343 #include <bits/stdc++.h> 344 345 using namespace std; 346 using ld = long double; 347 using ll = long long; 348 349 void solve() { 350 ll m, n; 351 cin >> n >> m; 352 vector<ll> v(n); 353 for (int i = 0; i < n; i++) { 354 string s; 355 cin >> s; 356 for (char c : s) { 357 v[i] *= 2; 358 v[i] += c - '0'; 359 } 360 } 361 ll need = ((1ll << m) - n - 1) / 2 + 1; 362 ll cur = (1ll << (m - 1)) - 1; 363 while (true) { 364 ll left = cur + 1; 365 bool flag = false; 366 for (int i = 0; i < n; i++) { 367 flag |= v[i] == cur; 368 if (v[i] <= cur) { 369 left--; 370 } 371 } 372 if (left == need && !flag) { 373 string s; 374 for (int i = 0; i < m; i++) { 375 s += (char)(cur % 2 + '0'); 376 cur /= 2; 377 } 378 reverse(s.begin(), s.end()); 379 cout << s << endl; 380 return; 381 } else if (left < need) { 382 cur++; 383 } else { 384 cur--; 385 } 386 } 387 } 388 389 int main() { 390 int t; 391 cin >> t; 392 while (t--) { 393 solve(); 394 } 395 } 396 ```