codeforces-scrape

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

2004.md (7215B)


      1 Source: https://codeforces.com/blog/entry/132790
      2 
      3 [2004A - Closest Point](/contest/2004/problem/A "Educational Codeforces Round 169 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     n = int(input())
     17     x = list(map(int, input().split()))
     18     if n > 2 or x[0] + 1 == x[-1]:
     19         print('NO')
     20     else:
     21         print('YES')
     22 ```
     23 
     24 [2004B - Game with Doors](/contest/2004/problem/B "Educational Codeforces Round 169 (Rated for Div. 2)")
     25 
     26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     27 
     28 **Tutorial**
     29 
     30 Tutorial is loading...
     31 
     32 **Solution (Neon)**
     33 
     34 ```
     35 #include <bits/stdc++.h>
     36  
     37 using namespace std;
     38  
     39 int main() {
     40   int t;
     41   cin >> t;
     42   while (t--) {
     43     int l, r, L, R;
     44     cin >> l >> r >> L >> R;
     45     int inter = min(r, R) - max(l, L) + 1;
     46     int ans = inter - 1;
     47     if (inter <= 0) {
     48       ans = 1;
     49     } else {
     50       ans += (l != L);
     51       ans += (r != R);
     52     }
     53     cout << ans << '\n';
     54   }
     55 }
     56 ```
     57 
     58 [2004C - Splitting Items](/contest/2004/problem/C "Educational Codeforces Round 169 (Rated for Div. 2)")
     59 
     60 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     61 
     62 **Tutorial**
     63 
     64 Tutorial is loading...
     65 
     66 **Solution (adedalic)**
     67 
     68 ```
     69 fun main() {
     70     repeat(readln().toInt()) {
     71         val (n, k) = readln().split(" ").map { it.toInt() }
     72         val a = readln().split(" ").map { it.toInt() }.sortedDescending().toIntArray()
     73 
     74         var score = 0L
     75         var rem = k
     76         for (i in a.indices) {
     77             if (i % 2 == 0) {
     78                 score += a[i]
     79             }
     80             else {
     81                 val needed = minOf(rem, a[i - 1] - a[i])
     82                 a[i] += needed
     83                 rem -= needed
     84                 score -= a[i]
     85             }
     86         }
     87         println(score)
     88     }
     89 }
     90 ```
     91 
     92 [2004D - Colored Portals](/contest/2004/problem/D "Educational Codeforces Round 169 (Rated for Div. 2)")
     93 
     94 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     95 
     96 **Tutorial**
     97 
     98 Tutorial is loading...
     99 
    100 **Solution (Neon)**
    101 
    102 ```
    103 #include <bits/stdc++.h>
    104  
    105 using namespace std;
    106  
    107 const int INF = 1e9;
    108 const string vars[] = {"BG", "BR", "BY", "GR", "GY", "RY"};
    109  
    110 int main() {
    111   ios::sync_with_stdio(false); cin.tie(0);
    112   int t;
    113   cin >> t;
    114   while (t--) {
    115     int n, q;
    116     cin >> n >> q;
    117     vector<int> a(n);
    118     for (int i = 0; i < n; ++i) {
    119       char s[5];
    120       cin >> s;
    121       a[i] = find(vars, vars + 6, s) - vars;
    122     }
    123     vector<vector<int>> lf(n), rg(n);
    124     for (int o = 0; o < 2; ++o) {
    125       vector<int> last(6, -INF);
    126       for (int i = 0; i < n; ++i) {
    127         last[a[i]] = (o ? n - i - 1 : i);
    128         (o ? rg[n - i - 1] : lf[i]) = last;
    129       }
    130       reverse(a.begin(), a.end());
    131     }
    132     while (q--) {
    133       int x, y;
    134       cin >> x >> y;
    135       --x; --y;
    136       int ans = INF;
    137       for (int j = 0; j < 6; ++j) {
    138         if (a[x] + j != 5 && j + a[y] != 5) {
    139           ans = min(ans, abs(x - lf[x][j]) + abs(lf[x][j] - y));
    140           ans = min(ans, abs(x - rg[x][j]) + abs(rg[x][j] - y));
    141         }
    142       }
    143       if (ans > INF / 2) ans = -1;
    144       cout << ans << '\n';
    145     }
    146   }
    147 }
    148 ```
    149 
    150 [2004E - Not a Nim Problem](/contest/2004/problem/E "Educational Codeforces Round 169 (Rated for Div. 2)")
    151 
    152 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    153 
    154 **Tutorial**
    155 
    156 Tutorial is loading...
    157 
    158 **Solution (BledDest)**
    159 
    160 ```
    161 #include<bits/stdc++.h>
    162  
    163 using namespace std;
    164  
    165 const int MOD = 998244353;
    166  
    167 const int N = int(1e7) + 43;
    168  
    169 int lp[N + 1];
    170 vector<int> pr;
    171 int idx[N + 1];
    172  
    173 void precalc()
    174 {
    175 	for (int i = 2; i <= N; i++) 
    176 	{
    177 		if (lp[i] == 0) 
    178 		{
    179 			lp[i] = i;
    180 			pr.push_back(i);
    181 		}
    182 		for (int j = 0; j < pr.size() && pr[j] <= lp[i] && i * 1ll * pr[j] <= N; ++j)
    183 			lp[i * pr[j]] = pr[j];
    184 	}
    185 	for (int i = 0; i < pr.size(); i++)
    186 		idx[pr[i]] = i + 1; 
    187 }
    188  
    189 int get(int x)
    190 {
    191 	if(x == 1) return 1;
    192  	x = lp[x];
    193  	if(x == 2)
    194  		return 0;
    195  	else return idx[x]; 		
    196 }
    197  
    198 void solve()
    199 {             
    200 	int n;
    201 	scanf("%d", &n);
    202 	int res = 0;
    203 	for(int i = 0; i < n; i++)
    204 	{
    205 	 	int x;
    206 	 	scanf("%d", &x);
    207 	 	res ^= get(x);
    208 	}
    209 	if(res) puts("Alice");
    210 	else puts("Bob");
    211 }
    212  
    213 int main()
    214 {
    215  	precalc();
    216  	int t;
    217  	scanf("%d", &t);
    218  	for(int i = 0; i < t; i++) solve();
    219 }
    220 ```
    221 
    222 [2004F - Make a Palindrome](/contest/2004/problem/F "Educational Codeforces Round 169 (Rated for Div. 2)")
    223 
    224 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    225 
    226 **Tutorial**
    227 
    228 Tutorial is loading...
    229 
    230 **Solution (Neon)**
    231 
    232 ```
    233 #include <bits/stdc++.h>
    234  
    235 using namespace std;
    236 
    237 int main() {
    238   int t;
    239   cin >> t;
    240   while (t--) {
    241     int n;
    242     cin >> n;
    243     vector<int> a(n);
    244     for (auto& x : a) cin >> x;
    245     vector<int> p(n + 1);
    246     for (int i = 0; i < n; ++i) p[i + 1] = p[i] + a[i];
    247     map<int, int> cnt;
    248     long long ans = 0;
    249     for (int len = 0; len <= n; ++len) {
    250       for (int i = 0; i <= n - len; ++i) {
    251         int s = p[i] + p[i + len];
    252         ans += len;
    253         ans -= 2 * cnt[s];
    254         ans -= (s % 2 == 1 || !binary_search(p.begin(), p.end(), s / 2));
    255         cnt[s] += 1;
    256       }
    257     }
    258     cout << ans << '\n';
    259   }
    260 }
    261 ```
    262 
    263 [2004G - Substring Compression](/contest/2004/problem/G "Educational Codeforces Round 169 (Rated for Div. 2)")
    264 
    265 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    266 
    267 **Tutorial**
    268 
    269 Tutorial is loading...
    270 
    271 **Solution (awoo)**
    272 
    273 ```
    274 #include <bits/stdc++.h>
    275  
    276 #define forn(i, n) for (int i = 0; i < int(n); i++)
    277  
    278 using namespace std;
    279  
    280 const int D = 10;
    281 const int INF = 1e9;
    282  
    283 typedef array<array<int, D>, D> mat;
    284  
    285 mat mul(const mat &a, const mat &b, bool fl){
    286 	mat c;
    287 	forn(i, D) forn(j, D) c[i][j] = INF;
    288 	if (fl){
    289 		forn(i, D) forn(j, D){
    290 			c[j][i] = min(c[j][i], min(a[j][0] + b[0][i], a[j][i] + b[i][i]));
    291 			c[j][0] = min(c[j][0], a[j][i] + b[i][0]);
    292 		}
    293 	}
    294 	else{
    295 		forn(i, D) forn(j, D){
    296 			c[i][j] = min(c[i][j], min(a[i][0] + b[0][j], a[i][i] + b[i][j]));
    297 			c[0][j] = min(c[0][j], a[0][i] + b[i][j]);
    298 		}
    299 	}
    300 	return c;
    301 }
    302  
    303 struct minqueue{
    304 	vector<pair<mat, mat>> st1, st2;
    305 	
    306 	void push(const mat &a){
    307 		if (!st1.empty())
    308 			st1.push_back({a, mul(st1.back().second, a, true)});
    309 		else
    310 			st1.push_back({a, a});
    311 	}
    312 	
    313 	void pop(){
    314 		if (st2.empty()){
    315 			st2 = st1;
    316 			reverse(st2.begin(), st2.end());
    317 			st1.clear();
    318 			assert(!st2.empty());
    319 			st2[0].second = st2[0].first;
    320 			forn(i, int(st2.size()) - 1)
    321 				st2[i + 1].second = mul(st2[i + 1].first, st2[i].second, false);
    322 		}
    323 		st2.pop_back();
    324 	}
    325 	
    326 	int get(){
    327 		if (st1.empty()) return st2.back().second[0][0];
    328 		if (st2.empty()) return st1.back().second[0][0];
    329 		int ans = INF;
    330 		forn(i, D) ans = min(ans, st2.back().second[0][i] + st1.back().second[i][0]);
    331 		return ans;
    332 	}
    333 };
    334  
    335 mat tran[D];
    336  
    337 void init(int d){
    338 	forn(i, D) forn(j, D) tran[d][i][j] = INF;
    339 	for (int i = 1; i <= 9; ++i){
    340 		tran[d][i][i] = i;
    341 		tran[d][i][0] = i;
    342 	}
    343 	tran[d][0][d] = 0;
    344 }
    345  
    346 int main() {
    347 	cin.tie(0);
    348 	ios::sync_with_stdio(false);
    349 	for (int i = 1; i <= 9; ++i) init(i);
    350 	int n, k;
    351 	cin >> n >> k;
    352 	string s;
    353 	cin >> s;
    354 	minqueue q;
    355 	forn(i, n){
    356 		q.push(tran[s[i] - '0']);
    357 		if (i - k >= 0) q.pop();
    358 		if (i - k >= -1) cout << q.get() << ' ';
    359 	}
    360 	cout << '\n';
    361 	return 0;
    362 }
    363 ```