codeforces-scrape

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

1342.md (6204B)


      1 Source: https://codeforces.com/blog/entry/76633
      2 
      3 [1342A - Road To Zero](/contest/1342/problem/A "Educational Codeforces Round 86 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") and [adedalic](/profile/adedalic "International Master adedalic")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Roms)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15     x, y = map(int, input().split())
     16     a, b = map(int, input().split())
     17     b = min(b, a + a)
     18     if x < y:
     19         x, y= y, x
     20     print(y * b + (x - y) * a)
     21 ```
     22 
     23 [1342B - Binary Period](/contest/1342/problem/B "Educational Codeforces Round 86 (Rated for Div. 2)")
     24 
     25 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     26 
     27 **Tutorial**
     28 
     29 Tutorial is loading...
     30 
     31 **Solution (adedalic)**
     32 
     33 ```
     34 fun main() {
     35     val T = readLine()!!.toInt()
     36     for (tc in 1..T) {
     37         val t = readLine()!!
     38 
     39         val s = t.toCharArray().distinct().joinToString("").repeat(t.length)
     40         println(s)
     41     }
     42 }
     43 ```
     44 
     45 [1342C - Yet Another Counting Problem](/contest/1342/problem/C "Educational Codeforces Round 86 (Rated for Div. 2)")
     46 
     47 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") and [adedalic](/profile/adedalic "International Master adedalic")
     48 
     49 **Tutorial**
     50 
     51 Tutorial is loading...
     52 
     53 **Solution (BledDest)**
     54 
     55 ```
     56 #include<bits/stdc++.h>
     57 
     58 using namespace std;
     59 
     60 const int N = 40043;
     61 
     62 int len;
     63 int p[N];
     64 
     65 void build(int a, int b)
     66 {
     67 	len = a * b;
     68 	p[0] = 0;
     69 	for(int i = 1; i <= len; i++)
     70 	{
     71 		p[i] = p[i - 1];
     72 		if((i % a) % b != (i % b) % a)
     73 			p[i]++;
     74 	}
     75 }
     76 
     77 long long query(long long l)
     78 {
     79 	long long cnt = l / len;
     80 	int rem = l % len;
     81 	return p[len] * 1ll * cnt + p[rem]; 
     82 }
     83 
     84 long long query(long long l, long long r)
     85 {
     86 	return query(r) - query(l - 1);
     87 }
     88 
     89 int main()
     90 {
     91 	int t;
     92 	cin >> t;
     93 	for(int i = 0; i < t; i++)
     94 	{
     95 		int a, b, q;
     96 		cin >> a >> b >> q;
     97 		build(a, b);
     98 		long long l, r;
     99 		for(int j = 0; j < q; j++)
    100 		{
    101 			cin >> l >> r;
    102 			cout << query(l, r) << " ";
    103 		}
    104 		cout << endl;
    105 	}
    106 }
    107 ```
    108 
    109 [1342D - Multiple Testcases](/contest/1342/problem/D "Educational Codeforces Round 86 (Rated for Div. 2)")
    110 
    111 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    112 
    113 **Tutorial**
    114 
    115 Tutorial is loading...
    116 
    117 **Solution (pikmike)**
    118 
    119 ```
    120 #include <bits/stdc++.h>
    121 
    122 #define forn(i, n) for (int i = 0; i < int(n); i++)
    123 
    124 using namespace std;
    125 
    126 int main() {
    127 	int n, k;
    128 	scanf("%d%d", &n, &k);
    129 	vector<int> a(n);
    130 	forn(i, n) scanf("%d", &a[i]);
    131 	vector<int> c(k + 1);
    132 	forn(i, k) scanf("%d", &c[i + 1]);
    133 	
    134 	sort(a.begin(), a.end(), greater<int>());
    135 	int ans = 0;
    136 	for (int i = k, g = 0; i >= 1; --i){
    137 		while (g < n && a[g] == i) ++g;
    138 		ans = max(ans, (g + c[i] - 1) / c[i]);
    139 	}
    140 	vector<vector<int>> res(ans);
    141 	forn(i, n) res[i % ans].push_back(a[i]);
    142 	
    143 	printf("%d\n", ans);
    144 	forn(i, ans){
    145 		printf("%d", int(res[i].size()));
    146 		for (auto it : res[i])
    147 			printf(" %d", it);
    148 		puts("");
    149 	}
    150 	return 0;
    151 }
    152 ```
    153 
    154 [1342E - Placing Rooks](/contest/1342/problem/E "Educational Codeforces Round 86 (Rated for Div. 2)")
    155 
    156 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    157 
    158 **Tutorial**
    159 
    160 Tutorial is loading...
    161 
    162 **Solution (BledDest)**
    163 
    164 ```
    165 #include<bits/stdc++.h>
    166 
    167 using namespace std;
    168 
    169 const int MOD = 998244353;
    170 const int N = 200043;
    171 
    172 int add(int x, int y)
    173 {
    174 	return (x + y) % MOD;
    175 }
    176 
    177 int sub(int x, int y)
    178 {
    179 	return add(x, MOD - y);
    180 }
    181 
    182 int mul(int x, int y)
    183 {
    184 	return (x * 1ll * y) % MOD;
    185 }
    186 
    187 int binpow(int x, int y)
    188 {
    189 	int z = 1;
    190 	while(y > 0)
    191 	{
    192 		if(y % 2 == 1)
    193 			z = mul(z, x);
    194 		x = mul(x, x);
    195 		y /= 2;
    196 	}
    197 	return z;
    198 }
    199 
    200 int inv(int x)
    201 {
    202 	return binpow(x, MOD - 2);
    203 }
    204 
    205 int fact[N];
    206 
    207 int C(int n, int k)
    208 {
    209 	return mul(fact[n], inv(mul(fact[k], fact[n - k])));
    210 }
    211 
    212 int main()
    213 {
    214 	int n, k;
    215 	cin >> n >> k;
    216 	
    217 	if(k > n - 1)
    218 	{
    219 		cout << 0 << endl;
    220 		return 0;
    221 	}
    222 	
    223 	fact[0] = 1;
    224 	for(int i = 1; i <= n; i++)
    225 		fact[i] = mul(i, fact[i - 1]);
    226 	int ans = 0;
    227 	int c = n - k;
    228 	for(int i = c; i >= 0; i--)
    229 		if(i % 2 == c % 2)
    230 			ans = add(ans, mul(binpow(i, n), C(c, i)));
    231 		else
    232 			ans = sub(ans, mul(binpow(i, n), C(c, i)));
    233 	ans = mul(ans, C(n, c));
    234 	if(k > 0)
    235 		ans = mul(ans, 2);
    236 	cout << ans << endl;
    237 }
    238 ```
    239 
    240 [1342F - Make It Ascending](/contest/1342/problem/F "Educational Codeforces Round 86 (Rated for Div. 2)")
    241 
    242 Idea: [Neon](/profile/Neon "Candidate Master Neon")
    243 
    244 **Tutorial**
    245 
    246 Tutorial is loading...
    247 
    248 **Solution (Ne0n25)**
    249 
    250 ```
    251 #include <bits/stdc++.h>
    252 
    253 using namespace std;
    254 
    255 #define x first
    256 #define y second
    257 #define mp make_pair
    258 #define pb push_back
    259 #define sz(a) int((a).size())
    260 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    261 
    262 typedef pair<int, int> pt;
    263 
    264 const int INF = 1e9;
    265 const int N = 15;
    266 
    267 int n;
    268 int a[N];
    269 int sum[1 << N];
    270 int dp[N + 1][1 << N][N + 1];
    271 pt p[N + 1][1 << N][N + 1];
    272 
    273 void solve() {
    274 	scanf("%d", &n);
    275 	forn(i, n) scanf("%d", &a[i]);
    276 	
    277 	forn(mask, 1 << n) {
    278 		sum[mask] = 0;
    279 		forn(i, n) if (mask & (1 << i))
    280 			sum[mask] += a[i];
    281 	}	
    282 	
    283 	forn(cnt, n + 1) forn(mask, 1 << n) forn(pos, n + 1)
    284 		dp[cnt][mask][pos] = INF;
    285 	
    286 	dp[0][0][0] = 0;
    287 	forn(cnt, n) forn(mask, 1 << n) forn(pos, n) if (dp[cnt][mask][pos] < INF) {
    288 		int rmask = mask ^ ((1 << n) - 1);
    289 		for (int nmask = rmask; nmask; nmask = (nmask - 1) & rmask) {
    290 			if (sum[nmask] <= dp[cnt][mask][pos])
    291 				continue;
    292 			if ((nmask >> pos) == 0)
    293 				continue;
    294 			int npos = pos + __builtin_ctz(nmask >> pos) + 1;
    295 			if (dp[cnt + 1][mask | nmask][npos] > sum[nmask]) {
    296 				dp[cnt + 1][mask | nmask][npos] = sum[nmask];
    297 				p[cnt + 1][mask | nmask][npos] = mp(mask, pos);
    298 			}
    299 		}
    300 	}
    301 	
    302 	int acnt = 0, apos = 0;
    303 	forn(cnt, n + 1) forn(pos, n + 1) if (dp[cnt][(1 << n) - 1][pos] < INF)
    304 		acnt = cnt, apos = pos;
    305 		
    306 	vector<pt> ans;
    307 	
    308 	int mask = (1 << n) - 1, pos = apos;
    309 	for (int cnt = acnt; cnt > 0; --cnt) {
    310 		int nmask = p[cnt][mask][pos].x;
    311 		int npos = p[cnt][mask][pos].y;
    312 		forn(i, n) if ((nmask ^ mask) & (1 << i))
    313 			if (i != pos - 1) ans.pb(mp(i, pos - 1));
    314 		mask = nmask, pos = npos;
    315 	}
    316 	
    317 	
    318 	printf("%d\n", sz(ans));
    319 	forn(i, sz(ans)) {
    320 		int from = ans[i].x;
    321 		forn(j, i) from -= ans[j].x < ans[i].x;
    322 		int to = ans[i].y;
    323 		forn(j, i) to -= ans[j].x < ans[i].y;
    324 		printf("%d %d\n", from + 1, to + 1);
    325 	}
    326 }	
    327 
    328 int main() {
    329 	int tc;
    330 	scanf("%d", &tc);
    331 	forn(i, tc) solve();
    332 		
    333 }
    334 ```