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 ```