codeforces-scrape

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

1722.md (8046B)


      1 Source: https://codeforces.com/blog/entry/106478
      2 
      3 Thanks for participating!
      4 
      5 [1722A - Проверка правописания](/contest/1722/problem/A "Codeforces Round 817 (Div. 4)")
      6 
      7 Idea: [mesanu](/profile/mesanu "Эксперт mesanu"), [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov")
      8 
      9 **Tutorial**
     10 
     11 ### [1722A - Проверка правописания](/contest/1722/problem/A "Codeforces Round 817 (Div. 4)")
     12 
     13 Check if the string has length 5 and if it has the characters $\texttt{T}, \texttt{i}, \texttt{m}, \texttt{u}, \texttt{r}$. The complexity is $\mathcal{O}(n)$.
     14 
     15 You can also sort the string, and check if it is $\texttt{Timur}$ when sorted (which is $\texttt{Timru}$).
     16 
     17 **Solution**
     18 
     19 ```
     20 #include <bits/stdc++.h>
     21 
     22 using namespace std;
     23 
     24 #define forn(i, n) for (int i = 0; i < int(n); i++)
     25 
     26 int main() {
     27     string name = "Timur";
     28     sort(name.begin(), name.end());
     29 
     30     int n;
     31     cin >> n;
     32     forn(i, n) {
     33         int m;
     34         cin >> m;
     35         string s;
     36         cin >> s;
     37         sort(s.begin(), s.end());
     38         cout << (s == name ? "YES" : "NO") << endl;
     39     }
     40 }
     41 ```
     42 
     43 [1722B - Дальтонизм](/contest/1722/problem/B "Codeforces Round 817 (Div. 4)")
     44 
     45 Idea: [flamestorm](/profile/flamestorm "Эксперт flamestorm")
     46 
     47 **Tutorial**
     48 
     49 Tutorial is loading...
     50 
     51 **Solution**
     52 
     53 ```
     54 #include <bits/stdc++.h>
     55 
     56 using namespace std;
     57 
     58 const int MAX = 200007;
     59 const int MOD = 1000000007;
     60 
     61 void solve() {
     62 	int n;
     63 	cin >> n;
     64 	string s, t;
     65 	cin >> s >> t;
     66 	for (int i = 0; i < n; i++) {
     67 		if (s[i] == 'R') {
     68 			if (t[i] != 'R') {cout << "NO\n"; return;}
     69 		}
     70 		else {
     71 			if (t[i] == 'R') {cout << "NO\n"; return;}
     72 		}
     73 	}
     74 	cout << "YES\n";
     75 }
     76 
     77 int main() {
     78 	ios::sync_with_stdio(false);
     79 	cin.tie(nullptr);
     80 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
     81 	// solve();
     82 }
     83 ```
     84 
     85 [1722C - Игра в слова](/contest/1722/problem/C "Codeforces Round 817 (Div. 4)")
     86 
     87 Idea: [flamestorm](/profile/flamestorm "Эксперт flamestorm")
     88 
     89 **Tutorial**
     90 
     91 Tutorial is loading...
     92 
     93 **Solution**
     94 
     95 ```
     96 #include <bits/stdc++.h>
     97 
     98 using namespace std;
     99 
    100 const int MAX = 200007;
    101 const int MOD = 1000000007;
    102 
    103 void solve() {
    104 	int n;
    105 	cin >> n;
    106 	map<string, int> mp;
    107 	string a[3][n];
    108 	for (int i = 0; i < 3; i++) {
    109 		for (int j = 0; j < n; j++) {
    110 			cin >> a[i][j];
    111 			mp[a[i][j]]++;
    112 		}
    113 	}
    114 	for (int i = 0; i < 3; i++) {
    115 		int tot = 0;
    116 		for (int j = 0; j < n; j++) {
    117 			if (mp[a[i][j]] == 1) {tot += 3;}
    118 			else if (mp[a[i][j]] == 2) {tot++;}
    119 		}
    120 		cout << tot << ' ';
    121 	}
    122 	cout << '\n';
    123 }
    124 
    125 int main() {
    126 	ios::sync_with_stdio(false);
    127 	cin.tie(nullptr);
    128 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    129 	// solve();
    130 }
    131 ```
    132 
    133 [1722D - Ряд](/contest/1722/problem/D "Codeforces Round 817 (Div. 4)")
    134 
    135 Idea: [flamestorm](/profile/flamestorm "Эксперт flamestorm")
    136 
    137 **Tutorial**
    138 
    139 Tutorial is loading...
    140 
    141 **Solution**
    142 
    143 ```
    144 #include <bits/stdc++.h>
    145 
    146 using namespace std;
    147 
    148 const int MAX = 200007;
    149 const int MOD = 1000000007;
    150 
    151 void solve() {
    152 	int n;
    153 	cin >> n;
    154 	string s;
    155 	cin >> s;
    156 	long long tot = 0;
    157 	vector<long long> v;
    158 	for (int i = 0; i < n; i++) {
    159 		if (s[i] == 'L') {
    160 			v.push_back((n - 1 - i) - i);
    161 			tot += i;
    162 		}
    163 		else {
    164 			v.push_back(i - (n - 1 - i));
    165 			tot += n - 1 - i;
    166 		}
    167 	}
    168 	sort(v.begin(), v.end(), greater<int>());
    169 	for (int i = 0; i < n; i++) {
    170 		if (v[i] > 0) {tot += v[i];}
    171 		cout << tot << ' ';
    172 	}
    173 	cout << '\n';
    174 }
    175 
    176 int main() {
    177 	ios::sync_with_stdio(false);
    178 	cin.tie(nullptr);
    179 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    180 	// solve();
    181 }
    182 ```
    183 
    184 [1722E - Считаем прямоугольники](/contest/1722/problem/E "Codeforces Round 817 (Div. 4)")
    185 
    186 Idea: [mesanu](/profile/mesanu "Эксперт mesanu")
    187 
    188 **Tutorial**
    189 
    190 Tutorial is loading...
    191 
    192 You can read about [2D prefix sums](https://usaco.guide/silver/more-prefix-sums?lang=cpp#2d-prefix-sums) if you haven't heard of them before.
    193 
    194 **Solution**
    195 
    196 ```
    197 #include <bits/stdc++.h>
    198 
    199 using namespace std;
    200 
    201 long long a[1005][1005];
    202 long long pref[1005][1005];
    203 
    204 void solve()
    205 {
    206     long long n, q;
    207     cin >> n >> q;
    208     for(int i = 0; i <= 1001; i++)
    209     {
    210         for(int j = 0; j <= 1001; j++)
    211         {
    212             a[i][j] = pref[i][j] = 0;
    213         }
    214     }
    215     for(int i = 0; i < n; i++)
    216     {
    217         long long h, w;
    218         cin >> h >> w;
    219         a[h][w]+=h*w;
    220     }
    221     for(int i = 1; i <= 1000; i++)
    222     {
    223         for(int j = 1; j <= 1000; j++)
    224         {
    225             pref[i][j] = pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j];
    226         }
    227     }
    228     for(int i = 0; i < q; i++)
    229     {
    230         long long hs, ws, hb, wb;
    231         cin >> hs >> ws >> hb >> wb;
    232         cout << pref[hb-1][wb-1]-pref[hb-1][ws]-pref[hs][wb-1]+pref[hs][ws] << endl;
    233     }
    234 }
    235  
    236 int main() {
    237     int t = 1;
    238     cin >> t;
    239     while(t--)
    240     {
    241         solve();
    242     }
    243 }
    244 ```
    245 
    246 [1722F - L-фигуры](/contest/1722/problem/F "Codeforces Round 817 (Div. 4)")
    247 
    248 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov")
    249 
    250 **Tutorial**
    251 
    252 Tutorial is loading...
    253 
    254 **Solution**
    255 
    256 ```
    257 #include <bits/stdc++.h>
    258 
    259 using namespace std;
    260 
    261 const int MAX = 200007;
    262 const int MOD = 1000000007;
    263 
    264 const int dx[3] = {-1, 0, 1}, dy[3] = {-1, 0, 1};
    265 
    266 void solve() {
    267 	int n, m;
    268 	cin >> n >> m;
    269 	char g[n][m];
    270 	int id[n][m];
    271 	for (int i = 0; i < n; i++) {
    272 		for (int j = 0; j < m; j++) {
    273 			cin >> g[i][j];
    274 			id[i][j] = 0;
    275 		}
    276 	}
    277 	int curr = 1;
    278 	for (int i = 0; i < n; i++) {
    279 		for (int j = 0; j < m; j++) {
    280 			if (g[i][j] == '*') {
    281 				vector<pair<int, int>> adjh, adjv;
    282 				if (i > 0 && g[i - 1][j] == '*') {
    283 					adjh.emplace_back(i - 1, j);
    284 				}
    285 				if (i < n - 1 && g[i + 1][j] == '*') {
    286 					adjh.emplace_back(i + 1, j);
    287 				}
    288 				if (j > 0 && g[i][j - 1] == '*') {
    289 					adjv.emplace_back(i, j - 1);
    290 				}
    291 				if (j < m - 1 && g[i][j + 1] == '*') {
    292 					adjv.emplace_back(i, j + 1);
    293 				}
    294 				if (adjh.size() == 1 && adjv.size() == 1) {
    295 					if (id[i][j] == 0) {id[i][j] = curr;}
    296 					else {cout << "NO\n"; return;}
    297 					if (id[adjh[0].first][adjh[0].second] == 0) {id[adjh[0].first][adjh[0].second] = curr;}
    298 					else {cout << "NO\n"; return;}
    299 					if (id[adjv[0].first][adjv[0].second] == 0) {id[adjv[0].first][adjv[0].second] = curr;}
    300 					else {cout << "NO\n"; return;}
    301 					curr++;
    302 				}
    303 				else if (adjh.size() > 1 || adjv.size() > 1) {
    304 					cout << "NO\n"; return;
    305 				}
    306 			}
    307 		}
    308 	}
    309 	for (int i = 0; i < n; i++) {
    310 		for (int j = 0; j < m; j++) {
    311 			if (g[i][j] == '*') {
    312 				if (id[i][j] == 0) {cout << "NO\n"; return;}
    313 				else {
    314 					for (int x = 0; x < 3; x++) {
    315 						for (int y = 0; y < 3; y++) {
    316 							if (0 <= i + dx[x] && i + dx[x] < n) {
    317 								if (0 <= j + dy[y] && j + dy[y] < m) {
    318 									if (id[i + dx[x]][j + dy[y]] != id[i][j] && id[i + dx[x]][j + dy[y]] != 0) {
    319 										cout << "NO\n"; return;
    320 									}
    321 								}
    322 							}
    323 						}
    324 					}
    325 				}
    326 			}
    327 		}
    328 	}
    329 	cout << "YES\n";
    330 }
    331 
    332 int main() {
    333 	ios::sync_with_stdio(false);
    334 	cin.tie(nullptr);
    335 	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    336 	// solve();
    337 }
    338 ```
    339 
    340 [1722G - Чётный-нечётный XOR](/contest/1722/problem/G "Codeforces Round 817 (Div. 4)")
    341 
    342 Idea: [mesanu](/profile/mesanu "Эксперт mesanu")
    343 
    344 **Tutorial**
    345 
    346 Tutorial is loading...
    347 
    348 **Alternate Tutorial Sketch**
    349 
    350 Output the integers from $1$ to $n-3$, then $2^{29}$, $2^{30}$, and the XOR of those $n-1$ numbers. Why does it work?
    351 
    352 **Solution**
    353 
    354 ```
    355 #include <bits/stdc++.h>
    356 
    357 using namespace std;
    358 
    359 void solve()
    360 {
    361     int n;
    362     cin >> n;
    363     int case1 = 0;
    364     int case2 = 0;
    365     for(int i = 0; i < n-2; i++)
    366     {
    367         case1^=i;
    368         case2^=(i+1);
    369     }
    370     long long addLast = ((long long)1<<31)-1;
    371     if(case1 != 0)
    372     {
    373         for(int i = 0; i < n-2; i++)
    374         {
    375             cout << i << " ";
    376         }
    377         case1^=addLast;
    378         cout << addLast << " " << case1 << endl;
    379     }
    380     else
    381     {
    382         for(int i = 1; i <= n-2; i++)
    383         {
    384             cout << i << " ";
    385         }
    386         case2^=addLast;
    387         cout << addLast << " " << case2 << endl;
    388     }
    389 }
    390 
    391 int main()
    392 {
    393     int t = 1;
    394     cin >> t;
    395     while(t--)
    396     {
    397         solve();
    398     }
    399 }
    400 ```