codeforces-scrape

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

1809.md (8223B)


      1 Source: https://codeforces.com/blog/entry/114300
      2 
      3 [1809A - Garland](/contest/1809/problem/A "Educational Codeforces Round 145 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Neon)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19   ios::sync_with_stdio(false); cin.tie(0);
     20   int tc;
     21   cin >> tc;
     22   while (tc--) {
     23     string s;
     24     cin >> s;
     25     vector<int> cnt(10);
     26     for (auto c : s) ++cnt[c - '0'];
     27     int mx = *max_element(cnt.begin(), cnt.end());
     28     if (mx == 4) cout << -1;
     29     else if (mx == 3) cout << 6;
     30     else cout << 4;
     31     cout << '\n';
     32   }
     33 }
     34 ```
     35 
     36 [1809B - Points on Plane](/contest/1809/problem/B "Educational Codeforces Round 145 (Rated for Div. 2)")
     37 
     38 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     39 
     40 **Tutorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Solution 1 (adedalic)**
     45 
     46 ```
     47 fun main() {
     48     repeat(readln().toInt()) {
     49         val n = readln().toLong()
     50         var l = (-1).toLong()
     51         var r = 1e9.toLong()
     52         while (r - l > 1) {
     53             val mid = (l + r) / 2
     54             if (mid * mid >= n)
     55                 r = mid
     56             else
     57                 l = mid
     58         }
     59         println(r - 1)
     60     }
     61 }
     62 ```
     63 
     64 **Solution 2 (adedalic)**
     65 
     66 ```
     67 import kotlin.math.sqrt
     68 
     69 fun main() {
     70     repeat(readln().toInt()) {
     71         val n = readln().toLong()
     72         var ans = sqrt(n.toDouble()).toLong()
     73         while (ans * ans > n)
     74             ans--
     75         while (ans * ans < n)
     76             ans++
     77         println(ans - 1)
     78     }
     79 }
     80 ```
     81 
     82 [1809C - Sum on Subarrays](/contest/1809/problem/C "Educational Codeforces Round 145 (Rated for Div. 2)")
     83 
     84 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     85 
     86 **Tutorial**
     87 
     88 Tutorial is loading...
     89 
     90 **Solution (BledDest)**
     91 
     92 ```
     93 def solve(n, k):
     94     if n == 0:
     95         return []
     96     if k < n:
     97         a = [-1 for i in range(n)]
     98         if k > 0:
     99             a[k - 1] = 200
    100         a[k] = -400
    101     else:
    102         a = solve(n - 1, k - n)
    103         a.append(1000)
    104     return a
    105 
    106 t = int(input())
    107 for i in range(t):
    108     n, k = map(int, input().split())
    109     b = solve(n, k)
    110     print(*b)
    111 ```
    112 
    113 [1809D - Binary String Sorting](/contest/1809/problem/D "Educational Codeforces Round 145 (Rated for Div. 2)")
    114 
    115 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    116 
    117 **Tutorial**
    118 
    119 Tutorial is loading...
    120 
    121 **Solution (Neon)**
    122 
    123 ```
    124 #include <bits/stdc++.h>
    125 
    126 using namespace std;
    127 
    128 const long long pw10 = 1e12;
    129 
    130 int main() {
    131   ios::sync_with_stdio(false); cin.tie(0);
    132   int tc;
    133   cin >> tc;
    134   while (tc--) {
    135     string s;
    136     cin >> s;
    137     int n = s.size();
    138     int cnt0 = 0, cnt1 = count(s.begin(), s.end(), '1');
    139     long long ans = 1e18;
    140     if (n == 1) ans = 0;
    141     for (int i = 0; i < n - 1; ++i) {
    142       cnt0 += s[i] == '0';
    143       cnt1 -= s[i] == '1';
    144       int k = cnt0 + cnt1 + (s[i] == '1') + (s[i + 1] == '0');
    145       long long cur = (n - k) * (pw10 + 1);
    146       if (s[i] > s[i + 1]) cur += pw10;
    147       ans = min(ans, cur); 
    148     }
    149     cout << ans << '\n';
    150   }
    151 }
    152 ```
    153 
    154 [1809E - Two Tanks](/contest/1809/problem/E "Educational Codeforces Round 145 (Rated for Div. 2)")
    155 
    156 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    157 
    158 **Tutorial**
    159 
    160 Tutorial is loading...
    161 
    162 **Solution (awoo)**
    163 
    164 ```
    165 #include <bits/stdc++.h>
    166 
    167 #define forn(i, n) for (int i = 0; i < int(n); i++)
    168 
    169 using namespace std;
    170 
    171 int main() {
    172 	int n, a, b;
    173 	scanf("%d%d%d", &n, &a, &b);
    174 	vector<int> v(n);
    175 	forn(i, n) scanf("%d", &v[i]);
    176 	vector<vector<int>> ans(a + 1, vector<int>(b + 1));
    177 	forn(cd, a + b + 1){
    178 		int l = max(0, cd - b), r = min(a, cd);
    179 		int sum = 0;
    180 		for (int x : v){
    181 			sum += x;
    182 			l = max({l, sum, cd + sum - b});
    183 			r = min({r, a + sum, sum + cd});
    184 		}
    185 		if (l > r) l = r = max(0, cd - b);
    186 		int res = l;
    187 		for (int x : v){
    188 			if (x > 0)
    189 				res -= min({res, x, b - (cd - res)});
    190 			else
    191 				res += min({cd - res, -x, a - res});
    192 		}
    193 		forn(c, cd + 1) if (c <= a && cd - c <= b){
    194 			ans[c][cd - c] = (c < l ? res : (c > r ? res + r - l : res + c - l));
    195 		}
    196 	}
    197 	forn(i, a + 1){
    198 		forn(j, b + 1)
    199 			printf("%d ", ans[i][j]);
    200 		puts("");
    201 	}
    202 	return 0;
    203 }
    204 ```
    205 
    206 [1809F - Traveling in Berland](/contest/1809/problem/F "Educational Codeforces Round 145 (Rated for Div. 2)")
    207 
    208 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    209 
    210 **Tutorial (Neon)**
    211 
    212 Tutorial is loading...
    213 
    214 **Solution (awoo)**
    215 
    216 ```
    217 #include<bits/stdc++.h>
    218 
    219 using namespace std;
    220 
    221 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    222 
    223 void solve(){
    224 	int n, k;
    225 	scanf("%d%d", &n, &k);
    226 	vector<int> a(n);
    227 	forn(i, n) scanf("%d", &a[i]);
    228 	vector<int> b(n);
    229 	forn(i, n) scanf("%d", &b[i]);
    230 	
    231 	vector<long long> pr(2 * n + 1);
    232 	forn(i, 2 * n) pr[i + 1] = pr[i] + a[i % n];
    233 	
    234 	vector<long long> dist(n);
    235 	vector<long long> cost(n);
    236 	int cnt = 0;
    237 	for (int i = 2 * n - 1; i >= 0; --i){
    238 		if (i < n){
    239 			if (b[i] == 2){
    240 				dist[i] = 1;
    241 				cost[i] = a[i] * 2;
    242 			}
    243 			else if (cnt == 0){
    244 				dist[i] = 1;
    245 				cost[i] = a[i];
    246 			}
    247 			else{
    248 				int j = lower_bound(pr.begin() + i, pr.begin() + i + cnt + 1, pr[i] + k) - pr.begin();
    249 				assert(j > i);
    250 				dist[i] = j - i;
    251 				if (pr[j] - pr[i] <= k)
    252 					cost[i] = pr[j] - pr[i];
    253 				else
    254 					cost[i] = 2 * (pr[j] - pr[i]) - k;
    255 			}
    256 		}
    257 		if (b[i % n] == 2) ++cnt;
    258 		else cnt = 0;
    259 	}
    260 	
    261 	int pw = 0;
    262 	while ((1 << pw) <= n) ++pw;
    263 	
    264 	vector<vector<long long>> distk(pw, dist);
    265 	vector<vector<long long>> costk(pw, cost);
    266 	for (int j = 1; j < pw; ++j) forn(i, n){
    267 		distk[j][i] = distk[j - 1][i] + distk[j - 1][(i + distk[j - 1][i]) % n];
    268 		costk[j][i] = costk[j - 1][i] + costk[j - 1][(i + distk[j - 1][i]) % n];
    269 	}
    270 	
    271 	forn(i, n){
    272 		int pos = i;
    273 		long long tot = 0;
    274 		long long ans = 0;
    275 		for (int j = pw - 1; j >= 0; --j) if (tot + distk[j][pos] <= n){
    276 			tot += distk[j][pos];
    277 			ans += costk[j][pos];
    278 			pos = (pos + distk[j][pos]) % n;
    279 		}
    280 		if (tot < n) ans += pr[i + n] - pr[i + tot];
    281 		printf("%lld ", ans);
    282 	}
    283 	puts("");
    284 }
    285 
    286 int main(){
    287 	int tc;
    288 	scanf("%d", &tc);
    289 	while (tc--) solve();
    290 }
    291 ```
    292 
    293 [1809G - Prediction](/contest/1809/problem/G "Educational Codeforces Round 145 (Rated for Div. 2)")
    294 
    295 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    296 
    297 **Tutorial**
    298 
    299 Tutorial is loading...
    300 
    301 **Solution (BledDest)**
    302 
    303 ```
    304 #include <bits/stdc++.h>
    305  
    306 using namespace std;
    307 
    308 const int MOD = 998244353;
    309 
    310 int add(int x, int y)
    311 {
    312     return ((x + y) % MOD + MOD) % MOD;
    313 }
    314 
    315 int mul(int x, int y)
    316 {
    317     return x * 1ll * y % MOD;   
    318 }
    319 
    320 int binpow(int x, int y)
    321 {
    322     int z = 1;
    323     while(y)
    324     {
    325         if(y % 2 == 1) z = mul(z, x);
    326         x = mul(x, x);
    327         y /= 2;
    328     }
    329     return z;
    330 }
    331 
    332 int inv(int x)
    333 {
    334     return binpow(x, MOD - 2);    
    335 }
    336 
    337 int divide(int x, int y)
    338 {
    339     return mul(x, inv(y));
    340 }
    341 
    342 int main()
    343 {
    344     int n, k;
    345     scanf("%d %d", &n, &k);
    346     vector<int> a(n);
    347     for(int i = 0; i < n; i++)    
    348         scanf("%d", &a[i]);
    349     
    350     reverse(a.begin(), a.end());
    351 
    352     vector<int> fact(n + 1);
    353     fact[0] = 1;
    354     for(int i = 1; i <= n; i++)
    355         fact[i] = mul(fact[i - 1], i);
    356 
    357     // for each player, we find the first player which doesn't conflict with them
    358     vector<int> first_no_conflict(n);
    359     for(int i = 0; i < n; i++)
    360     {
    361         if(i) first_no_conflict[i] = first_no_conflict[i - 1];
    362         while(first_no_conflict[i] < n && a[first_no_conflict[i]] >= a[i] - k)
    363             first_no_conflict[i]++;
    364     }
    365 
    366     vector<int> dp(n + 1);
    367     if(a[0] - a[1] > k) dp[1] = 1;
    368     for(int i = 1; i < n; i++)
    369     {
    370         // first choice: put a[i] on the first position
    371         // then we put all which conflict with a[i] on any position other than 1
    372         int no_of_conflicting = first_no_conflict[i] - i - 1;
    373         // put all conflicting with a[i] on any position other than 1
    374         // the first one chooses from i positions, the second - from i+1 positions, and so on
    375         // so the number of ways is fact[i + no_of_conflicting - 1] / fact[i - 1]
    376         dp[i + no_of_conflicting + 1] = add(dp[i + no_of_conflicting + 1], mul(dp[i], divide(fact[i + no_of_conflicting - 1], fact[i - 1])));
    377 
    378         // second choice: put a[i] on any other position
    379         dp[i + 1] = add(dp[i + 1], mul(dp[i], i));
    380     }
    381 
    382     printf("%d\n", dp[n]);
    383 }
    384 ```