codeforces-scrape

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

1697.md (9912B)


      1 Source: https://codeforces.com/blog/entry/103835
      2 
      3 [1697A - Parkway Walk](/contest/1697/problem/A "Educational Codeforces Round 130 (Rated for Div. 2)")
      4 
      5 Idea: [vovuh](/profile/vovuh "Master vovuh")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (vovuh)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19 #ifdef _DEBUG
     20     freopen("input.txt", H"r", stdin);
     21 //  freopen("output.txt", "w", stdout);
     22 #endif
     23     
     24     int tc;
     25     cin >> tc;
     26     while (tc--) {
     27         int n, m;
     28         cin >> n >> m;
     29         int sum = 0;
     30         for (int i = 0; i < n; ++i) {
     31             int x;
     32             cin >> x;
     33             sum += x;
     34         }
     35         cout << max(0, sum - m) << endl;
     36     }
     37     
     38     return 0;
     39 }
     40 ```
     41 
     42 [1697B - Promo](/contest/1697/problem/B "Educational Codeforces Round 130 (Rated for Div. 2)")
     43 
     44 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     45 
     46 **Tutorial**
     47 
     48 Tutorial is loading...
     49 
     50 **Solution (Neon)**
     51 
     52 ```
     53 #include <bits/stdc++.h>
     54 
     55 using namespace std;
     56 
     57 int main() {
     58   ios::sync_with_stdio(false); cin.tie(0);
     59   int n, q;
     60   cin >> n >> q;
     61   vector<long long> p(n), s(n + 1);
     62   for (auto& x : p) cin >> x;
     63   sort(p.begin(), p.end());
     64   for (int i = 0; i < n; ++i) s[i + 1] = s[i] + p[i];
     65   while (q--) {
     66     int x, y;
     67     cin >> x >> y;
     68     cout << s[n - x + y] - s[n - x] << '\n';
     69   }
     70 }
     71 ```
     72 
     73 [1697C - awoo's Favorite Problem](/contest/1697/problem/C "Educational Codeforces Round 130 (Rated for Div. 2)")
     74 
     75 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     76 
     77 **Tutorial**
     78 
     79 Tutorial is loading...
     80 
     81 **Solution (awoo)**
     82 
     83 ```
     84 for _ in range(int(input())):
     85 	n = int(input())
     86 	s = input()
     87 	t = input()
     88 	if s.count('b') != t.count('b'):
     89 		print("NO")
     90 		continue
     91 	j = 0
     92 	for i in range(n):
     93 		if s[i] == 'b':
     94 			continue
     95 		while t[j] == 'b':
     96 			j += 1
     97 		if s[i] != t[j] or (s[i] == 'a' and i > j) or (s[i] == 'c' and i < j):
     98 			print("NO")
     99 			break
    100 		j += 1
    101 	else:
    102 		print("YES")
    103 ```
    104 
    105 [1697D - Guess The String](/contest/1697/problem/D "Educational Codeforces Round 130 (Rated for Div. 2)")
    106 
    107 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    108 
    109 **Tutorial**
    110 
    111 Tutorial is loading...
    112 
    113 **Solution (BledDest)**
    114 
    115 ```
    116 #include<bits/stdc++.h>
    117 
    118 using namespace std;
    119 
    120 char ask_character(int i)
    121 {
    122     cout << "? 1 " << i << endl;
    123     cout.flush();
    124     string s;
    125     cin >> s;
    126     return s[0];
    127 }
    128 
    129 int ask_cnt(int l, int r)
    130 {
    131     cout << "? 2 " << l << " " << r << endl;
    132     cout.flush();
    133     int x;
    134     cin >> x;
    135     return x;
    136 }
    137 
    138 int main()
    139 {
    140     int n;
    141     cin >> n;
    142     string s = "";
    143     vector<vector<int>> cnt(n + 1);
    144     for(int i = 0; i < n; i++)
    145     {
    146         if(i == 0)
    147         {
    148             s.push_back(ask_character(1));
    149             cnt[0] = {1};
    150         }
    151         else
    152         {
    153              int cur = ask_cnt(1, i + 1);
    154              if(cur > cnt[i - 1][0])
    155                 s.push_back(ask_character(i + 1));
    156              else
    157              {
    158                 map<char, int> last;
    159                 for(int j = 0; j < s.size(); j++)
    160                     last[s[j]] = j;
    161                 vector<int> lasts;
    162                 for(auto x : last) lasts.push_back(x.second);
    163                 sort(lasts.begin(), lasts.end());
    164                 int l = 0;
    165                 int r = lasts.size();
    166                 // there is always an occurrence in [lasts[l], i)
    167                 // there is no occurrence in [lasts[r], i)
    168                 while(r - l > 1)
    169                 {
    170                     int m = (l + r) / 2;
    171                     int c = ask_cnt(lasts[m] + 1, i + 1);
    172                     if (c == cnt[i - 1][lasts[m]])
    173                         l = m;
    174                     else
    175                         r = m;
    176                 }   
    177                 s.push_back(s[lasts[l]]);                                                
    178              }
    179              cnt[i].resize(i + 1);
    180              set<char> q;
    181              for(int j = i; j >= 0; j--)
    182              {
    183                 q.insert(s[j]);
    184                 cnt[i][j] = q.size();
    185              }
    186         }
    187     }
    188     cout << "! " << s << endl;
    189     cout.flush();
    190     return 0;
    191 }
    192 ```
    193 
    194 [1697E - Coloring](/contest/1697/problem/E "Educational Codeforces Round 130 (Rated for Div. 2)")
    195 
    196 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    197 
    198 **Tutorial**
    199 
    200 Tutorial is loading...
    201 
    202 **Solution (BledDest)**
    203 
    204 ```
    205 #include<bits/stdc++.h>
    206 
    207 using namespace std;
    208 
    209 const int N = 143;
    210 const int K = 5;
    211 const int MOD = 998244353;
    212 
    213 int add(int x, int y)
    214 {
    215     x += y;
    216     while(x >= MOD) x -= MOD;
    217     while(x < 0) x += MOD;
    218     return x;   
    219 }
    220 
    221 int mul(int x, int y)
    222 {
    223     return (x * 1ll * y) % MOD;
    224 }
    225 
    226 int binpow(int x, int y)
    227 {
    228     int z = 1;
    229     while(y > 0)
    230     {
    231         if(y % 2 == 1) z = mul(z, x);
    232         x = mul(x, x);
    233         y /= 2;
    234     }
    235     return z;
    236 }
    237 
    238 int fact[N];
    239 int rfact[N];
    240 
    241 int A(int n, int k)
    242 {
    243     return mul(fact[n], rfact[n - k]);
    244 }
    245 
    246 int n;
    247 
    248 vector<int> g[N];
    249 int x[N];
    250 int y[N];
    251 int dist[N][N];
    252 int color[N];
    253 int dp[N][N];
    254 
    255 int cc = 0;
    256 set<int> pts;
    257 vector<int> compsize;
    258 
    259 void dfs1(int i)
    260 {
    261     //cerr << i << endl;
    262     if(pts.count(i) == 1) return;
    263     pts.insert(i);
    264     for(auto v : g[i])
    265     {
    266         dfs1(v);
    267     }
    268 }
    269 
    270 void dfs2(int i, int c)
    271 {
    272     if(color[i] == c) return;
    273     color[i] = c;
    274     for(auto v : g[i])
    275         dfs2(v, c);
    276 }
    277 
    278 int main()
    279 {
    280     fact[0] = 1;
    281     for(int i = 1; i < N; i++)
    282         fact[i] = mul(i, fact[i - 1]);
    283     for(int i = 0; i < N; i++)
    284         rfact[i] = binpow(fact[i], MOD - 2);
    285 
    286     scanf("%d", &n);
    287     for(int i = 0; i < n; i++)
    288     {
    289         scanf("%d %d", &x[i], &y[i]);    
    290     }
    291     for(int i = 0; i < n; i++)
    292     {
    293         dist[i][i] = int(1e9);
    294         for(int j = 0; j < n; j++)
    295             if(i != j)
    296                 dist[i][j] = abs(x[i] - x[j]) + abs(y[i] - y[j]);
    297     }
    298     for(int i = 0; i < n; i++)
    299     {
    300         int d = *min_element(dist[i], dist[i] + n);
    301         for(int j = 0; j < n; j++)
    302             if(dist[i][j] == d) g[i].push_back(j);    
    303     }
    304 
    305     for(int i = 0; i < n; i++)
    306     {
    307         if(color[i] != 0) continue;
    308         cc++;
    309         pts.clear();
    310         dfs1(i);
    311         //cerr << "!" << endl; 
    312         int d = *min_element(dist[i], dist[i] + n);                      
    313         set<int> pts2 = pts;
    314         bool bad = false;
    315         for(auto x : pts)
    316             for(auto y : pts2)
    317                 if(x != y && dist[x][y] != d)
    318                     bad = true;
    319         if(bad)           
    320         {
    321             color[i] = cc;
    322             compsize.push_back(1);
    323         }
    324         else
    325         {
    326             dfs2(i, cc);
    327             compsize.push_back(pts.size());
    328         }
    329     }            
    330 
    331     dp[0][0] = 1;
    332     int m = compsize.size();
    333     for(int i = 0; i < m; i++)
    334         for(int j = 0; j < n; j++)
    335         {
    336             if(dp[i][j] == 0) continue;
    337             dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
    338             if(compsize[i] != 1)
    339             {
    340                 dp[i + 1][j + compsize[i]] = add(dp[i + 1][j + compsize[i]], dp[i][j]);
    341             }
    342         }
    343     int ans = 0;
    344     for(int i = 1; i <= n; i++)
    345         ans = add(ans, mul(dp[m][i], A(n, i)));
    346     cout << ans << endl;
    347 }
    348 ```
    349 
    350 [1697F - Too Many Constraints](/contest/1697/problem/F "Educational Codeforces Round 130 (Rated for Div. 2)")
    351 
    352 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    353 
    354 **Tutorial**
    355 
    356 Tutorial is loading...
    357 
    358 **Solution (awoo)**
    359 
    360 ```
    361 #include <bits/stdc++.h>
    362 
    363 #define forn(i, n) for (int i = 0; i < int(n); i++)
    364 
    365 using namespace std;
    366 
    367 struct constraint{
    368 	int tp, i, j, x;
    369 };
    370 
    371 vector<vector<int>> g, tg;
    372 vector<char> used;
    373 vector<int> clr, ord;
    374 
    375 void ts(int v){
    376 	used[v] = true;
    377 	for (int u : g[v]) if (!used[u])
    378 		ts(u);
    379 	ord.push_back(v);
    380 }
    381 
    382 void dfs(int v, int k){
    383 	clr[v] = k;
    384 	for (int u : tg[v]) if (clr[u] == -1)
    385 		dfs(u, k);
    386 }
    387 
    388 void either(int x, int y){
    389 	g[x ^ 1].push_back(y);
    390 	g[y ^ 1].push_back(x);
    391 	tg[y].push_back(x ^ 1);
    392 	tg[x].push_back(y ^ 1);
    393 }
    394 
    395 void implies(int x, int y){
    396 	either(x ^ 1, y);
    397 }
    398 
    399 void must(int x){
    400 	either(x, x);
    401 }
    402 
    403 int main() {
    404 	int t;
    405 	scanf("%d", &t);
    406 	forn(_, t){
    407 		int n, m, k;
    408 		scanf("%d%d%d", &n, &m, &k);
    409 		vector<constraint> c(m);
    410 		forn(i, m){
    411 			scanf("%d%d", &c[i].tp, &c[i].i);
    412 			if (c[i].tp != 1) scanf("%d", &c[i].j);
    413 			scanf("%d", &c[i].x);
    414 			--c[i].i, --c[i].j;
    415 		}
    416 		int vts = n * (k + 2);
    417 		g.assign(2 * vts, vector<int>());
    418 		tg.assign(2 * vts, vector<int>());
    419 		forn(i, n){
    420 			forn(j, (k + 2) - 1)
    421 				implies(2 * (i * (k + 2) + j + 1) + 1, 2 * (i * (k + 2) + j) + 1);
    422 			must(2 * (i * (k + 2) + 1) + 1);
    423 			must(2 * (i * (k + 2) + k + 1));
    424 		}
    425 		forn(i, n - 1) forn(j, k + 2){
    426 			implies(2 * (i * (k + 2) + j) + 1, 2 * ((i + 1) * (k + 2) + j) + 1);
    427 		}
    428 		forn(i, m){
    429 			if (c[i].tp == 1)
    430 				either(2 * (c[i].i * (k + 2) + c[i].x + 1) + 1, 2 * (c[i].i * (k + 2) + c[i].x));
    431 			else if (c[i].tp == 2){
    432 				for (int a = max(1, c[i].x - k); a <= min(k, c[i].x - 1); ++a){
    433 					implies(2 * (c[i].i * (k + 2) + a) + 1, 2 * (c[i].j * (k + 2) + (c[i].x - a) + 1));
    434 					implies(2 * (c[i].j * (k + 2) + a) + 1, 2 * (c[i].i * (k + 2) + (c[i].x - a) + 1));
    435 				}
    436 			}
    437 			else{
    438 				for (int a = max(1, c[i].x - k); a <= min(k, c[i].x - 1); ++a){
    439 					implies(2 * (c[i].i * (k + 2) + a + 1), 2 * (c[i].j * (k + 2) + (c[i].x - a)) + 1);
    440 					implies(2 * (c[i].j * (k + 2) + a + 1), 2 * (c[i].i * (k + 2) + (c[i].x - a)) + 1);
    441 				}
    442 			}
    443 		}
    444 		used.assign(2 * vts, 0);
    445 		ord.clear();
    446 		forn(i, used.size()) if (!used[i]) ts(i);
    447 		reverse(ord.begin(), ord.end());
    448 		clr.assign(2 * vts, -1);
    449 		int cc = 0;
    450 		for (int v : ord) if (clr[v] == -1){
    451 			dfs(v, cc);
    452 			++cc;
    453 		}
    454 		vector<int> vals(vts);
    455 		bool ans = true;
    456 		forn(i, vts){
    457 			if (clr[2 * i] == clr[2 * i + 1]){
    458 				ans = false;
    459 				break;
    460 			}
    461 			vals[i] = (clr[2 * i] < clr[2 * i + 1]);
    462 		}
    463 		if (!ans){
    464 			puts("-1");
    465 			continue;
    466 		}
    467 		forn(i, n){
    468 			int lst = 0;
    469 			forn(j, k + 2) if (vals[i * (k + 2) + j])
    470 				lst = j;
    471 			printf("%d ", lst);
    472 		}
    473 		puts("");
    474 	}
    475 	return 0;
    476 }
    477 ```