codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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