codeforces-scrape

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

1676.md (8724B)


      1 Source: https://codeforces.com/blog/entry/102710
      2 
      3 Thank you for participating!
      4 
      5 [1676A - Счастливый?](/contest/1676/problem/A "Codeforces Round 790 (Div. 4)")
      6 
      7 Idea: [mesanu](/profile/mesanu "Эксперт mesanu") and [SlavicG](/profile/SlavicG "Кандидат в мастера SlavicG")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 using namespace std;
     18 
     19 void solve() {
     20 	string s;
     21 	cin >> s;
     22 	if(s[0]+s[1]+s[2] == s[3]+s[4]+s[5]) {
     23 		cout << "YES" << endl;
     24 	}
     25 	else {
     26 		cout << "NO" << endl;
     27 	}
     28 }
     29 
     30 int main() {
     31 	int t = 1;
     32 	cin >> t;
     33 	while (t--) {
     34 		solve();
     35 	}
     36 }
     37 ```
     38 
     39 [1676B - Равенство конфет](/contest/1676/problem/B "Codeforces Round 790 (Div. 4)")
     40 
     41 Idea: [Errichto](/profile/Errichto "Международный гроссмейстер Errichto")
     42 
     43 **Tutorial**
     44 
     45 Tutorial is loading...
     46 
     47 **Solution**
     48 
     49 ```
     50 #include "bits/stdc++.h"
     51 using namespace std;
     52 
     53 int main() {
     54     int t; cin >> t;
     55     while(t--) {
     56         int n; cin >> n;
     57         vector<int> a(n);
     58         int mn = INT_MAX, ans = 0;
     59         for(int i = 0; i < n; ++i) {
     60             cin >> a[i];
     61             mn = min(mn, a[i]);
     62         }
     63         for(int i = 0; i < n; ++i) {
     64             ans += a[i] - mn;
     65         }
     66         cout << ans << "\n";
     67     }
     68 }
     69 ```
     70 
     71 [1676C - Самые похожие слова](/contest/1676/problem/C "Codeforces Round 790 (Div. 4)")
     72 
     73 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov")
     74 
     75 **Tutorial**
     76 
     77 Tutorial is loading...
     78 
     79 **Solution**
     80 
     81 ```
     82 #include "bits/stdc++.h"
     83 using namespace std;
     84 
     85 int cost(string& a, string& b) {
     86     int val = 0;
     87     for(int i = 0; i < a.size(); ++i) {
     88         val += abs(a[i] - b[i]);
     89     }
     90     return val;
     91 }
     92 
     93 int main() {
     94     int t; cin >> t;
     95     while(t--) {
     96         int n, m; cin >> n >> m;
     97         vector<string> s(n);
     98         for(int i = 0; i < n; ++i) {
     99             cin >> s[i];
    100         }
    101         int ans = INT_MAX;
    102         for(int i = 0; i < n; ++i) {
    103             for(int j = i + 1; j < n; ++j) {
    104                 ans = min(ans, cost(s[i], s[j]));
    105             }
    106         }
    107         cout << ans << "\n";
    108     }
    109 }
    110 ```
    111 
    112 [1676D - X-сумма](/contest/1676/problem/D "Codeforces Round 790 (Div. 4)")
    113 
    114 Idea: [mesanu](/profile/mesanu "Эксперт mesanu")
    115 
    116 **Tutorial**
    117 
    118 Tutorial is loading...
    119 
    120 **Solution**
    121 
    122 ```
    123 #include <bits/stdc++.h>
    124 using namespace std;
    125  
    126 void solve()
    127 {
    128 	int n, m;
    129 	cin >> n >> m;
    130 	int a[n][m];
    131 	for(int i = 0; i < n; i++)
    132 	{
    133 		for(int j = 0; j < m; j++)
    134 		{
    135 			cin >> a[i][j];
    136 		}
    137 	}
    138 	int mx = 0;
    139 	for(int i = 0; i < n; i++)
    140 	{
    141 		for(int j = 0; j < m; j++)
    142 		{
    143 			int now = 0;
    144 			int ci = i, cj = j;
    145 			while(ci >= 0 && ci < n && cj >= 0 && cj < m)
    146 			{
    147 				now+=a[ci][cj];
    148 				ci--;
    149 				cj--;
    150 			}
    151 			ci = i, cj = j;
    152 			while(ci >= 0 && ci < n && cj >= 0 && cj < m)
    153 			{
    154 				now+=a[ci][cj];
    155 				ci++;
    156 				cj--;
    157 			}
    158 			ci = i, cj = j;
    159 			while(ci >= 0 && ci < n && cj >= 0 && cj < m)
    160 			{
    161 				now+=a[ci][cj];
    162 				ci--;
    163 				cj++;
    164 			}
    165 			ci = i, cj = j;
    166 			while(ci >= 0 && ci < n && cj >= 0 && cj < m)
    167 			{
    168 				now+=a[ci][cj];
    169 				ci++;
    170 				cj++;
    171 			}
    172 			now-=a[i][j]*3;
    173 			mx = max(mx, now);
    174 		}
    175 	}
    176 	cout << mx << endl;
    177 }
    178 
    179 int main() {
    180 	int t;
    181 	cin >> t;
    182 	while(t--)
    183 	{
    184 		solve();
    185 	}
    186 }
    187 ```
    188 
    189 [1676E - Запросы на поедание конфет](/contest/1676/problem/E "Codeforces Round 790 (Div. 4)")
    190 
    191 Idea: [mesanu](/profile/mesanu "Эксперт mesanu")
    192 
    193 **Tutorial**
    194 
    195 Tutorial is loading...
    196 
    197 **Solution**
    198 
    199 ```
    200 #include "bits/stdc++.h"
    201 using namespace std;
    202 
    203 int main() {  
    204     int t; cin >> t;
    205     while(t--) {
    206         int n, q; cin >> n >> q;
    207         vector<long long> a(n), p(n);
    208         for(int i = 0; i < n; ++i) {
    209             cin >> a[i];
    210         }
    211         sort(a.rbegin(), a.rend());
    212         for(int i = 0; i < n; ++i) {
    213             p[i] = (i ? p[i - 1] : 0) + a[i];
    214         }
    215     
    216         while(q--) {
    217             long long x; cin >> x;
    218             int l = 1, r = n, ans = -1;
    219             while(l <= r) {
    220                 int mid = (l + r) / 2;
    221                 if(p[mid - 1] >= x) {
    222                     ans = mid;
    223                     r = mid - 1;
    224                 } else {
    225                     l = mid + 1;
    226                 }
    227             }
    228             cout << ans << "\n";
    229         }
    230     }
    231 }
    232 ```
    233 
    234 [1676F - Самый длинный страйк](/contest/1676/problem/F "Codeforces Round 790 (Div. 4)")
    235 
    236 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov")
    237 
    238 **Tutorial**
    239 
    240 Tutorial is loading...
    241 
    242 **Solution**
    243 
    244 ```
    245 #include <bits/stdc++.h>
    246 using namespace std;
    247  
    248 void solve()
    249 {
    250 	int n, k;
    251 	cin >> n >> k;
    252 	int a[n];
    253 	map<int, int> mp;
    254 	for(int i = 0; i < n; i++)
    255 	{
    256 		cin >> a[i];
    257 		mp[a[i]]++;
    258 	}
    259 	vector<int> c;
    260 	for(auto x : mp)
    261 	{
    262 		if(x.second >= k)
    263 		{
    264 			c.push_back(x.first);
    265 		}
    266 	}
    267 	if(c.size() == 0)
    268 	{
    269 		cout << -1 << endl;
    270 		return;
    271 	}
    272 	sort(c.begin(), c.end());
    273 	int mx = 0;
    274 	int lans = c[0], rans = c[0];
    275 	int l = c[0];
    276 	for(int i = 1; i < c.size(); i++)
    277 	{
    278 		if(c[i]-1 == c[i-1])
    279 		{
    280 			if(c[i]-l > mx)
    281 			{
    282 				lans = l;
    283 				rans = c[i];
    284 				mx = c[i]-l;
    285 			}
    286 		}
    287 		else
    288 		{
    289 			l = c[i];
    290 		}
    291 	}
    292 	cout << lans << " " << rans << endl;
    293 }
    294 
    295 int main(int argc, char * argv[])
    296 {
    297 	int t;
    298 	cin >> t;
    299 	while(t--)
    300 	{
    301 		solve();
    302 	}
    303 }
    304 ```
    305 
    306 [1676G - Чёрно-белые сбалансированные поддеревья](/contest/1676/problem/G "Codeforces Round 790 (Div. 4)")
    307 
    308 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov")
    309 
    310 **Tutorial**
    311 
    312 Tutorial is loading...
    313 
    314 **Solution**
    315 
    316 ```
    317 #include <bits/stdc++.h>
    318 
    319 using namespace std;
    320 
    321 const int MAX = 200007;
    322 const int MOD = 1000000007;
    323 
    324 void solve() {
    325 	int n;
    326 	cin >> n;
    327 	vector<int> child[n + 7];
    328 	for (int i = 2; i <= n; i++) {
    329 		int x;
    330 		cin >> x;
    331 		child[x].push_back(i);
    332 	}
    333 	string s;
    334 	cin >> s;
    335 	int res = 0;
    336 	function<int(int)> dp = [&] (int x) {
    337 		int bal = (s[x - 1] == 'B') ? -1 : 1;
    338 		if (child[x].empty()) {return bal;}
    339 		for (int i : child[x]) {
    340 			bal += dp(i);
    341 		}
    342 		if (bal == 0) {res++;}
    343 		return bal;
    344 	};
    345 	dp(1);
    346 	cout << res << '\n';
    347 }
    348 
    349 int main() {
    350     ios::sync_with_stdio(false);
    351     cin.tie(nullptr);
    352     int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    353     // solve();
    354 }
    355 ```
    356 
    357 [1676H1 - Максимизация пересечений (простая версия)](/contest/1676/problem/H1 "Codeforces Round 790 (Div. 4)")
    358 
    359 Idea: [flamestorm](/profile/flamestorm "Эксперт flamestorm")
    360 
    361 **Tutorial**
    362 
    363 Tutorial is loading...
    364 
    365 **Solution**
    366 
    367 ```
    368 #include <bits/stdc++.h>
    369 
    370 using namespace std;
    371 
    372 const int MAX = 200007;
    373 const int MOD = 1000000007;
    374 
    375 void solve() {
    376 	int n;
    377 	cin >> n;
    378 	int a[n];
    379 	for (int i = 0; i < n; i++) {
    380 		cin >> a[i];
    381 	}
    382 	int res = 0;
    383 	for (int i = 0; i < n; i++) {
    384 		for (int j = i + 1; j < n; j++) {
    385 			if (a[i] >= a[j]) {res++;}
    386 		}
    387 	}
    388 	cout << res << '\n';
    389 }
    390 
    391 int main() {
    392     ios::sync_with_stdio(false);
    393     cin.tie(nullptr);
    394     int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    395     // solve();
    396 }
    397 ```
    398 
    399 [1676H2 - Максимизация пересечений (сложная версия)](/contest/1676/problem/H2 "Codeforces Round 790 (Div. 4)")
    400 
    401 Idea: [flamestorm](/profile/flamestorm "Эксперт flamestorm")
    402 
    403 **Tutorial**
    404 
    405 Tutorial is loading...
    406 
    407 **Solution**
    408 
    409 ```
    410 #include <bits/stdc++.h>
    411 
    412 using namespace std;
    413 
    414 const int MAX = 200007;
    415 const int MOD = 1000000007;
    416 
    417 long long merge(int a[], int temp[], int left, int mid, int right) {
    418    int i, j, k;
    419    long long count = 0;
    420    i = left;
    421    j = mid;
    422    k = left;
    423    while ((i <= mid - 1) && (j <= right)) {
    424       if (a[i] <= a[j]){
    425       temp[k++] = a[i++];
    426       } else {
    427          temp[k++] = a[j++];
    428          count += (mid - i);
    429       }
    430    }
    431    while (i <= mid - 1)
    432       temp[k++] = a[i++];
    433    while (j <= right)
    434       temp[k++] = a[j++];
    435    for (i=left; i <= right; i++)
    436       a[i] = temp[i];
    437    return count;
    438 }
    439 long long mergeSort(int a[], int temp[], int left, int right){
    440    int mid;
    441    long long count = 0;
    442    if (right > left) {
    443       mid = (right + left)/2;
    444       count = mergeSort(a, temp, left, mid);
    445       count += mergeSort(a, temp, mid+1, right);
    446       count += merge(a, temp, left, mid+1, right);
    447    }
    448    return count;
    449 }
    450 long long aInversion(int a[], int n) {
    451    int temp[n];
    452    return mergeSort(a, temp, 0, n - 1);
    453 }
    454 
    455 void solve() {
    456 	int n;
    457 	cin >> n;
    458 	int a[n];
    459 	for (int i = 0; i < n; i++) {
    460 		cin >> a[i];
    461 	}
    462 	long long res = aInversion(a, n);
    463 	sort(a, a + n);
    464 	long long curr = 1;
    465 	for (int i = 1; i < n; i++) {
    466 	    if (a[i] != a[i - 1]) {res += (curr * (curr - 1)) / 2; curr = 1;}
    467 	    else {curr++;}
    468 	}
    469 	res += (curr * (curr - 1)) / 2;
    470 	cout << res << '\n';
    471 }
    472 
    473 int main() {
    474     ios::sync_with_stdio(false);
    475     cin.tie(nullptr);
    476     int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    477     // solve();
    478 }
    479 ```