1790.md (7255B)
1 Source: https://codeforces.com/blog/entry/111948 2 3 [1790A - Polycarp and the Day of Pi](/contest/1790/problem/A "Codeforces Round 847 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 t = int(input()) 15 pi = '31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679' 16 for _ in range(t): 17 n = input() + '#' 18 for i in range(len(n)): 19 if pi[i] != n[i]: 20 print(i) 21 break 22 ``` 23 24 [1790B - Taisia and Dice](/contest/1790/problem/B "Codeforces Round 847 (Div. 3)") 25 26 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution** 33 34 ``` 35 #include <bits/stdc++.h> 36 37 using namespace std; 38 39 const int MAXN = 55; 40 41 int n, s1, s2; 42 vector<int> res; 43 44 void solve() { 45 res.clear(); 46 int d = s1 - s2; 47 for (; s2 >= d; s2 -= d) 48 res.push_back(d); 49 if (s2) res.push_back(s2); 50 for (int i = 0; i < res.size() && res.size() + 1 < n;) { 51 if (res[i] == 1) { 52 ++i; 53 continue; 54 } 55 --res[i]; 56 res.push_back(1); 57 } 58 res.push_back(d); 59 } 60 61 int main() { 62 int t; cin >> t; 63 while (t--) { 64 cin >> n >> s1 >> s2; 65 solve(); 66 sort(res.begin(), res.end()); 67 for (int x: res) 68 cout << x << ' '; 69 cout << endl; 70 } 71 } 72 ``` 73 74 [1790C - Premutation](/contest/1790/problem/C "Codeforces Round 847 (Div. 3)") 75 76 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 77 78 **Tutorial** 79 80 Tutorial is loading... 81 82 **Solution** 83 84 ``` 85 #include "bits/stdc++.h" 86 using namespace std; 87 int n; 88 89 void solve(){ 90 cin >> n; 91 vector<vector<int>>perm(n, vector<int>(n - 1)); 92 vector<int>p(n, 0); 93 vector<int>cnt(n + 1, 0); 94 for(int i = 0; i < n; i++){ 95 p[i] = i + 1; 96 for(int j = 0; j < n - 1; j++){ 97 cin >> perm[i][j]; 98 if(j == 0) cnt[perm[i][j]]++; 99 } 100 } 101 for(int i = 1; i <= n; i++){ 102 if(cnt[i] == n - 1){ 103 p[0] = i; 104 break; 105 } 106 } 107 for(int i = 0; i < n; i++){ 108 if(perm[i][0] != p[0]){ 109 for(int j = 0; j < n - 1; j++){ 110 p[j + 1] = perm[i][j]; 111 } 112 } 113 } 114 for(int i = 0; i < n; i++) cout << p[i] << ' '; 115 cout << endl; 116 117 } 118 119 int main(){ 120 int t; 121 cin >> t; 122 while(t--){ 123 solve(); 124 } 125 return 0; 126 } 127 ``` 128 129 [1790D - Matryoshkas](/contest/1790/problem/D "Codeforces Round 847 (Div. 3)") 130 131 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 132 133 **Tutorial** 134 135 Tutorial is loading... 136 137 **Solution** 138 139 ``` 140 #include <iostream> 141 #include <vector> 142 #include <queue> 143 #include <map> 144 #include <set> 145 146 using namespace std; 147 148 void solve() { 149 int n; 150 cin >> n; 151 vector<int> a(n); 152 map<int, int> cnt; 153 set<int> b; 154 for (int i = 0; i < n; ++i) { 155 cin >> a[i]; 156 cnt[a[i]]++; 157 b.insert(a[i]); 158 b.insert(a[i] + 1); 159 } 160 int last = 0; 161 int res = 0; 162 for (auto x: b) { 163 int c = cnt[x]; 164 res += max(0, c - last); 165 last = c; 166 } 167 cout << res << '\n'; 168 } 169 170 int main(int argc, char* argv[]) { 171 int t; 172 cin >> t; 173 for (int i = 0; i < t; ++i) { 174 solve(); 175 } 176 } 177 ``` 178 179 [1790E - Vlad and a Pair of Numbers](/contest/1790/problem/E "Codeforces Round 847 (Div. 3)") 180 181 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 182 183 **Tutorial** 184 185 Tutorial is loading... 186 187 **Solution** 188 189 ``` 190 t = int(input()) 191 for _ in range(t): 192 x = int(input()) 193 a = x 194 b = 0 195 for i in range(32, -1, -1): 196 if x & (1 << i) > 0: 197 continue 198 if 2 * x - a - b >= (2 << i): 199 a += 1 << i 200 b += 1 << i 201 if a + b == 2 * x and a ^ b == x: 202 print(a, b) 203 else: 204 print(-1) 205 ``` 206 207 [1790F - Timofey and Black-White Tree](/contest/1790/problem/F "Codeforces Round 847 (Div. 3)") 208 209 Idea: [molney](/profile/molney "Candidate Master molney") 210 211 **Tutorial** 212 213 Tutorial is loading... 214 215 **Solution** 216 217 ``` 218 #include <bits/stdc++.h> 219 using namespace std; 220 221 const int MAXN = 200200; 222 const int INF = 1e9; 223 224 int n, ANS = INF; 225 int crr[MAXN], dist[MAXN], res[MAXN]; 226 bool clr[MAXN]; 227 vector<int> gr[MAXN]; 228 229 void init() { 230 ANS = INF; 231 for (int v = 0; v < n; ++v) 232 gr[v].clear(); 233 fill(dist, dist + n, INF); 234 memset(clr, 0, n); 235 } 236 237 void dfs(int v, int p) { 238 if (dist[v] >= ANS) return; 239 if (clr[v]) ANS = min(ANS, dist[v]); 240 for (int u: gr[v]) { 241 if (u == p) continue; 242 if (dist[v] + 1 < dist[u]) { 243 dist[u] = dist[v] + 1; 244 dfs(u, v); 245 } else ANS = min(ANS, dist[v] + 1 + dist[u]); 246 } 247 } 248 249 void solve() { 250 dist[*crr] = 0; 251 dfs(*crr, -1); 252 clr[*crr] = true; 253 for (int i = 1; i < n; ++i) { 254 dist[crr[i]] = 0; 255 dfs(crr[i], -1); 256 clr[crr[i]] = true; 257 res[i] = ANS; 258 } 259 } 260 261 int main() { 262 int gorilla; cin >> gorilla; 263 while (gorilla--) { 264 cin >> n >> *crr, --(*crr); 265 init(); 266 for (int i = 1; i < n; ++i) 267 cin >> crr[i], --crr[i]; 268 for (int i = 1; i < n; ++i) { 269 int v, u; cin >> v >> u, --v, --u; 270 gr[v].push_back(u); 271 gr[u].push_back(v); 272 } 273 solve(); 274 for (int i = 1; i < n; ++i) 275 cout << res[i] << ' '; 276 cout << '\n'; 277 } 278 } 279 ``` 280 281 [1790G - Tokens on Graph](/contest/1790/problem/G "Codeforces Round 847 (Div. 3)") 282 283 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 284 285 **Tutorial** 286 287 Tutorial is loading... 288 289 **Solution** 290 291 ``` 292 #include<bits/stdc++.h> 293 294 using namespace std; 295 296 void solve() 297 { 298 int n; 299 cin >> n; 300 vector<int> token(n), boni(n); 301 vector<vector<int>> g(n); 302 vector<int> good(n); 303 int m; 304 cin >> m; 305 int p, b; 306 cin >> p >> b; 307 for(int i = 0; i < p; i++) 308 { 309 int x; 310 cin >> x; 311 --x; 312 token[x] = 1; 313 } 314 for(int i = 0; i < b; i++) 315 { 316 int x; 317 cin >> x; 318 --x; 319 boni[x] = 1; 320 } 321 for(int i = 0; i < m; i++) 322 { 323 int x, y; 324 cin >> x >> y; 325 --x; 326 --y; 327 g[x].push_back(y); 328 g[y].push_back(x); 329 } 330 for(int i = 0; i < n; i++) 331 for(auto x : g[i]) 332 if(boni[i] && boni[x]) good[i] = 1; 333 set<int> good_tokens; 334 set<int> not_so_good_tokens; 335 for(int i = 0; i < n; i++) 336 for(auto x : g[i]) 337 { 338 if(token[i] && good[x]) good_tokens.insert(i); 339 else if(token[i] && boni[x]) not_so_good_tokens.insert(i); 340 } 341 vector<int> d(n, int(1e9)); 342 queue<int> q; 343 d[0] = 0; 344 q.push(0); 345 while(!q.empty()) 346 { 347 int k = q.front(); 348 q.pop(); 349 for(auto x : g[k]) 350 { 351 if(d[x] > d[k] + 1) 352 { 353 d[x] = d[k] + 1; 354 if(boni[x]) q.push(x); 355 } 356 } 357 } 358 bool has_ans = false; 359 for(int i = 0; i < n; i++) 360 { 361 if(!token[i] || d[i] > n) continue; 362 has_ans |= (!good_tokens.empty() && (*good_tokens.begin() != i || *good_tokens.rbegin() != i)); 363 int cnt = not_so_good_tokens.size(); 364 if(not_so_good_tokens.count(i)) cnt--; 365 has_ans |= d[i] <= 1 + cnt; 366 } 367 cout << (has_ans ? "YES" : "NO") << endl; 368 } 369 370 int main() 371 { 372 ios_base::sync_with_stdio(0); 373 cin.tie(0); 374 #ifdef _DEBUG 375 freopen("input.txt", "r", stdin); 376 #endif 377 int tc = 1; 378 cin >> tc; 379 for(int i = 0; i < tc; i++) 380 { 381 solve(); 382 } 383 } 384 ```