codeforces-scrape

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

1009.md (9759B)


      1 Source: https://codeforces.com/blog/entry/60630
      2 
      3 [1009A - Game Shopping](/contest/1009/problem/A "Educational Codeforces Round 47 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (Vovuh)**
     10 
     11 ```
     12 n, m = map(int, input().split())
     13 a = list(map(int, input().split()))
     14 b = list(map(int, input().split()))
     15 pos = 0
     16 for i in a:
     17 	pos += (pos < len(b) and b[pos] >= i)
     18 print(pos)
     19 ```
     20 
     21 [1009B - Minimum Ternary String](/contest/1009/problem/B "Educational Codeforces Round 47 (Rated for Div. 2)")
     22 
     23 **Tutorial**
     24 
     25 Tutorial is loading...
     26 
     27 **Solution (Vovuh)**
     28 
     29 ```
     30 #include <bits/stdc++.h>
     31 
     32 using namespace std;
     33 
     34 int main() {
     35 #ifdef _DEBUG
     36 	freopen("input.txt", "r", stdin);
     37 //	freopen("output.txt", "w", stdout);
     38 #endif
     39 	
     40 	string s;
     41 	cin >> s;
     42 	
     43 	string ans;
     44 	
     45 	int cnt = 0;
     46 	for (auto c : s) {
     47 		if (c == '1') ++cnt;
     48 		else ans += c;
     49 	}
     50 	
     51 	int n = ans.size();
     52 	int pos = -1;
     53 	while (pos + 1 < n && ans[pos + 1] == '0') ++pos;
     54 	ans.insert(pos + 1, string(cnt, '1'));
     55 	
     56 	cout << ans << endl;
     57 	
     58 	return 0;
     59 }
     60 ```
     61 
     62 [1009C - Annoying Present](/contest/1009/problem/C "Educational Codeforces Round 47 (Rated for Div. 2)")
     63 
     64 **Tutorial**
     65 
     66 Tutorial is loading...
     67 
     68 **Solution (PikMike)**
     69 
     70 ```
     71 #include <bits/stdc++.h>
     72 
     73 #define forn(i, n) for (int i = 0; i < int(n); i++)
     74 
     75 using namespace std;
     76 
     77 typedef long long li;
     78 
     79 int main() {
     80 	int n, m;
     81 	scanf("%d%d", &n, &m);
     82 	
     83 	li neg = ((n - 1) / 2) * li((n - 1) / 2 + 1);
     84 	if (n % 2 == 0) neg += n / 2;
     85 	li pos = n * li(n - 1) / 2;
     86 	
     87 	li ans = 0;
     88 	forn(i, m){
     89 		int x, d;
     90 		scanf("%d%d", &x, &d);
     91 		ans += x * li(n);
     92 		if (d < 0)
     93 			ans += neg * d;
     94 		else
     95 			ans += pos * d;
     96 	}
     97 	
     98 	printf("%.15f\n", double(ans) / n);
     99 	return 0;
    100 }
    101 ```
    102 
    103 [1009D - Relatively Prime Graph](/contest/1009/problem/D "Educational Codeforces Round 47 (Rated for Div. 2)")
    104 
    105 **Tutorial**
    106 
    107 Tutorial is loading...
    108 
    109 **Solution (PikMike)**
    110 
    111 ```
    112 #include <bits/stdc++.h>
    113 
    114 #define forn(i, n) for (int i = 0; i < int(n); i++)
    115 
    116 using namespace std;
    117 
    118 const int N = 100000;
    119 
    120 pair<int, int> ans[N];
    121 
    122 int main() {
    123 	int n, m;
    124 	scanf("%d%d", &n, &m);
    125 	
    126 	if (m < n - 1) {
    127 		puts("Impossible");
    128 		return 0;
    129 	}
    130 	
    131 	int cur = 0;
    132 	
    133 	forn(i, n) for (int j = i + 1; j < n; ++j){
    134 		if (cur == m)
    135 			break;
    136 		if (__gcd(i + 1, j + 1) == 1)
    137 			ans[cur++] = make_pair(j, i);
    138 	}
    139 	
    140 	if (cur != m){
    141 		puts("Impossible");
    142 		return 0;
    143 	}
    144 	
    145 	puts("Possible");
    146 	forn(i, m)
    147 		printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
    148 	
    149 	return 0;
    150 }
    151 ```
    152 
    153 [1009E - Intercity Travelling](/contest/1009/problem/E "Educational Codeforces Round 47 (Rated for Div. 2)")
    154 
    155 **Tutorial**
    156 
    157 Tutorial is loading...
    158 
    159 **Solution (BledDest)**
    160 
    161 ```
    162 #include<bits/stdc++.h>
    163 
    164 using namespace std;
    165 
    166 const int MOD = 998244353;
    167 
    168 int add(int x, int y)
    169 {
    170     x += y;
    171     while(x >= MOD)
    172         x -= MOD;
    173     while(x < 0)
    174         x += MOD;
    175     return x;
    176 }
    177 
    178 int mul(int x, int y)
    179 {
    180     return (x * 1ll * y) % MOD;
    181 }
    182 
    183 int main()
    184 {
    185     int n;
    186     scanf("%d", &n);
    187     vector<int> a(n);
    188     for(int i = 0; i < n; i++)
    189         scanf("%d", &a[i]);
    190         
    191     int ans = 0;
    192     vector<int> pw2(1, 1);
    193     while(pw2.size() < n)
    194         pw2.push_back(mul(pw2.back(), 2));
    195     int cur = mul(pw2[n - 1], a[0]);
    196     for(int i = 0; i < n; i++)
    197     {
    198         ans = add(ans, cur);
    199         if(i < n - 1)
    200         {
    201             cur = add(cur, -mul(pw2[n - 2 - i], a[i]));
    202             cur = add(cur, mul(pw2[n - 2 - i], a[i + 1]));
    203         }
    204     }
    205     printf("%d\n", ans);
    206 }
    207 ```
    208 
    209 [1009F - Dominant Indices](/contest/1009/problem/F "Educational Codeforces Round 47 (Rated for Div. 2)")
    210 
    211 **Tutorial**
    212 
    213 Tutorial is loading...
    214 
    215 **Solution (BledDest)**
    216 
    217 ```
    218 #define _CRT_SECURE_NO_WARNINGS
    219 
    220 #include <vector>
    221 #include <cstdio>
    222 #include <iostream>
    223 #include <algorithm>
    224 
    225 // RJ? No, thanks
    226 
    227 using namespace std;
    228 
    229 const int N = 1000043;
    230 
    231 struct state
    232 {
    233 	vector<int>* a;
    234 	int cur_max;
    235 	int sz()
    236 	{
    237 		return a->size();
    238 	}
    239 	void add(int i, int val)
    240 	{
    241 		(*a)[i] += val;
    242 		if(make_pair((*a)[i], i) > make_pair((*a)[cur_max], cur_max))
    243 			cur_max = i;
    244 	}
    245 };
    246 
    247 state pull(state z)
    248 {
    249 	if(z.sz() == 0)
    250 	{
    251 		state c;
    252 		c.a = new vector<int>(1, 1);
    253 		c.cur_max = 0;
    254 		return c;
    255 	}
    256 	else
    257 	{
    258 		state c;
    259 		c.a = z.a;
    260 		c.cur_max = z.cur_max;
    261 		c.a->push_back(0);
    262 		c.add(c.sz() - 1, 1);
    263 		return c;
    264 	}
    265 }
    266 
    267 state merge(state a, state b)
    268 {
    269 	if(a.sz() < b.sz())
    270 		swap(a, b);
    271 	state c;
    272 	c.a = a.a;
    273 	c.cur_max = a.cur_max;
    274 	int as = c.sz();
    275 	int bs = b.sz();
    276 	for(int i = 0; i < bs; i++)
    277 		a.add(as - i - 1, (*(b.a))[bs - i - 1]);
    278 	return a;
    279 }
    280 
    281 state s[N];
    282 int ans[N];
    283 vector<int> g[N];
    284 
    285 void dfs(int x, int p = -1)
    286 {
    287 	s[x].a = new vector<int>(0);
    288 	s[x].cur_max = 0;
    289 	for(auto y : g[x])
    290 		if(y != p)
    291 		{
    292 			dfs(y, x);
    293 			s[x] = merge(s[x], s[y]);
    294 		}
    295 	s[x] = pull(s[x]);
    296 	ans[x] = s[x].sz() - s[x].cur_max - 1;
    297 }
    298 
    299 int main()
    300 {
    301 	int n;
    302 	scanf("%d", &n);
    303 	for(int i = 0; i < n - 1; i++)
    304 	{
    305 		int x, y;
    306 		scanf("%d %d", &x, &y);
    307 		--x;
    308 		--y;
    309 		g[x].push_back(y);
    310 		g[y].push_back(x);
    311 	}
    312 	dfs(0);
    313 	for(int i = 0; i < n; i++)
    314 		printf("%d\n", ans[i]);
    315 	return 0;
    316 }
    317 ```
    318 
    319 [1009G - Allowed Letters](/contest/1009/problem/G "Educational Codeforces Round 47 (Rated for Div. 2)")
    320 
    321 **Tutorial**
    322 
    323 Tutorial is loading...
    324 
    325 **Solution (Bleddest)**
    326 
    327 ```
    328 #include<bits/stdc++.h>
    329 
    330 using namespace std;
    331 
    332 #define sz(a) ((int)(a).size())
    333 
    334 struct edge
    335 {
    336     int y;
    337     int c;
    338     int f;
    339     edge() {};
    340     edge(int y, int c, int f) : y(y), c(c), f(f) {};
    341 };
    342 
    343 const int N = 100;
    344 
    345 vector<edge> e;
    346 vector<int> g[N];
    347 int edge_num[N][N];
    348 int char_vertex[6];
    349 int mask_vertex[N];
    350 int used[N];
    351 int cc = 0;
    352 int s, t;
    353 
    354 void add_edge(int x, int y, int c)
    355 {
    356     edge_num[x][y] = sz(e);
    357     g[x].push_back(sz(e));
    358     e.push_back(edge(y, c, 0));
    359     edge_num[y][x] = sz(e);
    360     g[y].push_back(sz(e));
    361     e.push_back(edge(x, 0, 0));
    362 }
    363 
    364 int rem(int num)
    365 {
    366     return e[num].c - e[num].f;
    367 }
    368 
    369 int dfs(int x, int mx)
    370 {
    371     if(x == t) return mx;
    372     if(used[x] == cc) return 0;
    373     used[x] = cc;
    374     for(auto num : g[x])
    375     {
    376         if(rem(num))
    377         {
    378             int pushed = dfs(e[num].y, min(mx, rem(num)));
    379             if(pushed)
    380             {
    381                 e[num].f += pushed;
    382                 e[num ^ 1].f -= pushed;
    383                 return pushed;
    384             }
    385         }
    386     }
    387     return 0;
    388 }
    389 
    390 bool check(int ch, int mask)
    391 {
    392     if((mask & (1 << ch)) == 0)
    393         return false;
    394     int cv = char_vertex[ch];
    395     int mv = mask_vertex[mask];
    396     int e1 = edge_num[s][cv];
    397     int e2 = edge_num[mv][t];
    398     if(e[e1].f == 0 || e[e2].f == 0)
    399         return false;
    400     e[e1].f--;
    401     e[e1 ^ 1].f++;
    402     vector<int> affected_edges;
    403     affected_edges.push_back(e1);
    404     for(auto x : g[cv])
    405     {
    406         if((x & 1) == 0 && e[x].f > 0)
    407         {
    408             affected_edges.push_back(x);
    409             e[x].f--;
    410             e[x ^ 1].f++;
    411             int y = e[x].y;
    412             for(auto x2 : g[y])
    413             {
    414                 if((x2 & 1) == 0)
    415                 {
    416                     affected_edges.push_back(x2);
    417                     e[x2].f--;
    418                     e[x2 ^ 1].f++;
    419                     break;
    420                 }
    421             }
    422             break;
    423         }
    424     }
    425     if(e[e2].f < e[e2].c)
    426     {
    427         e[e1].c--;
    428         e[e2].c--;
    429         return true;
    430     }
    431     affected_edges.push_back(e2);
    432     e[e2].f--;
    433     e[e2 ^ 1].f++;
    434     for(auto x : g[mv])
    435     {
    436         if((x & 1) == 1 && e[x].f < 0)
    437         {
    438             affected_edges.push_back(x ^ 1);
    439             e[x].f++;
    440             e[x ^ 1].f--;
    441             int y = e[x].y;
    442             for(auto x2 : g[y])
    443             {
    444                 if((x2 & 1) == 1)
    445                 {
    446                     affected_edges.push_back(x2 ^ 1);
    447                     e[x2].f++;
    448                     e[x2 ^ 1].f--;
    449                     break;
    450                 }
    451             }
    452             break;
    453         }
    454     }
    455     cc++;
    456     e[e1].c--;
    457     e[e2].c--;
    458     if(dfs(s, 1))
    459         return true;
    460     else
    461     {
    462         e[e1].c++;
    463         e[e2].c++;
    464         for(auto x : affected_edges)
    465         {
    466             e[x].f++;
    467             e[x ^ 1].f--;
    468         }
    469         return false;
    470     }
    471 }
    472 
    473 char buf[100043];
    474 string allowed[100043];
    475 int allowed_mask[100043];
    476 
    477 int main()
    478 {
    479     s = 70;
    480     t = 71;
    481     scanf("%s", buf);
    482     string z = buf;
    483     int n = sz(z);
    484     int m;
    485     scanf("%d", &m);
    486     for(int i = 0; i < n; i++)
    487     {
    488         allowed[i] = "abcdef";
    489         allowed_mask[i] = 63;
    490     }
    491     for(int i = 0; i < m; i++)
    492     {
    493         int idx;
    494         scanf("%d", &idx);
    495         --idx;
    496         scanf("%s", buf);
    497         allowed[idx] = buf;
    498         allowed_mask[idx] = 0;
    499         for(auto x : allowed[idx])
    500         {
    501             allowed_mask[idx] |= (1 << (x - 'a'));
    502         }
    503     }
    504     for(int i = 0; i < 6; i++)
    505         char_vertex[i] = i;
    506     for(int i = 0; i < (1 << 6); i++)
    507         mask_vertex[i] = i + 6;
    508     for(int i = 0; i < (1 << 6); i++)
    509         for(int j = 0; j < 6; j++)
    510             if(i & (1 << j))
    511                 add_edge(char_vertex[j], mask_vertex[i], 100000);
    512     for(int i = 0; i < 6; i++)
    513     {
    514         int cnt = 0;
    515         for(int j = 0; j < n; j++)
    516             if(z[j] == 'a' + i)
    517                 cnt++;
    518         add_edge(s, char_vertex[i], cnt);
    519     }
    520     for(int i = 0; i < (1 << 6); i++)
    521     {
    522         int cnt = 0;
    523         for(int j = 0; j < n; j++)
    524             if(allowed_mask[j] == i)
    525                 cnt++;
    526         add_edge(mask_vertex[i], t, cnt);
    527     }
    528     int flow = 0;
    529     while(true)
    530     {
    531         cc++;
    532         int p = dfs(s, 100000);
    533         if(p)
    534             flow += p;
    535         else
    536             break;
    537     }
    538     if(flow != n)
    539     {
    540         puts("Impossible");
    541         return 0;
    542     }
    543     for(int i = 0; i < n; i++)
    544         for(int j = 0; j < 6; j++)
    545         {
    546             if(check(j, allowed_mask[i]))
    547             {
    548                 printf("%c", j + 'a');
    549                 break;
    550             }
    551         }
    552     puts("");
    553 }
    554 ```