codeforces-scrape

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

1263.md (7998B)


      1 Source: https://codeforces.com/blog/entry/71844
      2 
      3 [1263A - Sweet Problem](/contest/1263/problem/A "Codeforces Round 603 (Div. 2)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (MikeMirzayanov)**
     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 main() {
     21     int t;
     22     cin >> t;
     23     forn(tt, t) {   
     24         int a[3];
     25         cin >> a[0] >> a[1] >> a[2];
     26         sort(a, a + 3);
     27         if (a[2] <= a[0] + a[1])
     28             cout << (a[0] + a[1] + a[2]) / 2 << endl;
     29         else
     30             cout << a[0] + a[1] << endl;
     31     }
     32 }
     33 ```
     34 
     35 [1263B - PIN Codes](/contest/1263/problem/B "Codeforces Round 603 (Div. 2)")
     36 
     37 Idea: [Stepavly](/profile/Stepavly "Candidate Master Stepavly")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution (Stepavly)**
     44 
     45 ```
     46 #include <bits/stdc++.h>
     47 using namespace std;
     48 
     49 void solve() {
     50 	int n;
     51 	cin >> n;
     52 
     53 	vector<char> calced(n);
     54 	vector<string> a(n);
     55 	set<string> have;
     56 	int res = 0;
     57 
     58 	for (string &pin : a) {
     59 		cin >> pin;
     60 		have.insert(pin);
     61 	}
     62 
     63 	for (int i = 0; i < n; i++) {
     64 		if (calced[i]) {
     65 			continue;
     66 		}
     67 
     68 		vector<int> sameIds;
     69 
     70 		for (int j = i + 1; j < n; j++) {
     71 			if (a[i] == a[j]) {
     72 				sameIds.push_back(j);
     73 				calced[j] = 1;
     74 				res++;
     75 
     76 				for (int k = 0; k < 4 && a[i] == a[j]; k++) {
     77 					for (char c = '0'; c <= '9'; c++) {
     78 						string t = a[j];
     79 						t[k] = c;
     80 
     81 						if (!have.count(t)) {
     82 							have.insert(t);
     83 							a[j] = t;
     84 							break;
     85 						}
     86 					}
     87 				}
     88 			}
     89 		}
     90 	}
     91 
     92 	cout << res << "\n";
     93 
     94 	for (string& s : a) {
     95 		cout << s << "\n";
     96 	}
     97 }
     98 
     99 int main() {
    100 	int test;
    101 	cin >> test;
    102 
    103 	while (test--) {
    104 		solve();
    105 	}
    106 }
    107 ```
    108 
    109 [1263C - Everyone is a Winner!](/contest/1263/problem/C "Codeforces Round 603 (Div. 2)")
    110 
    111 Idea: [unreal.eugene](/profile/unreal.eugene "Candidate Master unreal.eugene")
    112 
    113 **Tutorial**
    114 
    115 Tutorial is loading...
    116 
    117 **Solution (unreal.eugene)**
    118 
    119 ```
    120 // #pragma GCC optimize("Ofast")
    121 // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    122 
    123 #include <bits/stdc++.h>
    124 #define ALL(s) (s).begin(), (s).end()
    125 #define rALL(s) (s).rbegin(), (s).rend()
    126 #define sz(s) (int)(s).size()
    127 #define mkp make_pair
    128 #define pb push_back
    129 #define sqr(s) ((s) * (s))
    130 
    131 using namespace std;
    132 
    133 typedef long long ll;
    134 typedef long double ld;
    135 typedef unsigned long long ull;
    136 typedef unsigned int ui;
    137 
    138 #ifdef EUGENE
    139 	mt19937 rng(1337);
    140 #else
    141 	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    142 #endif
    143 
    144 void solve() {
    145 	int n;
    146 	cin >> n;
    147 	vector<int> ans;
    148 	int s = (int)sqrtl(n);
    149 	for (int i = 0; i <= s; i++)
    150 		ans.pb(i);
    151 	for (int i = 1; i <= s; i++)
    152 		ans.pb(n / i);
    153 	sort(ALL(ans));
    154 	ans.resize(unique(ALL(ans)) - ans.begin());
    155 	cout << sz(ans) << endl;
    156 	for (int &x : ans)
    157 		cout << x << " ";
    158 	cout << endl;
    159 }
    160 
    161 int main() {
    162 	ios::sync_with_stdio(false); cin.tie(0);
    163 	#ifdef EUGENE
    164 		freopen("input.txt", "r", stdin);
    165 		// freopen("output.txt", "r", stdout);
    166 	#endif
    167 
    168 	int t;
    169 	cin >> t;
    170 	while (t--)
    171 		solve();
    172 }
    173 ```
    174 
    175 [1263D - Secret Passwords](/contest/1263/problem/D "Codeforces Round 603 (Div. 2)")
    176 
    177 Idea: [Stepavly](/profile/Stepavly "Candidate Master Stepavly")
    178 
    179 **Tutorial**
    180 
    181 Tutorial is loading...
    182 
    183 **Solution (Stepavly)**
    184 
    185 ```
    186 #include <bits/stdc++.h>
    187 using namespace std;
    188 
    189 const int N = (int)2e5 + 100;
    190 
    191 vector<int> g[N];
    192 char used[N];
    193 
    194 void addEdge(int v, int u) {
    195 	g[v].push_back(u);
    196 	g[u].push_back(v);
    197 }
    198 
    199 void dfs(int v) {
    200 	used[v] = 1;
    201 
    202 	for (int to : g[v]) {
    203 		if (!used[to]) {
    204 			dfs(to);
    205 		}
    206 	}
    207 }
    208 
    209 int main() {
    210 	int n;
    211 	cin >> n;
    212 
    213 	for (int i = 0; i < n; i++) {
    214 		string s;
    215 		cin >> s;
    216 
    217 		for (char c : s) {
    218 			addEdge(i, n + c - 'a');
    219 		}
    220 	}
    221 
    222 	int res = 0;
    223 
    224 	for (int i = n; i < n + 26; i++) {
    225 		if (!g[i].empty() && !used[i]) {
    226 			dfs(i);
    227 			res++;
    228 		}
    229 	}
    230 
    231 	cout << res;
    232 
    233 	return 0;
    234 }
    235 ```
    236 
    237 [1263E - Editor](/contest/1263/problem/E "Codeforces Round 603 (Div. 2)")
    238 
    239 Idea: [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz")
    240 
    241 **Tutorial**
    242 
    243 Tutorial is loading...
    244 
    245 **Solution (Supermagzzz)**
    246 
    247 ```
    248 #include <bits/stdc++.h>
    249 
    250 using namespace std;
    251 
    252 using ll = long long;
    253 using ld = long double;
    254 
    255 struct MyStack {
    256     int cnt = 0;
    257     int allOpens = 0;
    258     stack<int> s;
    259     stack<int> minValue;
    260     stack<int> maxValue;
    261 
    262     void push(int x) {
    263         s.push(x);
    264         cnt += x;
    265         if (x == 1) {
    266             allOpens += 1;
    267         }
    268         minValue.push((minValue.size() ? min(minValue.top(), cnt) : cnt));
    269         maxValue.push((maxValue.size() ? max(maxValue.top(), cnt) : cnt));
    270     }
    271 
    272     void pop() {
    273         if (s.size() == 0) {
    274             return;
    275         }
    276         cnt -= s.top();
    277         if (s.top() == 1) {
    278             allOpens -= 1;
    279         }
    280         s.pop();
    281         minValue.pop();
    282         maxValue.pop();
    283     }
    284 
    285     int top() {
    286         return s.top();
    287     }
    288 
    289     bool isCorrect() {
    290         return (minValue.size() == 0 || minValue.top() >= 0);
    291     }
    292 
    293     int depth() {
    294         return (maxValue.size() ? maxValue.top() : 0);
    295     }
    296 };
    297 
    298 int main() {
    299     int n;
    300     cin >> n;
    301     string s;
    302     cin >> s;
    303     MyStack left, right;
    304     vector<int> ans(n);
    305     for (int i = 0; i < n; i++) {
    306         right.push(0);
    307     }
    308     left.push(0);
    309     int pos = 0;
    310     for (int i = 0; i < n; i++) {
    311         if (s[i] == 'L') {
    312             if (pos != 0) {
    313                 pos--;
    314                 right.push(-left.top());
    315                 left.pop();
    316             }
    317         } else if (s[i] == 'R') {
    318             pos++;
    319             left.push(-right.top());
    320             right.pop();
    321         } else if (s[i] == '(') {
    322             left.pop();
    323             left.push(1);
    324         } else if (s[i] == ')') {
    325             left.pop();
    326             left.push(-1);
    327         } else {
    328             left.pop();
    329             left.push(0);
    330         }
    331         if (left.isCorrect() && right.isCorrect() && left.cnt == right.cnt) {
    332             cout << max({left.depth(), right.depth(), left.cnt}) << " ";
    333         } else {
    334             cout << "-1 ";
    335         }
    336     }
    337 }           	
    338 ```
    339 
    340 [1263F - Economic Difficulties](/contest/1263/problem/F "Codeforces Round 603 (Div. 2)")
    341 
    342 Idea: [AdvancerMan](/profile/AdvancerMan "Candidate Master AdvancerMan")
    343 
    344 **Tutorial**
    345 
    346 Tutorial is loading...
    347 
    348 **Solution (Rox)**
    349 
    350 ```
    351 #include <bits/stdc++.h>
    352 
    353 using namespace std;
    354 
    355 using ll = long long;
    356 using ld = long double;
    357 
    358 #define sz(x) int((x).size())
    359 #define all(x) begin(x), end(x)
    360 
    361 #ifdef LOCAL
    362     #define eprint(x) cerr << #x << " = " << (x) << endl
    363     #define eprintf(args...) fprintf(stderr, args), fflush(stderr)
    364 #else
    365     #define eprint(x)
    366     #define eprintf(...)
    367 #endif
    368 
    369 vector<vector<int>> precalc(int n, vector<int> p, vector<int> id) {
    370     vector<vector<int>> res(n, vector<int>(n));
    371 
    372     for (int l = 0; l < n; l++) {
    373         vector<int> deg(sz(p));
    374         for (int i = 1; i < sz(p); i++)
    375             deg[p[i]]++;
    376 
    377         int val = 0;
    378         for (int r = l; r < n; r++) {
    379             int v = id[r];
    380             while (v != 0 && deg[v] == 0) {
    381                 deg[p[v]]--;
    382                 v = p[v];
    383                 val++;
    384             }
    385             res[l][r] = val;
    386         }
    387     }
    388 
    389     return res;
    390 }
    391 
    392 int main() {
    393     ios::sync_with_stdio(false);
    394     cin.tie(nullptr);
    395 
    396     int n;
    397     cin >> n;
    398 
    399     vector<vector<int>> p(2);
    400     vector<vector<int>> id(2);
    401     for (int i = 0; i < 2; i++) {
    402         int vn;
    403         cin >> vn;
    404         p[i].resize(vn);
    405         for (int v = 1; v < vn; v++) {
    406             cin >> p[i][v];
    407             p[i][v]--;
    408         }
    409         id[i].resize(n);
    410         for (int j = 0; j < n; j++) {
    411             cin >> id[i][j];
    412             id[i][j]--;
    413         }
    414     }
    415 
    416     vector<vector<vector<int>>> cost(2);
    417     for (int i = 0; i < 2; i++)
    418         cost[i] = precalc(n, p[i], id[i]);
    419 
    420     vector<int> dp(n + 1);
    421     for (int i = 0; i < n; i++) {
    422         for (int j = i + 1; j <= n; j++) {
    423             dp[j] = max(dp[j], dp[i] + max(
    424                 cost[0][i][j - 1],
    425                 cost[1][i][j - 1]
    426             ));
    427         }
    428     }
    429 
    430     cout << dp[n] << endl;
    431 }
    432 ```