codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```