codeforces-scrape

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

1814.md (8447B)


      1 Source: https://codeforces.com/blog/entry/114854
      2 
      3 [1814A - Coins](/contest/1814/problem/A "Educational Codeforces Round 146 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15 	n, k = map(int, input().split())
     16 	for x in range(2):
     17 		if n - x * k >= 0 and (n - x * k) % 2 == 0:
     18 			print("YES")
     19 			break
     20 	else:
     21 		print("NO")
     22 ```
     23 
     24 [1814B - Long Legs](/contest/1814/problem/B "Educational Codeforces Round 146 (Rated for Div. 2)")
     25 
     26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     27 
     28 **Tutorial**
     29 
     30 Tutorial is loading...
     31 
     32 **Solution (awoo)**
     33 
     34 ```
     35 for _ in range(int(input())):
     36 	a, b = map(int, input().split())
     37 	ans = a + b
     38 	for m in range(1, 100000):
     39 		ans = min(ans, (a + m - 1) // m + (b + m - 1) // m + (m - 1))
     40 	print(ans)
     41 ```
     42 
     43 [1814C - Search in Parallel](/contest/1814/problem/C "Educational Codeforces Round 146 (Rated for Div. 2)")
     44 
     45 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     46 
     47 **Tutorial**
     48 
     49 Tutorial is loading...
     50 
     51 **Solution (BledDest)**
     52 
     53 ```
     54 #include<bits/stdc++.h>
     55 
     56 using namespace std;
     57 
     58 int main()
     59 {
     60 	int t;
     61 	scanf("%d", &t);
     62 	for(int i = 0; i < t; i++)
     63 	{
     64 		int n;
     65 		scanf("%d", &n);
     66 		vector<int> s(2);
     67 		for(int j = 0; j < 2; j++)
     68 			scanf("%d", &s[j]);
     69 		vector<pair<int, int>> a(n);
     70 		for(int j = 0; j < n; j++)
     71 		{
     72 			scanf("%d", &a[j].first);
     73 			a[j].second = j + 1;
     74 		}
     75 		sort(a.begin(), a.end());
     76 		reverse(a.begin(), a.end());
     77 		vector<vector<int>> lists(2);
     78 		for(int j = 0; j < n; j++)
     79 		{
     80 			int cost1 = s[0] * (lists[0].size() + 1);
     81 			int cost2 = s[1] * (lists[1].size() + 1);
     82 			if(cost1 < cost2)
     83 				lists[0].push_back(a[j].second);
     84 			else
     85 				lists[1].push_back(a[j].second);
     86 		}
     87 		for(int j = 0; j < 2; j++)
     88 		{
     89 		    cout << lists[j].size();
     90 		    for(auto x : lists[j]) cout << " " << x;
     91 		    cout << endl;
     92 		}
     93 	}
     94 }
     95 ```
     96 
     97 [1814D - Balancing Weapons](/contest/1814/problem/D "Educational Codeforces Round 146 (Rated for Div. 2)")
     98 
     99 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    100 
    101 **Tutorial**
    102 
    103 Tutorial is loading...
    104 
    105 **Solution (adedalic)**
    106 
    107 ```
    108 fun main() {
    109     repeat(readln().toInt()) {
    110         val (n, k) = readln().split(' ').map { it.toInt() }
    111         val f = readln().split(' ').map { it.toLong() }
    112         val d = readln().split(' ').map { it.toLong() }
    113 
    114         fun checkAround(pos : Long) : Int {
    115             val qs = Array(2 * k + 1) { MutableList(0) { 0 } }
    116 
    117             fun inside(x : Long, pos: Long) = (pos - k <= x) && (x <= pos + k)
    118             for (i in f.indices) {
    119                 var newD = maxOf(1L, pos / f[i])
    120                 if (newD != d[i] && newD + 1 != d[i] && inside(d[i] * f[i], pos)) {
    121                     val id = (i + 1)
    122                     qs[(d[i] * f[i] - pos + k).toInt()].add(id)
    123                 }
    124                 repeat(2) {
    125                     if (inside(newD * f[i], pos)) {
    126                         val id = if (newD == d[i]) (i + 1) else -(i + 1)
    127                         qs[(newD * f[i] - pos + k).toInt()].add(id)
    128                     }
    129                     newD++
    130                 }
    131                 
    132             }
    133 
    134             val cntPerId = IntArray(n) { 0 }
    135             var cntDistinct = 0
    136             var cntGood = 0
    137 
    138             fun addToSeg(cid : Int) {
    139                 val id = -1 + if (cid > 0) cid else -cid
    140                 val c = if (cid > 0) 1 else 0
    141 
    142                 if (cntPerId[id] == 0)
    143                     cntDistinct++
    144                 cntPerId[id]++
    145 
    146                 cntGood += c
    147             }
    148             fun eraseFromSeg(cid : Int) {
    149                 val id = -1 + if (cid > 0) cid else -cid
    150                 val c = if (cid > 0) 1 else 0
    151 
    152                 cntPerId[id]--
    153                 if (cntPerId[id] == 0)
    154                     cntDistinct--
    155 
    156                 cntGood -= c
    157             }
    158             var ans = 0
    159             for (p in 0 until k)
    160                 qs[p].forEach { addToSeg(it) }
    161             for (p in 0..k) {
    162                 qs[p + k].forEach { addToSeg(it) }
    163                 if (cntDistinct == n)
    164                     ans = maxOf(ans, cntGood)
    165                 qs[p].forEach { eraseFromSeg(it) }
    166             }
    167             return n - ans
    168         }
    169 
    170         var ans = n
    171         for (i in f.indices) {
    172             ans = minOf(ans, checkAround(d[i] * f[i]))
    173         }
    174         println(ans)
    175     }
    176 }
    177 ```
    178 
    179 [1814E - Chain Chips](/contest/1814/problem/E "Educational Codeforces Round 146 (Rated for Div. 2)")
    180 
    181 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    182 
    183 **Tutorial**
    184 
    185 Tutorial is loading...
    186 
    187 **Solution (BledDest)**
    188 
    189 ```
    190 #include<bits/stdc++.h>
    191 
    192 using namespace std;
    193 
    194 typedef long long li;
    195 
    196 const li INF = (li)(1e18);
    197 const int N = 200043;
    198 
    199 struct data
    200 {
    201 	array<array<long long, 2>, 2> d;
    202 	data() {
    203 	    for(int i = 0; i < 2; i++)
    204 			for(int j = 0; j < 2; j++)
    205 				d[i][j] = INF;
    206 	};
    207 	data(li x)
    208 	{
    209 		for(int i = 0; i < 2; i++)
    210 			for(int j = 0; j < 2; j++)
    211 				d[i][j] = INF;
    212 		d[0][0] = 0;
    213 		d[1][1] = x;
    214 	};
    215 	data(data l, data r)
    216 	{
    217 		for(int i = 0; i < 2; i++)
    218 			for(int j = 0; j < 2; j++)
    219 				d[i][j] = INF;
    220 		for(int i = 0; i < 2; i++)
    221 			for(int j = 0; j < 2; j++)
    222 				for(int k = 0; k < 2; k++)
    223 					for(int x = 0; x < 2; x++)
    224 					{
    225 						if(j == 0 && k == 0) continue;
    226 						d[i][x] = min(d[i][x], l.d[i][j] + r.d[k][x]);
    227 					}
    228 	};
    229 };
    230 
    231 data T[4 * N];
    232 li a[N];
    233 
    234 void recalc(int v)
    235 {
    236 	T[v] = data(T[v * 2 + 1], T[v * 2 + 2]);
    237 }
    238 
    239 void build(int v, int l, int r)
    240 {
    241 	if(l == r - 1) T[v] = data(a[l]);
    242 	else
    243 	{
    244 		int m = (l + r) / 2;
    245 		build(v * 2 + 1, l, m);
    246 		build(v * 2 + 2, m, r);
    247 		recalc(v);
    248 	}
    249 }
    250 
    251 void upd(int v, int l, int r, int pos, li val)
    252 {
    253 	if(l == r - 1)
    254 	{
    255 		a[l] = val;
    256 		T[v] = data(a[l]);
    257 	}
    258 	else
    259 	{
    260 		int m = (l + r) / 2;
    261 		if(pos < m)
    262 			upd(v * 2 + 1, l, m, pos, val);
    263 		else
    264 			upd(v * 2 + 2, m, r, pos, val);
    265 		recalc(v);
    266 	}
    267 }
    268 
    269 int main()
    270 {
    271 	int n;
    272 	scanf("%d", &n);
    273 	for(int i = 0; i < n - 1; i++)
    274 	{
    275 		scanf("%lld", &a[i]);
    276 	}
    277 	build(0, 0, n - 1);
    278 	int q;
    279 	scanf("%d", &q);
    280 	for(int i = 0; i < q; i++)
    281 	{
    282 		int x;
    283 		li k;
    284 		scanf("%d %lld", &x, &k);
    285 		upd(0, 0, n - 1, x - 1, k);
    286 		printf("%lld\n", T[0].d[1][1] * 2);
    287 	}
    288 }
    289 ```
    290 
    291 [1814F - Communication Towers](/contest/1814/problem/F "Educational Codeforces Round 146 (Rated for Div. 2)")
    292 
    293 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    294 
    295 **Tutorial**
    296 
    297 Tutorial is loading...
    298 
    299 **Solution (Neon)**
    300 
    301 ```
    302 #include <bits/stdc++.h>
    303 
    304 using namespace std;
    305 
    306 #define sz(a) int((a).size())
    307 
    308 const int N = 200002;
    309 const int V = 50 * N;
    310 
    311 using pt = pair<int, int>;
    312 
    313 int n, m;
    314 pt a[N];
    315 vector<pt> t[4 * N];
    316 int p[N], rk[N], vs[N];
    317 int cntV;
    318 pt g[V];
    319 bool ans[V];
    320 
    321 void upd(int v, int l, int r, int L, int R, pt e) {
    322   if (L >= R) return;
    323   if (l == L && r == R) {
    324     t[v].push_back(e);
    325     return;
    326   }
    327   int m = (l + r) / 2;
    328   upd(v * 2 + 1, l, m, L, min(m, R), e);
    329   upd(v * 2 + 2, m, r, max(m, L), R, e);
    330 }
    331 
    332 int k;
    333 int* ptr[V];
    334 int val[V];
    335 
    336 void upd(int &a, int b) {
    337   ptr[k] = &a;
    338   val[k] = a;
    339   k += 1;
    340   a = b;
    341 }
    342 
    343 int getp(int v) {
    344   return p[v] == v ? v : getp(p[v]);
    345 }
    346 
    347 void unite(int v, int u) {
    348   v = getp(v), u = getp(u);
    349   if (v == u) return;
    350   if (rk[v] > rk[u]) swap(v, u);
    351   upd(p[v], u);
    352   g[cntV] = {vs[v], vs[u]};
    353   upd(vs[u], cntV++);
    354   if (rk[v] == rk[u])
    355     upd(rk[u], rk[u] + 1);
    356 }
    357 
    358 void solve(int v, int l, int r) {
    359   int cur = k;
    360   for (auto& [v, u] : t[v]) 
    361     unite(v, u);
    362   if (l + 1 == r) {
    363     ans[vs[getp(0)]] = 1;
    364   } else {
    365     int m = (l + r) / 2;
    366     solve(v * 2 + 1, l, m);
    367     solve(v * 2 + 2, m, r);
    368   }
    369   while (k > cur) {
    370     k -= 1;
    371     (*ptr[k]) = val[k];
    372   }
    373 }
    374 
    375 int main() {
    376   ios::sync_with_stdio(false); cin.tie(0);
    377   
    378   cin >> n >> m;
    379   for (int i = 0; i < n; ++i)
    380     cin >> a[i].first >> a[i].second;
    381   for (int i = 0; i < m; ++i) {
    382     int x, y;
    383     cin >> x >> y;
    384     --x; --y;
    385     int L = max(a[x].first, a[y].first);
    386     int R = min(a[x].second, a[y].second);
    387     upd(0, 0, N, L, R + 1, {x, y});
    388   }
    389   
    390   for (int i = 0; i < n; ++i) {
    391     p[i] = i;
    392     rk[i] = 1;
    393     vs[i] = i;
    394     g[i] = {-1, -1};
    395   }
    396   
    397   cntV = n;
    398   solve(0, 0, N);
    399   
    400   queue<int> q;
    401   for (int i = 0; i < cntV; ++i) if (ans[i]) 
    402     q.push(i);
    403   
    404   while (!q.empty()) {
    405     int v = q.front(); q.pop();
    406     for (int u : {g[v].first, g[v].second}) {
    407       if (u != -1 && !ans[u]) {
    408         ans[u] = true;
    409         q.push(u);
    410       }
    411     }
    412   }
    413   
    414   for (int i = 0; i < n; ++i) if (ans[i])
    415     cout << i + 1 << ' ';
    416 }
    417 ```