codeforces-scrape

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

1739.md (9575B)


      1 Source: https://codeforces.com/blog/entry/107461
      2 
      3 [1739A - Immobile Knight](/contest/1739/problem/A "Educational Codeforces Round 136 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution 1 (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15 	n, m = map(int, input().split())
     16 	print(n // 2 + 1, m // 2 + 1)
     17 ```
     18 
     19 **Solution 2 (awoo)**
     20 
     21 ```
     22 #include <bits/stdc++.h>
     23 
     24 #define forn(i, n) for (int i = 0; i < int(n); i++)
     25 
     26 using namespace std;
     27 
     28 int main() {
     29 	int t;
     30 	scanf("%d", &t);
     31 	forn(_, t){
     32 		int n, m;
     33 		scanf("%d%d", &n, &m);
     34 		int svx = 1, svy = 1;
     35 		for (int x = 1; x <= n; ++x){
     36 			for (int y = 1; y <= m; ++y){
     37 				bool ok = true;
     38 				for (int dx : {-2, -1, 1, 2}){
     39 					for (int dy : {-2, -1, 1, 2}){
     40 						if (abs(dx * dy) != 2) continue;
     41 						if (1 <= x + dx && x + dx <= n && 1 <= y + dy && y + dy <= m)
     42 							ok = false;
     43 					}
     44 				}
     45 				if (ok){
     46 					svx = x;
     47 					svy = y;
     48 				}
     49 			}
     50 		}
     51 		printf("%d %d\n", svx, svy);
     52 	}
     53 }
     54 ```
     55 
     56 [1739B - Array Recovery](/contest/1739/problem/B "Educational Codeforces Round 136 (Rated for Div. 2)")
     57 
     58 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     59 
     60 **Tutorial**
     61 
     62 Tutorial is loading...
     63 
     64 **Solution (Neon)**
     65 
     66 ```
     67 for _ in range(int(input())):
     68 	n = int(input())
     69 	ans = [0]
     70 	for x in map(int, input().split()):
     71 		if x != 0 and ans[-1] - x >= 0:
     72 			print(-1)
     73 			break
     74 		else:
     75 			ans.append(ans[-1] + x)
     76 	else:
     77 		print(*ans[1:])
     78 ```
     79 
     80 [1739C - Card Game](/contest/1739/problem/C "Educational Codeforces Round 136 (Rated for Div. 2)")
     81 
     82 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     83 
     84 **Tutorial**
     85 
     86 Tutorial is loading...
     87 
     88 **Solution 1 (BledDest)**
     89 
     90 ```
     91 #include<bits/stdc++.h>
     92 
     93 using namespace std;
     94 
     95 long long dp[65][65][3];
     96 
     97 void solve(int n)
     98 {
     99     memset(dp, 0, sizeof dp);
    100     int k = n / 2;
    101     dp[0][0][2] = 1;
    102     for(int i = 0; i <= k; i++)
    103         for(int j = 0; j <= k; j++)
    104             for(int t = 0; t <= 2; t++)
    105             {
    106                 int turn = (i + j) % 4;
    107                 if (turn == 0 || turn == 3)
    108                 {
    109                     if(i < k) dp[i + 1][j][t == 2 ? 0 : t] += dp[i][j][t];
    110                     if(j < k) dp[i][j + 1][t] += dp[i][j][t];
    111                 }
    112                 else
    113                 {
    114                     if(i < k) dp[i + 1][j][t] += dp[i][j][t];
    115                     if(j < k) dp[i][j + 1][t == 2 ? 1 : t] += dp[i][j][t];
    116                 }
    117             }
    118     for(int i = 0; i < 3; i++)
    119         cout << dp[k][k][i] % 998244353 << " ";
    120     cout << endl;
    121 }
    122 
    123 int main()
    124 {
    125     int t;
    126     cin >> t;
    127     for(int i = 0; i < t; i++)
    128     {
    129         int n;
    130         cin >> n;
    131         solve(n);
    132     }
    133 }
    134 ```
    135 
    136 **Solution 2 (BledDest)**
    137 
    138 ```
    139 def fact(n):
    140     return 1 if n == 0 else n * fact(n - 1)
    141 
    142 def choose(n, k):
    143     return fact(n) // fact(k) // fact(n - k)
    144 
    145 def calc(n):
    146     if n == 2:
    147         return [1, 0, 1]
    148     else:
    149         a = calc(n - 2)
    150         return [choose(n - 1, n // 2) + a[1], choose(n - 2, n // 2) + a[0], 1]
    151 
    152 t = int(input())
    153 for i in range(t):
    154     mod = 998244353
    155     n = int(input())
    156     a = calc(n)
    157     a = list(map(lambda x: x % mod, a))
    158     print(*a)
    159 ```
    160 
    161 [1739D - Reset K Edges](/contest/1739/problem/D "Educational Codeforces Round 136 (Rated for Div. 2)")
    162 
    163 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    164 
    165 **Tutorial**
    166 
    167 Tutorial is loading...
    168 
    169 **Solution (awoo)**
    170 
    171 ```
    172 #include <bits/stdc++.h>
    173 
    174 #define forn(i, n) for (int i = 0; i < int(n); i++)
    175 
    176 using namespace std;
    177 
    178 int n;
    179 vector<vector<int>> g;
    180 
    181 vector<int> st;
    182 vector<int> pd;
    183 
    184 void init(int v, int d){
    185 	st.push_back(v);
    186 	if (int(st.size()) - d >= 0)
    187 		pd[v] = st[st.size() - d];
    188 	for (int u : g[v])
    189 		init(u, d);
    190 	st.pop_back();
    191 }
    192 
    193 vector<char> used;
    194 
    195 void dfs(int v){
    196 	used[v] = true;
    197 	for (int u : g[v]) if (!used[u])
    198 		dfs(u);
    199 }
    200 
    201 int get(int d){
    202 	pd.assign(n, -1);
    203 	init(0, d);
    204 	
    205 	vector<int> ord, h(n);
    206 	queue<int> q;
    207 	q.push(0);
    208 	while (!q.empty()){
    209 		int v = q.front();
    210 		q.pop();
    211 		ord.push_back(v);
    212 		for (int u : g[v]){
    213 			q.push(u);
    214 			h[u] = h[v] + 1;
    215 		}
    216 	}
    217 	reverse(ord.begin(), ord.end());
    218 	
    219 	used.assign(n, 0);
    220 	int res = 0;
    221 	for (int v : ord) if (!used[v] && h[v] > d){
    222 		++res;
    223 		dfs(pd[v]);
    224 	}
    225 	
    226 	return res;
    227 }
    228 
    229 int main() {
    230 	int t;
    231 	scanf("%d", &t);
    232 	while (t--){
    233 		int k;
    234 		scanf("%d%d", &n, &k);
    235 		g.assign(n, vector<int>());
    236 		for (int i = 1; i < n; ++i){
    237 			int p;
    238 			scanf("%d", &p);
    239 			--p;
    240 			g[p].push_back(i);
    241 		}
    242 		int l = 1, r = n - 1;
    243 		int ans = n;
    244 		while (l <= r){
    245 			int m = (l + r) / 2;
    246 			if (get(m) <= k){
    247 				ans = m;
    248 				r = m - 1;
    249 			}
    250 			else{
    251 				l = m + 1;
    252 			}
    253 		}
    254 		printf("%d\n", ans);
    255 	}
    256 	return 0;
    257 }
    258 ```
    259 
    260 [1739E - Cleaning Robot](/contest/1739/problem/E "Educational Codeforces Round 136 (Rated for Div. 2)")
    261 
    262 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    263 
    264 **Tutorial**
    265 
    266 Tutorial is loading...
    267 
    268 **Solution (awoo)**
    269 
    270 ```
    271 #include <bits/stdc++.h>
    272 
    273 using namespace std;
    274 
    275 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    276 
    277 const int INF = 1e9;
    278 
    279 int main(){
    280 	int n;
    281 	cin >> n;
    282 	vector<string> s(2);
    283 	forn(i, 2) cin >> s[i];
    284 	vector<array<array<int, 2>, 2>> dp(n + 1);
    285 	forn(i, n + 1) forn(j, 2) forn(k, 2) dp[i][j][k] = -INF;
    286 	dp[0][0][s[1][0] == '1'] = s[1][0] == '1';
    287 	dp[0][0][0] = 0;
    288 	forn(i, n - 1) forn(j, 2){
    289 		int nxtj = s[j][i + 1] == '1';
    290 		int nxtj1 = s[j ^ 1][i + 1] == '1';
    291 		dp[i + 1][j ^ 1][0] = max(dp[i + 1][j ^ 1][0], dp[i][j][1] + nxtj1);
    292 		dp[i + 1][j][nxtj1] = max(dp[i + 1][j][nxtj1], dp[i][j][0] + nxtj1 + nxtj);
    293 		dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][0] + nxtj);
    294 	}
    295 	cout << max({dp[n - 1][0][0], dp[n - 1][0][1], dp[n - 1][1][0], dp[n - 1][1][1]}) << '\n';
    296 }
    297 ```
    298 
    299 [1739F - Keyboard Design](/contest/1739/problem/F "Educational Codeforces Round 136 (Rated for Div. 2)")
    300 
    301 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    302 
    303 **Tutorial**
    304 
    305 Tutorial is loading...
    306 
    307 **Solution (BledDest)**
    308 
    309 ```
    310 #include<bits/stdc++.h>
    311 
    312 using namespace std;
    313 
    314 const int N = 10043;
    315 const int K = 12;
    316 
    317 int tsz = 0;
    318 int trie[N][K];
    319 int aut[N][K];
    320 int lnk[N];
    321 int p[N];
    322 int pchar[N];
    323 int cost[N];
    324 int ncost[N];
    325 
    326 int newNode()
    327 {
    328     lnk[tsz] = -1;
    329     ncost[tsz] = -1;
    330     cost[tsz] = 0;
    331     for(int i = 0; i < K; i++)
    332     {
    333         trie[tsz][i] = aut[tsz][i] = -1;
    334     }
    335     return tsz++;
    336 }
    337 
    338 int nxt(int x, int y)
    339 {                                 
    340     if(trie[x][y] == -1) 
    341     {
    342         trie[x][y] = newNode();
    343         pchar[trie[x][y]] = y;
    344         p[trie[x][y]] = x;
    345     }
    346     return trie[x][y];
    347 }
    348 
    349 int go(int x, int y);
    350 
    351 int get_lnk(int x)
    352 {
    353     if(lnk[x] != -1) return lnk[x];
    354     int& d = lnk[x];
    355     if(x == 0 || p[x] == 0) return d = 0;
    356     return d = go(get_lnk(p[x]), pchar[x]);    
    357 }
    358 
    359 int go(int x, int y)
    360 {
    361     if(aut[x][y] != -1) return aut[x][y];
    362     int& d = aut[x][y];
    363     if(trie[x][y] != -1) return d = trie[x][y];
    364     if(x == 0) return d = 0;
    365     return d = go(get_lnk(x), y);
    366 }
    367 
    368 void add(string s, int c)
    369 {
    370     int cur = 0;
    371     for(auto x : s) cur = nxt(cur, x - 'a');
    372     cost[cur] += c;     
    373 } 
    374 
    375 int calc(int x)
    376 {
    377     if(ncost[x] != -1) return ncost[x];
    378     ncost[x] = cost[x];
    379     int y = get_lnk(x);
    380     if(y != x) ncost[x] += calc(y);
    381     return ncost[x];
    382 }
    383 
    384 int main()
    385 {
    386     int root = newNode();
    387     int n;
    388     cin >> n;
    389     for(int i = 0; i < n; i++)
    390     {
    391         string s;
    392         int x;
    393         cin >> x >> s;
    394         map<char, set<char>> adj;
    395         for(int j = 0; j + 1 < s.size(); j++)
    396         {
    397             adj[s[j]].insert(s[j + 1]);
    398             adj[s[j + 1]].insert(s[j]);
    399         }
    400         bool bad = false;
    401         string res = "";
    402         char c;
    403         for(c = 'a'; c <= 'l'; c++)
    404         {
    405             if(!adj.count(c)) continue;
    406             if(adj[c].size() >= 3)
    407                 bad = true;
    408             if(adj[c].size() == 1)
    409                 break;
    410         }
    411         if(c == 'm' || bad) continue;
    412         res.push_back(c);
    413         while(adj[c].size() > 0)
    414         {
    415             char d = *adj[c].begin();
    416             adj[c].erase(d);
    417             adj[d].erase(c);
    418             c = d;
    419             res.push_back(c);  
    420         }
    421         bad |= adj.size() != res.size();
    422         map<char, int> pos;
    423         for(int i = 0; i < res.size(); i++)
    424             pos[res[i]] = i;
    425         for(int i = 0; i + 1 < s.size(); i++)
    426             bad |= abs(pos[s[i]] - pos[s[i + 1]]) > 1;
    427         if(bad) continue;
    428         add(res, x);
    429         reverse(res.begin(), res.end());
    430         add(res, x);
    431     }  
    432     int INF = 1e9;
    433     int K = 12;
    434     vector<vector<int>> dp(1 << K, vector<int>(tsz + 1, -INF));
    435     vector<vector<pair<int, int>>> pdp(1 << K, vector<pair<int, int>>(tsz + 1));
    436     dp[0][0] = 0;
    437     for(int i = 0; i < (1 << K); i++)
    438         for(int j = 0; j <= tsz; j++)
    439         {
    440             for(int z = 0; z < K; z++)
    441             {
    442                 if(i & (1 << z)) continue;
    443                 int nstate = go(j, z);
    444                 int add = calc(nstate);
    445                 int nmask = i | (1 << z);
    446                 if(dp[nmask][nstate] < dp[i][j] + add)
    447                 {
    448                     dp[nmask][nstate] = dp[i][j] + add;
    449                     pdp[nmask][nstate] = {z, j};
    450                 }
    451             }
    452         }
    453     string ans = "";
    454     int curmask = (1 << K) - 1;
    455     int curstate = max_element(dp[curmask].begin(), dp[curmask].end()) - dp[curmask].begin();
    456     while(curmask != 0)
    457     {
    458         int cc = pdp[curmask][curstate].first;
    459         int ns = pdp[curmask][curstate].second;
    460         ans.push_back(char('a' + cc));
    461         curmask ^= (1 << cc);
    462         curstate = ns;
    463     }
    464     cout << ans << endl;
    465 }
    466 ```