codeforces-scrape

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

1185.md (13685B)


      1 Source: https://codeforces.com/blog/entry/67829
      2 
      3 Tutorial is loading...
      4 
      5 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555")
      6 
      7 **Authors' solution**
      8 
      9 ```
     10 def solve(a, b, c, d):
     11     return max(0, d - (b - a)) + max(0, d - (c - b))
     12 
     13 def main():
     14     a, b, c, d = map(int, input().split())
     15     a, b, c = sorted((a, b, c))
     16     print(solve(a, b, c, d))
     17 
     18 main()
     19 ```
     20 
     21 Tutorial is loading...
     22 
     23 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov")
     24 
     25 **Authors' solution**
     26 
     27 ```
     28 #include <bits/stdc++.h>
     29 
     30 using namespace std;
     31 
     32 #define forn(i, n) for (int i = 0; i < int(n); i++)
     33 
     34 vector<pair<char,int>> split(string s) {
     35     char c = s[0];
     36     int cnt = 1;
     37     vector<pair<char,int>> result;
     38     auto ss = s.c_str();
     39     for (int i = 1; i <= int(s.length()); i++) {
     40         if (ss[i] != c) {
     41             result.push_back({c, cnt});
     42             c = s[i];
     43             cnt = 1;
     44         } else
     45             cnt++;
     46     }
     47     return result;
     48 }
     49 
     50 int main() {
     51     int n;
     52     cin >> n;
     53     forn(tt, n) {
     54         string s, t;
     55         cin >> s >> t;
     56         auto sa(split(s)), ta(split(t));
     57         bool ok = sa.size() == ta.size();
     58         if (ok)
     59             forn(i, sa.size())
     60                 if (sa[i].first != ta[i].first || sa[i].second > ta[i].second)
     61                     ok = false;
     62         cout << (ok ? "YES" : "NO") << endl;
     63     }
     64 }
     65 ```
     66 
     67 Tutorial is loading...
     68 
     69 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"), [cannor147](/profile/cannor147 "Специалист cannor147") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555")
     70 
     71 **Authors' solution**
     72 
     73 ```
     74 #include <bits/stdc++.h>
     75 
     76 using namespace std;
     77 
     78 const int T = 100;
     79 
     80 int main() {
     81 	int n, m;
     82 	cin >> n >> m;
     83 	
     84 	int sum = 0;
     85 	vector<int> t(n), count(T + 1, 0);
     86 	for (int i = 0; i < n; i++) {
     87 		cin >> t[i];
     88 	}
     89 	
     90 	for (int i = 0; i < n; i++) {
     91 		int d = sum + t[i] - m, k = 0;
     92 		if (d > 0) {
     93 		    for (int j = T; j > 0; j--) {
     94 				int x = j * count[j];
     95 				if (d <= x) {
     96 					k += (d + j - 1) / j;
     97 					break;
     98 				}
     99 				k += count[j];
    100 				d -= x;
    101 			}
    102 		}
    103 		sum += t[i];
    104 		count[t[i]]++;
    105 		cout << k << " ";
    106 	}
    107 }
    108 ```
    109 
    110 Tutorial is loading...
    111 
    112 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"), [cannor147](/profile/cannor147 "Специалист cannor147") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555")
    113 
    114 **Authors' solution**
    115 
    116 ```
    117 #include <bits/stdc++.h>
    118 
    119 using namespace std;
    120 
    121 const int T = 100;
    122 
    123 int main() {
    124 	int n, m;
    125 	cin >> n >> m;
    126 	
    127 	int sum = 0;
    128 	vector<int> t(n), count(T + 1, 0);
    129 	for (int i = 0; i < n; i++) {
    130 		cin >> t[i];
    131 	}
    132 	
    133 	for (int i = 0; i < n; i++) {
    134 		int d = sum + t[i] - m, k = 0;
    135 		if (d > 0) {
    136 		    for (int j = T; j > 0; j--) {
    137 				int x = j * count[j];
    138 				if (d <= x) {
    139 					k += (d + j - 1) / j;
    140 					break;
    141 				}
    142 				k += count[j];
    143 				d -= x;
    144 			}
    145 		}
    146 		sum += t[i];
    147 		count[t[i]]++;
    148 		cout << k << " ";
    149 	}
    150 }
    151 ```
    152 
    153 Tutorial is loading...
    154 
    155 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov")
    156 
    157 **Authors' solution**
    158 
    159 ```
    160 #include <bits/stdc++.h>
    161 
    162 using namespace std;
    163 
    164 int main() {
    165 	int n;
    166 	cin >> n;
    167 	
    168 	vector<pair<int, int>> b(n);
    169 	for (int i = 0; i < n; i++) {
    170 	    int x;
    171 	    cin >> x;
    172 	    b[i] = {x, i};
    173 	}
    174 	sort(b.begin(), b.end());
    175 	
    176 	vector<int> d(n - 1);
    177 	for (int i = 1; i < n; i++) {
    178 		d[i - 1] = b[i].first - b[i - 1].first;
    179 	}
    180 	
    181 	bool f = true;
    182 	for (int i = 2; i < n - 1; i++) {
    183 		f &= d[i] == d[1];
    184 	}
    185 	if (f) {
    186 		cout << b[0].second + 1;
    187 		return 0;
    188 	}
    189 	
    190 	f = true;
    191 	for (int i = 2; i < n - 1; i++) {
    192 		f &= d[i] == b[2].first - b[0].first;
    193 	}
    194 	if (f) {
    195 		cout << b[1].second + 1;
    196 		return 0;
    197 	}
    198 	
    199 	int answer;
    200 	f = false;
    201 	for (int i = 1; i < n - 1; i++) {
    202 		if (d[i] == d[0]) continue;
    203 		if (f) {
    204 			cout << -1;
    205 			return 0;
    206 		} else {
    207 			if (i == n - 2) {
    208 				cout << b[n - 1].second + 1;
    209 				return 0;
    210 			} else {
    211 				if (b[i + 2].first - b[i].first == d[0]) {
    212 					answer = b[i + 1].second;
    213 					f = true;
    214 					i++;
    215 				} else {
    216 					cout << -1;
    217 					return 0;
    218 				}
    219 			}
    220 		}
    221 	}
    222 	
    223 	if (f) {
    224         cout << answer + 1;
    225 	} else {
    226 	    cout << b[n - 1].second + 1;
    227 	}
    228 }
    229 ```
    230 
    231 Tutorial is loading...
    232 
    233 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"), [cannor147](/profile/cannor147 "Специалист cannor147") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555")
    234 
    235 **Authors' solution**
    236 
    237 ```
    238 #include <bits/stdc++.h>
    239 
    240 using namespace std;
    241 
    242 #define forn(i, n) for (int i = 0; i < int(n); i++)
    243 	
    244 int min(int a, int b) {
    245 	return (a < b) ? a : b;
    246 }
    247 int max(int a, int b) {
    248 	return (a > b) ? a : b;
    249 }
    250 
    251 int main() {
    252 	int t;
    253 	cin >> t;
    254 	
    255 	vector<string> lines(2000, "");
    256 	vector<int> vertical_min(26, 2001), vertical_max(26, -1);
    257 	vector<int> horizontal_min(26, 2001), horizontal_max(26, -1);
    258 		
    259 	for (int k = 0; k < t; k++) {
    260 		int n, m;
    261 		cin >> n >> m;
    262 		for (int i = 0; i < n; i++) {
    263 			cin >> lines[i];
    264 		}
    265 		
    266 		for (int b = 0; b < 26; b++) {
    267 			vertical_min[b] = 2001;
    268 			horizontal_min[b] = 2001;
    269 			vertical_max[b] = -1;
    270 			horizontal_max[b] = -1;
    271 		}
    272 		for (int i = 0; i < n; i++) {
    273 			for (int j = 0; j < m; j++) {
    274 				if (lines[i][j] != '.') {
    275 					int b = (int) (lines[i][j] - 'a');
    276 					vertical_min[b] = min(vertical_min[b], i);
    277 					vertical_max[b] = max(vertical_max[b], i);
    278 					horizontal_min[b] = min(horizontal_min[b], j);
    279 					horizontal_max[b] = max(horizontal_max[b], j);
    280 				}
    281 			}
    282 		}
    283 		
    284 		bool f = true, q = false;
    285 		int count = 26;
    286 		for (int b = 25; b >= 0; b--) {
    287 			if (vertical_max[b] == -1) {
    288 				if (!q) {
    289 					count--;
    290 					continue;
    291 				} else {
    292 					vertical_min[b] = vertical_min[b + 1];
    293 					vertical_max[b] = vertical_max[b + 1];
    294 					horizontal_min[b] = horizontal_min[b + 1];
    295 					horizontal_max[b] = horizontal_max[b + 1];
    296 					continue;
    297 				}
    298 			}
    299 			
    300 			q = true;
    301 			if (vertical_max[b] == vertical_min[b]) {
    302 				for (int j = horizontal_min[b]; j <= horizontal_max[b]; j++) {
    303 					if (lines[vertical_max[b]][j] == 'a' + b || (q && lines[vertical_max[b]][j] == '*')) {
    304 						lines[vertical_max[b]][j] = '*';
    305 					} else {
    306 						f = false;
    307 						break;
    308 					}
    309 				}
    310 			} else if (horizontal_max[b] == horizontal_min[b]) {
    311 				for (int i = vertical_min[b]; i <= vertical_max[b]; i++) {
    312 					if (lines[i][horizontal_max[b]] == 'a' + b || (q && lines[i][horizontal_max[b]] == '*')) {
    313 						lines[i][horizontal_max[b]] = '*';
    314 					} else {
    315 						f = false;
    316 						break;
    317 					}
    318 				}
    319 			} else {
    320 				f = false;
    321 			}
    322 			if (!f) {
    323 				break;
    324 			}
    325 		}
    326 		
    327 		if (f) {
    328 			cout << "YES" << endl;
    329 			cout << count << endl;
    330 			for (int i = 0; i < count; i++) {
    331 				cout << vertical_min[i] + 1 << " " << horizontal_min[i] + 1 << " " << vertical_max[i] + 1 << " " << horizontal_max[i] + 1 << endl;
    332 			}
    333 		} else {
    334 			cout << "NO" << endl;
    335 		}
    336 	}
    337 }
    338 ```
    339 
    340 Tutorial is loading...
    341 
    342 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"), [cannor147](/profile/cannor147 "Специалист cannor147") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555")
    343 
    344 **Authors' solution**
    345 
    346 ```
    347 #include <bits/stdc++.h>
    348 
    349 using namespace std;
    350 
    351 #define x first
    352 #define y second
    353 #define pb push_back
    354 #define mp make_pair
    355 #define sqr(a) ((a) * (a))
    356 #define sz(a) int((a).size())
    357 #define all(a) (a).begin(), (a).end()
    358 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    359 #define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
    360 
    361 template<class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
    362 	return out <<  "(" << a.x << ", " << a.y << ")";
    363 }
    364 
    365 template<class A> ostream& operator << (ostream& out, const vector<A> &a) {
    366 	out << "[";
    367 	for (auto it = a.begin(); it != a.end(); ++it) {
    368 		if (it != a.begin())
    369 			out << ", ";
    370 		out << *it;
    371 	}
    372 	return out << "]";
    373 }
    374 
    375 typedef long long li;
    376 typedef long double ld;
    377 typedef pair<int, int> pt;
    378 
    379 const int INF = 1e9;
    380 const li INF64 = 1e18;
    381 const int MOD = 1e9 + 7;
    382 const ld PI = acosl(-1.0);
    383 const ld EPS = 1e-9;
    384 
    385 mt19937 rnd(time(NULL));
    386 mt19937_64 rnd64(time(NULL));
    387 
    388 const int N = 100 * 1000 + 11;
    389 const int MSK = 1 << 9;
    390 
    391 int n, m;
    392 int cnt[MSK];
    393 vector<pt> pz[N];
    394 
    395 bool read() {
    396 	if (scanf("%d %d", &n, &m) != 2)
    397 		return false;
    398 	forn(i, n) {
    399 		int k;
    400 		scanf("%d", &k);
    401 		int msk = 0;
    402 		forn(j, k) {
    403 			int pos;
    404 			scanf("%d", &pos);
    405 			--pos;
    406 			msk |= (1 << pos);
    407 		}
    408 		++cnt[msk];
    409 	}
    410 	return true;
    411 }
    412 
    413 void solve() {
    414 	forn(i, m) {
    415 		int c;
    416 		scanf("%d", &c);
    417 		int msk = 0;
    418 		int k;
    419 		scanf("%d", &k);
    420 		forn(j, k) {
    421 			int pos;
    422 			scanf("%d", &pos);
    423 			--pos;
    424 			msk |= (1 << pos);
    425 		}
    426 		pz[msk].pb(mp(c, i));
    427 		sort(all(pz[msk]));
    428 		while (sz(pz[msk]) > 2) pz[msk].pop_back();
    429 	}
    430 	int ans = 0, cost = 2 * INF + 1;
    431 	pt res = mp(-1, -1);
    432 	forn(p1, MSK) forn(p2, MSK) {
    433 		int curcost = 0;
    434 		int pos1, pos2;
    435 		if (p1 == p2) {
    436 			if (sz(pz[p1]) < 2) continue;
    437 			curcost = pz[p1][0].x + pz[p1][1].x;
    438 			pos1 = pz[p1][0].y;
    439 			pos2 = pz[p1][1].y;
    440 		} else {
    441 			if (sz(pz[p1]) == 0 || sz(pz[p2]) == 0) continue;
    442 			curcost = pz[p1][0].x + pz[p2][0].x;
    443 			pos1 = pz[p1][0].y;
    444 			pos2 = pz[p2][0].y;
    445 		}
    446 		int curans = 0;
    447 		int curmask = p1 | p2;
    448 		forn(pp, MSK) {
    449 			if ((curmask & pp) == pp) {
    450 				curans += cnt[pp];
    451 			}
    452 		}
    453 		if (curans > ans || (curans == ans && curcost < cost)) {
    454 			ans = curans;
    455 			cost = curcost;
    456 			res = mp(pos1, pos2);
    457 		}
    458 	}
    459 	cout << res.x + 1 << " " << res.y + 1 << endl;
    460 }
    461 
    462 int main() {
    463 #ifdef _DEBUG
    464 	freopen("input.txt", "r", stdin);
    465 	//freopen("output.txt", "w", stdout);
    466 	
    467 	int tt = clock();
    468 #endif
    469 
    470 	cout << fixed << setprecision(10);
    471 	cerr << fixed << setprecision(10);
    472 
    473 #ifdef _DEBUG
    474 	while (read()) {
    475 #else
    476 	if (read()) {
    477 #endif
    478 		solve();
    479 		
    480 #ifdef _DEBUG
    481 		cerr << "TIME = " << clock() - tt << endl;
    482 		tt = clock();	
    483 #endif
    484 	}
    485 }
    486 ```
    487 
    488 Tutorial is loading...
    489 
    490 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"), [cannor147](/profile/cannor147 "Специалист cannor147") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555")
    491 
    492 **Authors' solution**
    493 
    494 ```
    495 #include <bits/stdc++.h>
    496 
    497 using namespace std;
    498 
    499 #define forn(i, n) for (int i = 0; i < int(n); i++)
    500 
    501 const int M = 1000000007;
    502 const int N = 16;
    503 
    504 int d[1 << N][4];
    505 
    506 int main() {
    507     int n, T;
    508     cin >> n >> T;
    509     vector<int> durs(n), types(n);
    510     forn(i, n) {
    511         cin >> durs[i] >> types[i];
    512         types[i]--;
    513     }
    514 
    515     int result = 0;
    516     d[0][3] = 1;
    517     forn(mask, 1 << n)
    518         forn(lst, 4) {
    519             forn(j, n)
    520                 if (types[j] != lst && ((mask & (1 << j)) == 0))
    521                     d[mask ^ (1 << j)][types[j]] = (d[mask ^ (1 << j)][types[j]] + d[mask][lst]) % M;
    522             int sum = 0;
    523             forn(i, n)
    524                 if (mask & (1 << i))
    525                     sum += durs[i];
    526             if (sum == T)
    527                 result = (result + d[mask][lst]) % M;
    528         }
    529 
    530     cout << result << endl;
    531 }
    532 ```
    533 
    534 Tutorial is loading...
    535 
    536 Authors: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"), [cannor147](/profile/cannor147 "Специалист cannor147") and [geranazavr555](/profile/geranazavr555 "Эксперт geranazavr555")
    537 
    538 **Authors' solution**
    539 
    540 ```
    541 #include <bits/stdc++.h>
    542 
    543 using namespace std;
    544 
    545 #define forn(i, n) for (int i = 0; i < int(n); i++)
    546 
    547 const int M = 1000000007;
    548 const int N = 51;
    549 const int S = 2501;
    550 
    551 void inc(int& a, int d) {
    552     a += d;
    553     if (a >= M)
    554         a -= M;
    555 }
    556 
    557 int a[N][S];
    558 int bc[N][N][S];
    559 int ways[N][N][N][4];
    560 
    561 int main() {
    562     int n, T;
    563     cin >> n >> T;
    564 
    565     vector<int> cnts(4);
    566     vector<int> durs(4);
    567 
    568     a[0][0] = bc[0][0][0] = 1;
    569     forn(i, n) {
    570         int dur, type;
    571         cin >> dur >> type;
    572         type--;
    573         if (type == 0) {
    574             for (int cnts0 = cnts[0]; cnts0 >= 0; cnts0--)
    575                 forn(durs0, durs[0] + 1)
    576                     inc(a[cnts0 + 1][durs0 + dur], a[cnts0][durs0]);
    577         } else {
    578             for (int cnts1 = cnts[1]; cnts1 >= 0; cnts1--)
    579                 for (int cnts2 = cnts[2]; cnts2 >= 0; cnts2--)
    580                     forn(durs12, durs[1] + durs[2] + 1)
    581                         inc(bc[cnts1 + (type == 1)][cnts2 + (type == 2)][durs12 + dur],
    582                             bc[cnts1][cnts2][durs12]);
    583         }
    584         cnts[type]++;
    585         durs[type] += dur;
    586     }
    587 
    588     ways[0][0][0][3] = 1;
    589     vector<int> c(3);
    590     for (c[0] = 0; c[0] <= cnts[0]; c[0]++)
    591         for (c[1] = 0; c[1] <= cnts[1]; c[1]++)
    592             for (c[2] = 0; c[2] <= cnts[2]; c[2]++)
    593                 forn(lst, 4)
    594                     if (ways[c[0]][c[1]][c[2]][lst] != 0) {
    595                         forn(nxt, 3)
    596                             if (nxt != lst && c[nxt] + 1 <= cnts[nxt]) {
    597                                 vector<int> cn(c);
    598                                 cn[nxt]++;
    599                                 inc(ways[cn[0]][cn[1]][cn[2]][nxt], ways[c[0]][c[1]][c[2]][lst]);
    600                             }
    601                     }
    602 
    603     vector<int> f(N + 1, 1);
    604     forn(i, N)
    605         f[i + 1] = ((long long) f[i]) * (i + 1) % M;
    606 
    607     int result = 0;
    608     for (c[0] = 0; c[0] <= cnts[0]; c[0]++)
    609         forn(durs0, durs[0] + 1)
    610             if (T - durs0 >= 0)
    611                 for (c[1] = 0; c[1] <= cnts[1]; c[1]++)
    612                     for (c[2] = 0; c[2] <= cnts[2]; c[2]++) {
    613                         long long extra = (long long)(a[c[0]][durs0]) * bc[c[1]][c[2]][T - durs0] % M;
    614                         forn(i, 3)
    615                             extra = extra * f[c[i]] % M;
    616                         forn(lst, 3)
    617                             if (c[lst] > 0)
    618                                 inc(result, extra * ways[c[0]][c[1]][c[2]][lst] % M);
    619                     }
    620     
    621     cout << result << endl;
    622 }
    623 ```