734.md (6654B)
1 Source: https://codeforces.com/blog/entry/48397 2 3 Tutorial for the tasks of the contest. If something isn't clear, you can write in comments :) 4 5 Tutorial is loading... 6 7 **Code** 8 9 ``` 10 #include <iostream> 11 #include <string> 12 13 using namespace std; 14 15 int main() 16 { 17 int n; cin >> n; 18 string s; cin >> s; 19 int k_a = 0, k_d = 0; 20 for (int i = 0; i < n; i++) 21 if (s[i] == 'A') k_a++; else k_d++; 22 if (k_a > k_d) cout << "Anton" << endl; 23 if (k_a < k_d) cout << "Danik" << endl; 24 if (k_a == k_d) cout << "Friendship" << endl; 25 return 0; 26 } 27 ``` 28 29 Tutorial is loading... 30 31 **Code** 32 33 ``` 34 #include <iostream> 35 #include <algorithm> 36 37 using namespace std; 38 39 int main() 40 { 41 int k2, k3, k5, k6; 42 cin >> k2 >> k3 >> k5 >> k6; 43 int n256 = min(k2, min(k5, k6)); 44 int n32 = min(k3, k2 - n256); 45 cout << 32 * n32 + 256 * n256 << endl; 46 return 0; 47 } 48 ``` 49 50 Tutorial is loading... 51 52 **Code** 53 54 ``` 55 #include <iostream> 56 57 using namespace std; 58 59 const int max_n = 1000000; 60 61 int n, m, k; 62 int x, s; 63 int a[max_n], b[max_n], c[max_n], d[max_n]; 64 65 inline int max_complete(int money_left) 66 { 67 int l = 0, r = k; 68 while (l < r) 69 { 70 int m = (l + r + 1) / 2; 71 if (d[m] <= money_left) l = m; else r = m-1; 72 } 73 return c[l]; 74 } 75 76 int main() 77 { 78 ios_base::sync_with_stdio(false); 79 cin >> n >> m >> k; 80 cin >> x >> s; 81 a[0] = x; 82 b[0] = 0; 83 c[0] = 0; 84 d[0] = 0; 85 for (int i = 1; i <= m; i++) cin >> a[i]; 86 for (int i = 1; i <= m; i++) cin >> b[i]; 87 for (int i = 1; i <= k; i++) cin >> c[i]; 88 for (int i = 1; i <= k; i++) cin >> d[i]; 89 long long ans = 1LL * n * x; 90 for (int i = 0; i <= m; i++) 91 { 92 int money_left = s - b[i]; 93 if (money_left < 0) continue; 94 ans = min(ans, 1LL * (n - max_complete(money_left)) * a[i]); 95 } 96 cout << ans << endl; 97 return 0; 98 } 99 ``` 100 101 Tutorial is loading... 102 103 **Code** 104 105 ``` 106 #include <cstdio> 107 #include <algorithm> 108 109 using namespace std; 110 111 inline char in_char() 112 { 113 char c = '\0'; 114 while (c <= ' ') 115 c = getchar(); 116 return c; 117 } 118 119 inline int in_int() 120 { 121 int n; 122 scanf("%d", &n); 123 return n; 124 } 125 126 struct figurine 127 { 128 char kind; 129 int x, y; 130 }; 131 132 int n; 133 int x0, y0; 134 figurine nearest[8]; 135 136 inline int dist(int x1, int y1, int x2, int y2) 137 { 138 return max(abs(x1 - x2), abs(y1 - y2)); 139 } 140 141 inline void upd_nearest(figurine& was, const figurine& cur) 142 { 143 if (was.kind == '?' || 144 dist(x0, y0, cur.x, cur.y) < dist(x0, y0, was.x, was.y)) 145 was = cur; 146 } 147 148 inline int get_direction(const figurine& cur) 149 { 150 // vertical 151 if (cur.x == x0 && cur.y < y0) return 0; 152 if (cur.x == x0 && cur.y > y0) return 1; 153 // horizontal 154 if (cur.y == y0 && cur.x < x0) return 2; 155 if (cur.y == y0 && cur.x > x0) return 3; 156 // diagonal 1 157 if ((cur.y - y0) == (cur.x - x0) && cur.x < x0) return 4; 158 if ((cur.y - y0) == (cur.x - x0) && cur.x > x0) return 5; 159 // diagonal 2 160 if ((cur.y - y0) == (x0 - cur.x) && cur.y < y0) return 6; 161 if ((cur.y - y0) == (x0 - cur.x) && cur.y > y0) return 7; 162 // the piece doesn't lie on any of the eight directions 163 return -1; 164 } 165 166 int main() 167 { 168 n = in_int(); 169 x0 = in_int(); y0 = in_int(); 170 for (int i = 0; i < 8; i++) 171 nearest[i].kind = '?'; 172 // read and update nearest 173 for (int i = 0; i < n; i++) 174 { 175 figurine cur; 176 cur.kind = in_char(); cur.x = in_int(); cur.y = in_int(); 177 int dir = get_direction(cur); 178 if (dir >= 0) 179 upd_nearest(nearest[dir], cur); 180 } 181 bool ans = false; 182 // check verticals and horizontals 183 for (int i = 0; i < 4; i++) 184 if (nearest[i].kind == 'R' || nearest[i].kind == 'Q') 185 ans = true; 186 // check diagonals 187 for (int i = 4; i < 8; i++) 188 if (nearest[i].kind == 'B' || nearest[i].kind == 'Q') 189 ans = true; 190 // output 191 puts(ans ? "YES" : "NO"); 192 return 0; 193 } 194 ``` 195 196 Tutorial is loading... 197 198 **Code** 199 200 ``` 201 #include <iostream> 202 #include <vector> 203 #include <algorithm> 204 205 using namespace std; 206 207 int n; 208 vector <int> color; 209 vector < vector <int> > g; 210 vector <char> used; 211 vector <int> comp; 212 int n1; 213 vector < vector <int> > g1; 214 vector <int> dp; 215 int ans = 0; 216 217 void dfs1(int v, int col, int cmp) 218 { 219 if (used[v]) return; 220 if (color[v] != col) return; 221 used[v] = true; 222 comp[v] = cmp; 223 for (int i = 0; i < g[v].size(); i++) 224 { 225 int to = g[v][i]; 226 dfs1(to, col, cmp); 227 } 228 } 229 230 void dfs2(int v, int p = -1) 231 { 232 int mx1 = 0, mx2 = 0; 233 for (int i = 0; i < g1[v].size(); i++) 234 { 235 int to = g1[v][i]; 236 if (to == p) continue; 237 dfs2(to, v); 238 int val = dp[to] + 1; 239 mx2 = max(mx2, val); 240 if (mx1 < mx2) swap(mx1, mx2); 241 } 242 dp[v] = mx1; 243 ans = max(ans, mx1 + mx2); 244 } 245 246 int main() 247 { 248 ios_base::sync_with_stdio(false); 249 cin >> n; 250 color.resize(n); 251 g.resize(n); 252 comp.resize(n); 253 used.assign(n, false); 254 for (int i = 0; i < n; i++) cin >> color[i]; 255 for (int i = 1; i < n; i++) 256 { 257 int a, b; cin >> a >> b; a--, b--; 258 g[a].push_back(b); 259 g[b].push_back(a); 260 } 261 for (int i = 0; i < n; i++) 262 if (!used[i]) 263 dfs1(i, color[i], n1++); 264 g1.resize(n1); 265 dp.resize(n1); 266 for (int i = 0; i < n; i++) 267 for (int j = 0; j < g[i].size(); j++) 268 { 269 int to = g[i][j]; 270 if (comp[i] != comp[to]) 271 g1[comp[i]].push_back(comp[to]); 272 } 273 dfs2(0); 274 cout << (ans + 1) / 2 << endl; 275 return 0; 276 } 277 ``` 278 279 Tutorial is loading... 280 281 **Code** 282 283 ``` 284 #include <iostream> 285 286 using namespace std; 287 288 const int max_n = 300000; 289 290 int n; 291 int b[max_n]; 292 int c[max_n]; 293 int a[max_n]; 294 int d[max_n]; 295 int b1[max_n]; 296 int c1[max_n]; 297 int bits[31][max_n]; 298 int kbit[31]; 299 300 int main() 301 { 302 // input 303 ios_base::sync_with_stdio(false); 304 cin >> n; 305 for (int i = 0; i < n; i++) cin >> b[i]; 306 for (int i = 0; i < n; i++) cin >> c[i]; 307 for (int i = 0; i < n; i++) d[i] = b[i] + c[i]; 308 309 // searching for answer 310 long long sum = 0; 311 for (int i = 0; i < n; i++) sum += d[i]; 312 sum /= (2 * n); 313 314 for (int i = 0; i < n; i++) a[i] = (d[i] - sum) / n; 315 316 // checking the answer 317 for (int i = 0; i < n; i++) 318 if (a[i] < 0) 319 { 320 cout << -1 << endl; 321 return 0; 322 } 323 324 for (int i = 0; i < 31; i++) 325 for (int j = 0; j < n; j++) 326 if ((a[j] & (1LL << i)) == 0) 327 bits[i][j] = 0; 328 else 329 bits[i][j] = 1; 330 for (int i = 0; i < 31; i++) 331 { 332 kbit[i] = 0; 333 for (int j = 0; j < n; j++) 334 kbit[i] += bits[i][j]; 335 } 336 337 for (int i = 0; i < n; i++) b1[i] = 0; 338 for (int i = 0; i < n; i++) c1[i] = 0; 339 340 for (int i = 0; i < 31; i++) 341 for (int j = 0; j < n; j++) 342 { 343 int bbase = bits[i][j] ? kbit[i] : 0; 344 int cbase = bits[i][j] ? n : kbit[i]; 345 b1[j] += bbase << i; 346 c1[j] += cbase << i; 347 } 348 349 for (int i = 0; i < n; i++) 350 if (b1[i] != b[i] || c1[i] != c[i]) 351 { 352 cout << -1 << endl; 353 return 0; 354 } 355 356 // output 357 for (int i = 0; i < n; i++) cout << a[i] << " "; 358 cout << endl; 359 return 0; 360 } 361 ```