1796.md (7530B)
1 Source: https://codeforces.com/blog/entry/113408 2 3 [1796A - Typical Interview Problem](/contest/1796/problem/A "Educational Codeforces Round 144 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() 19 { 20 string fb; 21 int cur = 1; 22 while(fb.size() < 100) 23 { 24 if(cur % 3 == 0) fb += "F"; 25 if(cur % 5 == 0) fb += "B"; 26 cur++; 27 } 28 int t; 29 cin >> t; 30 for(int i = 0; i < t; i++) 31 { 32 int k; 33 cin >> k; 34 string s; 35 cin >> s; 36 cout << (fb.find(s) != string::npos ? "YES" : "NO") << endl; 37 } 38 } 39 ``` 40 41 [1796B - Asterisk-Minor Template](/contest/1796/problem/B "Educational Codeforces Round 144 (Rated for Div. 2)") 42 43 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 44 45 **Tutorial** 46 47 Tutorial is loading... 48 49 **Solution (awoo)** 50 51 ``` 52 for _ in range(int(input())): 53 a = input() 54 b = input() 55 if a[0] == b[0]: 56 print("YES") 57 print(a[0] + "*") 58 continue 59 if a[-1] == b[-1]: 60 print("YES") 61 print("*" + a[-1]) 62 continue 63 for i in range(len(b) - 1): 64 if (b[i] + b[i + 1]) in a: 65 print("YES") 66 print("*" + b[i] + b[i + 1] + "*") 67 break 68 else: 69 print("NO") 70 ``` 71 72 [1796C - Maximum Set](/contest/1796/problem/C "Educational Codeforces Round 144 (Rated for Div. 2)") 73 74 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 75 76 **Tutorial** 77 78 Tutorial is loading... 79 80 **Solution (BledDest)** 81 82 ``` 83 #include <bits/stdc++.h> 84 85 using namespace std; 86 87 int main() 88 { 89 int t; 90 cin >> t; 91 for(int i = 0; i < t; i++) 92 { 93 int l, r; 94 cin >> l >> r; 95 int max_size = 1; 96 while((l << max_size) <= r) 97 max_size++; 98 int ans2 = (r / (1 << (max_size - 1)) - l + 1); 99 if(max_size > 1) 100 ans2 += (max_size - 1) * max(0, (r / (1 << (max_size - 2)) / 3 - l + 1)); 101 cout << max_size << " " << ans2 << endl; 102 } 103 } 104 ``` 105 106 [1796D - Maximum Subarray](/contest/1796/problem/D "Educational Codeforces Round 144 (Rated for Div. 2)") 107 108 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 109 110 **Tutorial** 111 112 Tutorial is loading... 113 114 **Solution (Neon)** 115 116 ``` 117 #include <bits/stdc++.h> 118 119 using namespace std; 120 121 using li = long long; 122 123 const int N = 222222; 124 const int K = 22; 125 const li INF = 1e18; 126 127 int n, k, x; 128 int a[N]; 129 li dp[N][K][3]; 130 131 int main() { 132 ios::sync_with_stdio(false); cin.tie(0); 133 int tc; 134 cin >> tc; 135 while (tc--) { 136 cin >> n >> k >> x; 137 for (int i = 0; i < n; ++i) cin >> a[i]; 138 for (int i = 0; i <= n; ++i) { 139 for (int j = 0; j <= k; ++j) { 140 for (int t = 0; t < 3; ++t) { 141 dp[i][j][t] = -INF; 142 } 143 } 144 } 145 dp[0][0][0] = 0; 146 for (int i = 0; i < n; ++i) { 147 for (int j = 0; j <= k; ++j) { 148 for (int t = 0; t < 3; ++t) { 149 if (dp[i][j][t] == -INF) continue; 150 for (int jj = j; jj <= min(k, j + 1); ++jj) { 151 li add = a[i] + (j == jj ? -x : x); 152 for (int tt = t; tt < 3; ++tt) { 153 dp[i + 1][jj][tt] = max(dp[i + 1][jj][tt], dp[i][j][t] + (tt == 1 ? add : 0)); 154 } 155 } 156 } 157 } 158 } 159 cout << max(dp[n][k][1], dp[n][k][2]) << '\n'; 160 } 161 } 162 ``` 163 164 [1796E - Colored Subgraphs](/contest/1796/problem/E "Educational Codeforces Round 144 (Rated for Div. 2)") 165 166 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 167 168 **Tutorial** 169 170 Tutorial is loading... 171 172 **Solution (awoo)** 173 174 ``` 175 #include <bits/stdc++.h> 176 177 using namespace std; 178 179 #define forn(i, n) for(int i = 0; i < int(n); i++) 180 181 vector<vector<int>> g; 182 vector<multiset<int>> len; 183 multiset<int> all; 184 185 int getlen(int v){ 186 return len[v].empty() ? 1 : *len[v].begin() + 1; 187 } 188 189 void init(int v, int p = -1){ 190 for (int u : g[v]) if (u != p){ 191 init(u, v); 192 len[v].insert(getlen(u)); 193 } 194 if (int(len[v].size()) > 1){ 195 all.insert(*(++len[v].begin())); 196 } 197 } 198 199 int ans; 200 201 void dfs(int v, int p = -1){ 202 ans = max(ans, min(*len[v].begin() + 1, *all.begin())); 203 204 for (int u : g[v]) if (u != p){ 205 if (int(len[v].size()) > 1) all.erase(all.find(*(++len[v].begin()))); 206 len[v].erase(len[v].find(getlen(u))); 207 if (int(len[v].size()) > 1) all.insert(*(++len[v].begin())); 208 209 if (int(len[u].size()) > 1) all.erase(all.find(*(++len[u].begin()))); 210 len[u].insert(getlen(v)); 211 if (int(len[u].size()) > 1) all.insert(*(++len[u].begin())); 212 213 dfs(u, v); 214 215 if (int(len[u].size()) > 1) all.erase(all.find(*(++len[u].begin()))); 216 len[u].erase(len[u].find(getlen(v))); 217 if (int(len[u].size()) > 1) all.insert(*(++len[u].begin())); 218 219 if (int(len[v].size()) > 1) all.erase(all.find(*(++len[v].begin()))); 220 len[v].insert(getlen(u)); 221 if (int(len[v].size()) > 1) all.insert(*(++len[v].begin())); 222 } 223 } 224 225 int main(){ 226 int t; 227 scanf("%d", &t); 228 while (t--){ 229 int n; 230 scanf("%d", &n); 231 g.assign(n, {}); 232 forn(i, n - 1){ 233 int v, u; 234 scanf("%d%d", &v, &u); 235 --v, --u; 236 g[v].push_back(u); 237 g[u].push_back(v); 238 } 239 len.assign(n, {}); 240 all.clear(); 241 all.insert(n); 242 init(0); 243 ans = 0; 244 dfs(0); 245 printf("%d\n", ans); 246 } 247 } 248 ``` 249 250 [1796F - Strange Triples](/contest/1796/problem/F "Educational Codeforces Round 144 (Rated for Div. 2)") 251 252 Idea: [Neon](/profile/Neon "Candidate Master Neon") and [adedalic](/profile/adedalic "International Master adedalic") 253 254 **Tutorial** 255 256 Tutorial is loading... 257 258 **Solution (Neon)** 259 260 ``` 261 #include <bits/stdc++.h> 262 263 using namespace std; 264 265 #define sz(a) int((a).size()) 266 267 using li = long long; 268 269 const int MAXLEN = 5; 270 271 vector<int> divs(int x) { 272 vector<int> res; 273 for (int i = 1; i * i <= x; ++i) { 274 if (x % i == 0) { 275 res.push_back(i); 276 if (i * i != x) 277 res.push_back(x / i); 278 } 279 } 280 return res; 281 } 282 283 int main() { 284 int A, B, N; 285 cin >> A >> B >> N; 286 287 vector<int> pw(10); 288 pw[0] = 1; 289 for (int i = 1; i < 10; ++i) pw[i] = pw[i - 1] * 10; 290 291 int PW = pw[MAXLEN]; 292 set<array<int, 3>> used; 293 294 vector<int> len(PW); 295 for (int i = 0; i < PW; ++i) 296 len[i] = sz(to_string(i)); 297 298 for (int lenn = 1; lenn <= 9; ++lenn) { 299 int x = pw[lenn] - 1; 300 for (int k2 : divs(x)) { 301 int r = x / k2; 302 for (int d = 1; d < PW; ++d) { 303 for (int lenb = len[d]; lenb <= MAXLEN; ++lenb) { 304 int bg = pw[lenb] - d * li(r) % pw[lenb]; 305 int dd = d / __gcd(d, bg); 306 int lb = (pw[lenb - 1] + bg - 1) / bg; 307 int rb = (pw[lenb] - 1) / bg; 308 for (int g = (lb + dd - 1) / dd * dd; g <= rb; g += dd) { 309 int b = bg * g; 310 assert(b % d == 0); 311 if (b >= B || __gcd(b / d, r) != 1) continue; 312 int ag = (d * li(r) + bg) / pw[lenb]; 313 li n = b / d * li(k2) * ag; 314 if (n < N && ag * g < A && __gcd(ag, bg) == 1 && sz(to_string(n)) == lenn) 315 used.insert({ag * g, b, n}); 316 } 317 } 318 } 319 } 320 } 321 322 int res = 0; 323 for (auto it : used) { 324 li a = it[0], b = it[1], n = it[2]; 325 int lenn = sz(to_string(n)); 326 int lenb = sz(to_string(b)); 327 res += a * b * pw[lenn] + n * b == a * n * pw[lenb] + a * b; 328 } 329 330 cout << res << endl; 331 } 332 ```