1487.md (8728B)
1 Source: https://codeforces.com/blog/entry/87873 2 3 [1487A - Arena](/contest/1487/problem/A "Educational Codeforces Round 104 (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 int t; 20 cin >> t; 21 while (t--) { 22 int n; 23 cin >> n; 24 vector<int> a(n); 25 for (int& x : a) cin >> x; 26 cout << n - count(a.begin(), a.end(), *min_element(a.begin(), a.end())) << endl; 27 } 28 } 29 ``` 30 31 [1487B - Cat Cycle](/contest/1487/problem/B "Educational Codeforces Round 104 (Rated for Div. 2)") 32 33 Idea: [adedalic](/profile/adedalic "International Master adedalic") 34 35 **Tutorial** 36 37 Tutorial is loading... 38 39 **Solution (adedalic)** 40 41 ``` 42 fun main() { 43 repeat(readLine()!!.toInt()) { 44 var (n, k) = readLine()!!.split(' ').map { it.toInt() } 45 k-- 46 val floor = n / 2 47 println((k + (n % 2) * k / floor) % n + 1) 48 } 49 } 50 ``` 51 52 [1487C - Minimum Ties](/contest/1487/problem/C "Educational Codeforces Round 104 (Rated for Div. 2)") 53 54 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 55 56 **Tutorial** 57 58 Tutorial is loading... 59 60 **Solution (BledDest)** 61 62 ``` 63 #include<bits/stdc++.h> 64 65 using namespace std; 66 67 int main() 68 { 69 int t; 70 cin >> t; 71 for(int i = 0; i < t; i++) 72 { 73 int n; 74 cin >> n; 75 if(n % 2 == 1) 76 { 77 for(int i = 0; i < n; i++) 78 for(int j = i + 1; j < n; j++) 79 if(j - i <= n / 2) 80 cout << 1 << " "; 81 else 82 cout << -1 << " "; 83 cout << endl; 84 } 85 else 86 { 87 for(int i = 0; i < n; i++) 88 for(int j = i + 1; j < n; j++) 89 if(j - i < n / 2) 90 cout << 1 << " "; 91 else if(j - i == n / 2) 92 cout << 0 << " "; 93 else 94 cout << -1 << " "; 95 cout << endl; 96 } 97 } 98 } 99 ``` 100 101 [1487D - Pythagorean Triples](/contest/1487/problem/D "Educational Codeforces Round 104 (Rated for Div. 2)") 102 103 Idea: [Neon](/profile/Neon "Candidate Master Neon") 104 105 **Tutorial** 106 107 Tutorial is loading... 108 109 **Solution (Neon)** 110 111 ``` 112 #include <bits/stdc++.h> 113 114 using namespace std; 115 116 int main() { 117 int t; 118 cin >> t; 119 while (t--) { 120 int n; 121 cin >> n; 122 int ans = 0; 123 for (int i = 3; i * i <= 2 * n - 1; i += 2) 124 ++ans; 125 cout << ans << '\n'; 126 } 127 } 128 ``` 129 130 [1487E - Cheap Dinner](/contest/1487/problem/E "Educational Codeforces Round 104 (Rated for Div. 2)") 131 132 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 133 134 **Tutorial** 135 136 Tutorial is loading... 137 138 **Solution (BledDest)** 139 140 ``` 141 #include<bits/stdc++.h> 142 143 using namespace std; 144 145 int main() 146 { 147 vector<int> ns(4); 148 for(int i = 0; i < 4; i++) 149 scanf("%d", &ns[i]); 150 vector<vector<int>> cs(4); 151 for(int i = 0; i < 4; i++) 152 { 153 cs[i].resize(ns[i]); 154 for(int j = 0; j < ns[i]; j++) 155 scanf("%d", &cs[i][j]); 156 } 157 vector<vector<vector<int>>> bad(3); 158 for(int i = 0; i < 3; i++) 159 { 160 bad[i].resize(ns[i + 1]); 161 int m; 162 scanf("%d", &m); 163 for(int j = 0; j < m; j++) 164 { 165 int x, y; 166 scanf("%d %d", &x, &y); 167 x--; 168 y--; 169 bad[i][y].push_back(x); 170 } 171 } 172 vector<vector<int>> dp(4); 173 dp[0] = cs[0]; 174 for(int i = 0; i < 3; i++) 175 { 176 dp[i + 1].resize(ns[i + 1]); 177 multiset<int> s; 178 for(int j = 0; j < ns[i]; j++) 179 s.insert(dp[i][j]); 180 for(int j = 0; j < ns[i + 1]; j++) 181 { 182 for(auto k : bad[i][j]) 183 s.erase(s.find(dp[i][k])); 184 if(s.empty()) 185 dp[i + 1][j] = int(4e8 + 43); 186 else 187 dp[i + 1][j] = *s.begin() + cs[i + 1][j]; 188 for(auto k : bad[i][j]) 189 s.insert(dp[i][k]); 190 } 191 } 192 int ans = *min_element(dp[3].begin(), dp[3].end()); 193 if(ans > int(4e8)) 194 ans = -1; 195 cout << ans << endl; 196 } 197 ``` 198 199 [1487F - Ones](/contest/1487/problem/F "Educational Codeforces Round 104 (Rated for Div. 2)") 200 201 Idea: [Neon](/profile/Neon "Candidate Master Neon") 202 203 **Tutorial** 204 205 Tutorial is loading... 206 207 **Solution (Neon)** 208 209 ``` 210 #include <bits/stdc++.h> 211 212 using namespace std; 213 214 #define sz(a) int((a).size()) 215 #define forn(i, n) for (int i = 0; i < int(n); ++i) 216 217 const int N = 250; 218 const int M = 28; 219 const int INF = 1e9; 220 221 int dp[2][M * 2 + 1][N][N]; 222 223 int main() { 224 string s; 225 cin >> s; 226 reverse(s.begin(), s.end()); 227 s += "0"; 228 229 forn(carry, M * 2 + 1) forn(cp, N) forn(cn, N) dp[0][carry][cp][cn] = INF; 230 dp[0][M][N - 1][N - 1] = 0; 231 232 forn(i, sz(s)) { 233 forn(carry, M * 2 + 1) forn(cp, N) forn(cn, N) dp[1][carry][cp][cn] = INF; 234 forn(carry, M * 2 + 1) for (int cp = N - 1; cp >= 0; --cp) for (int cn = N - 1; cn >= 0; --cn) if (dp[0][carry][cp][cn] != INF) { 235 if (cp > 0) dp[0][carry][cp - 1][cn] = min(dp[0][carry][cp - 1][cn], dp[0][carry][cp][cn]); 236 if (cn > 0) dp[0][carry][cp][cn - 1] = min(dp[0][carry][cp][cn - 1], dp[0][carry][cp][cn]); 237 int rcarry = carry - M; 238 int val = rcarry + cp - cn; 239 int digit = val % 10; 240 if (digit < 0) digit += 10; 241 int ncarry = val / 10; 242 if (val < 0 && digit != 0) --ncarry; 243 if (digit == s[i] - '0') dp[1][ncarry + M][cp][cn] = min(dp[1][ncarry + M][cp][cn], dp[0][carry][cp][cn] + cp + cn); 244 } 245 swap(dp[0], dp[1]); 246 } 247 248 int ans = INF; 249 forn(i, N) forn(j, N) ans = min(ans, dp[0][M][i][j]); 250 cout << ans << endl; 251 } 252 ``` 253 254 [1487G - String Counting](/contest/1487/problem/G "Educational Codeforces Round 104 (Rated for Div. 2)") 255 256 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 257 258 **Tutorial** 259 260 Tutorial is loading... 261 262 **Solution (BledDest)** 263 264 ``` 265 #include<bits/stdc++.h> 266 267 using namespace std; 268 269 const int MOD = 998244353; 270 const int N = 402; 271 272 int add(int x, int y) 273 { 274 x += y; 275 while(x >= MOD) x -= MOD; 276 while(x < 0) x += MOD; 277 return x; 278 } 279 280 int sub(int x, int y) 281 { 282 return add(x, -y); 283 } 284 285 int mul(int x, int y) 286 { 287 return (x * 1ll * y) % MOD; 288 } 289 290 int c[26]; 291 int dp[2][N][N][3][3]; 292 int sumDp[N][N]; 293 int p1[N][N]; 294 int p2[N][N]; 295 int n; 296 297 int main() 298 { 299 cin >> n; 300 for(int i = 0; i < 26; i++) 301 cin >> c[i]; 302 for(int i = 0; i < 26; i++) 303 for(int j = 0; j < 26; j++) 304 for(int k = 0; k < 26; k++) 305 if(i != k) 306 { 307 multiset<int> s = {i, j, k}; 308 dp[1][s.count(0)][s.count(1)][min(2, j)][min(2, k)]++; 309 } 310 for(int i = 4; i <= n; i++) 311 { 312 for(int j = 0; j < N; j++) 313 for(int k = 0; k < N; k++) 314 for(int x = 0; x < 3; x++) 315 for(int y = 0; y < 3; y++) 316 { 317 dp[0][j][k][x][y] = dp[1][j][k][x][y]; 318 dp[1][j][k][x][y] = 0; 319 } 320 for(int j = 0; j < N; j++) 321 for(int k = 0; k < N; k++) 322 for(int x = 0; x < 3; x++) 323 for(int y = 0; y < 3; y++) 324 { 325 int cur = dp[0][j][k][x][y]; 326 if(cur == 0) continue; 327 for(int z = 0; z < 3; z++) 328 { 329 int& nw = dp[1][j + (z == 0 ? 1 : 0)][k + (z == 1 ? 1 : 0)][y][z]; 330 nw = add(nw, mul(cur, (z == 2 ? 24 : 1) - (z == x ? 1 : 0))); 331 } 332 } 333 } 334 for(int i = 0; i < N; i++) 335 for(int j = 0; j < N; j++) 336 for(int k = 0; k < 3; k++) 337 for(int l = 0; l < 3; l++) 338 sumDp[i][j] = add(sumDp[i][j], dp[1][i][j][k][l]); 339 for(int i = 0; i < N; i++) 340 { 341 p1[i][N - 1] = sumDp[i][N - 1]; 342 for(int j = N - 2; j >= 0; j--) 343 p1[i][j] = add(sumDp[i][j], p1[i][j + 1]); 344 } 345 for(int j = 0; j < N; j++) 346 { 347 p2[N - 1][j] = p1[N - 1][j]; 348 for(int i = N - 2; i >= 0; i--) 349 p2[i][j] = add(p1[i][j], p2[i + 1][j]); 350 } 351 int ans = p2[0][0]; 352 for(int i = 0; i < 26; i++) 353 { 354 for(int j = 0; j < N; j++) 355 for(int k = c[i] + 1; k < N; k++) 356 ans = sub(ans, sumDp[k][j]); 357 } 358 for(int i = 0; i < 26; i++) 359 for(int j = 0; j < i; j++) 360 ans = add(ans, p2[c[i] + 1][c[j] + 1]); 361 cout << ans << endl; 362 } 363 ```