codeforces-scrape

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

1095.md (4812B)


      1 Source: https://codeforces.com/blog/entry/64130
      2 
      3 [1095A - Repeating Cipher](/contest/1095/problem/A "Codeforces Round 529 (Div. 3)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 using namespace std;
     15 
     16 int main() {
     17     int n;
     18     cin >> n;
     19     string s;
     20     cin >> s;
     21     int index = 0;
     22     int gap = 1;
     23     while (index < n)
     24         cout << s[index], index += gap, gap++;
     25 }
     26 ```
     27 
     28 [1095B - Array Stabilization](/contest/1095/problem/B "Codeforces Round 529 (Div. 3)")
     29 
     30 **Tutorial**
     31 
     32 Tutorial is loading...
     33 
     34 **Solution**
     35 
     36 ```
     37 #include <bits/stdc++.h>
     38 
     39 using namespace std;
     40 
     41 int main() {
     42 #ifdef _DEBUG
     43 	freopen("input.txt", "r", stdin);
     44 //	freopen("output.txt", "w", stdout);
     45 #endif
     46 	
     47 	int n;
     48 	cin >> n;
     49 	vector<int> a(n);
     50 	for (int i = 0; i < n; ++i) {
     51 		cin >> a[i];
     52 	}
     53 	sort(a.begin(), a.end());
     54 	
     55 	cout << min(a[n - 2] - a[0], a[n - 1] - a[1]) << endl;
     56 	
     57 	return 0;
     58 }
     59 ```
     60 
     61 [1095C - Powers Of Two](/contest/1095/problem/C "Codeforces Round 529 (Div. 3)")
     62 
     63 **Tutorial**
     64 
     65 Tutorial is loading...
     66 
     67 **Solution**
     68 
     69 ```
     70 #include<bits/stdc++.h>
     71 
     72 using namespace std;
     73 
     74 int main()
     75 {
     76 	int n, k;
     77 	cin >> n >> k;
     78 	map<int, int> ans;
     79 	queue<int> q;
     80 	for(int i = 0; i <= 30; i++)
     81 		if(n & (1 << i))
     82 		{
     83 			if(i > 0) q.push(1 << i);
     84 			ans[1 << i]++;
     85 		}
     86 	if(int(ans.size()) > k)
     87 	{
     88 		puts("NO");
     89 		return 0;
     90 	}
     91 	int cnt = ans.size();
     92 	while(cnt < k && !q.empty())
     93 	{
     94 		int z = q.front();
     95 		q.pop();
     96 		ans[z]--;
     97 		ans[z / 2] += 2;
     98 		if(z / 2 > 1)
     99 		{
    100 			q.push(z / 2);
    101 			q.push(z / 2);
    102 		}
    103 		cnt++;
    104 	}
    105 	if(cnt < k)
    106 	{
    107 		puts("NO");
    108 		return 0;
    109 	}
    110 	puts("YES");
    111 	for(auto x : ans)
    112 		for(int i = 0; i < x.second; i++)
    113 			printf("%d ", x.first);
    114 	puts("");
    115 	return 0;
    116 }
    117 ```
    118 
    119 [1095D - Circular Dance](/contest/1095/problem/D "Codeforces Round 529 (Div. 3)")
    120 
    121 **Tutorial**
    122 
    123 Tutorial is loading...
    124 
    125 **Solution**
    126 
    127 ```
    128 #include <bits/stdc++.h>
    129 
    130 using namespace std;
    131 
    132 int n;
    133 vector<vector<int>> a;
    134 
    135 void check(int l, int r) {
    136 	vector<int> ans;
    137 	for (int i = 0; i < n; ++i) {
    138 		int nxt = -1;
    139 		if (a[l][0] == r) {
    140 			nxt = a[l][1];
    141 		} else if (a[l][1] == r) {
    142 			nxt = a[l][0];
    143 		} else {
    144 			return;
    145 		}
    146 		ans.push_back(nxt);
    147 		l = r;
    148 		r = nxt;
    149 	}
    150 	for (auto it : ans) {
    151 		cout << it + 1 << " ";
    152 	}
    153 	cout << endl;
    154 	exit(0);
    155 }
    156 
    157 int main() {
    158 #ifdef _DEBUG
    159 	freopen("input.txt", "r", stdin);
    160 //	freopen("output.txt", "w", stdout);
    161 #endif
    162 	
    163 	cin >> n;
    164 	a = vector<vector<int>> (n, vector<int>(2));
    165 	for (int i = 0; i < n; ++i) {
    166 		cin >> a[i][0] >> a[i][1];
    167 		--a[i][0];
    168 		--a[i][1];
    169 	}
    170 	
    171 	check(0, a[0][0]);
    172 	check(0, a[0][1]);
    173 	
    174 	assert(false);
    175 	
    176 	return 0;
    177 }
    178 ```
    179 
    180 [1095E - Almost Regular Bracket Sequence](/contest/1095/problem/E "Codeforces Round 529 (Div. 3)")
    181 
    182 **Tutorial**
    183 
    184 Tutorial is loading...
    185 
    186 **Solution**
    187 
    188 ```
    189 #include <bits/stdc++.h>
    190 
    191 using namespace std;
    192 
    193 int main() {
    194 #ifdef _DEBUG
    195 	freopen("input.txt", "r", stdin);
    196 //	freopen("output.txt", "w", stdout);
    197 #endif
    198 	
    199 	int n;
    200 	string s;
    201 	cin >> n >> s;
    202 	
    203 	string rs(s.rbegin(), s.rend());
    204 	for (int i = 0; i < n; ++i) {
    205 		if (rs[i] == '(') {
    206 			rs[i] = ')';
    207 		} else {
    208 			rs[i] = '(';
    209 		}
    210 	}
    211 	
    212 	vector<int> pref(n + 1), suf(n + 1);
    213 	vector<bool> okp(n + 1), oks(n + 1);
    214 	okp[0] = oks[n] = true;
    215 	for (int i = 0; i < n; ++i) {
    216 		pref[i + 1] = pref[i] + (s[i] == '(' ? +1 : -1);
    217 		okp[i + 1] = okp[i] & (pref[i + 1] >= 0);
    218 		suf[n - i - 1] = suf[n - i] + (rs[i] == '(' ? +1 : -1);
    219 		oks[n - i - 1] = oks[n - i] & (suf[n - i - 1] >= 0);
    220 	}
    221 	
    222 	int ans = 0;
    223 	for (int i = 0; i < n; ++i) {
    224 		if (!okp[i] || !oks[i + 1]) {
    225 			continue;
    226 		}
    227 		if (s[i] == '(') {
    228 			if (pref[i] > 0 && pref[i] - 1 - suf[i + 1] == 0) {
    229 				++ans;
    230 			}
    231 		} else {
    232 			if (pref[i] + 1 - suf[i + 1] == 0) {
    233 				++ans;
    234 			}
    235 		}
    236 	}
    237 	
    238 	cout << ans << endl;
    239 	
    240 	return 0;
    241 }
    242 ```
    243 
    244 [1095F - Make It Connected](/contest/1095/problem/F "Codeforces Round 529 (Div. 3)")
    245 
    246 **Tutorial**
    247 
    248 Tutorial is loading...
    249 
    250 **Solution**
    251 
    252 ```
    253 #include<bits/stdc++.h>
    254 
    255 using namespace std;
    256 
    257 #define x first
    258 #define y second
    259 #define mp make_pair
    260 
    261 typedef pair<long long, pair<int, int> > edge;
    262 
    263 const int N = 200043;
    264 
    265 int p[N];
    266 long long a[N];
    267 
    268 int get_leader(int x)
    269 {
    270 	return (x == p[x] ? x : (p[x] = get_leader(p[x])));
    271 }
    272 
    273 bool merge(int x, int y)
    274 {
    275 	x = get_leader(x);
    276 	y = get_leader(y);
    277 	if(x == y) return false;
    278 	p[x] = y;
    279 	return true;
    280 }
    281 
    282 int main()
    283 {
    284 	int n, m;
    285 	scanf("%d %d", &n, &m);
    286 	for(int i = 0; i < n; i++)
    287 		scanf("%lld", &a[i]);
    288 	vector<edge> es(m);
    289 	for(int i = 0; i < m; i++)
    290 	{
    291 		scanf("%d %d %lld", &es[i].y.x, &es[i].y.y, &es[i].x);
    292 		es[i].y.x--;
    293 		es[i].y.y--;
    294 	}
    295 	int z = min_element(a, a + n) - a;
    296 	for(int i = 0; i < n; i++)
    297 		if(i != z)
    298 			es.push_back(mp(a[i] + a[z], mp(i, z)));
    299 	sort(es.begin(), es.end());
    300 	long long ans = 0;
    301 	for(int i = 0; i < n; i++)
    302 		p[i] = i;
    303 	for(auto e : es)
    304 		if(merge(e.y.x, e.y.y))
    305 			ans += e.x;
    306 	printf("%lld\n", ans);
    307 	return 0;		
    308 }
    309 ```