Разбор задач контеста. Если что будет непонятно, смело пишите в комментариях! :)↵
↵
[tutorial:734A]↵
↵
<spoiler summary="Код">↵
↵
~~~~~↵
#include <iostream>↵
#include <string>↵
↵
using namespace std;↵
↵
int main()↵
{↵
int n; cin >> n;↵
string s; cin >> s;↵
int k_a = 0, k_d = 0;↵
for (int i = 0; i < n; i++)↵
if (s[i] == 'A') k_a++; else k_d++;↵
if (k_a > k_d) cout << "Anton" << endl;↵
if (k_a < k_d) cout << "Danik" << endl;↵
if (k_a == k_d) cout << "Friendship" << endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:734B]↵
↵
<spoiler summary="Код">↵
↵
~~~~~↵
#include <iostream>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
int main()↵
{↵
int k2, k3, k5, k6;↵
cin >> k2 >> k3 >> k5 >> k6;↵
int n256 = min(k2, min(k5, k6));↵
int n32 = min(k3, k2 - n256);↵
cout << 32 * n32 + 256 * n256 << endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:734C]↵
↵
<spoiler summary="Код">↵
↵
~~~~~↵
#include <iostream>↵
↵
using namespace std;↵
↵
const int max_n = 1000000;↵
↵
int n, m, k;↵
int x, s;↵
int a[max_n], b[max_n], c[max_n], d[max_n];↵
↵
inline int max_complete(int money_left)↵
{↵
int l = 0, r = k;↵
while (l < r)↵
{↵
int m = (l + r + 1) / 2;↵
if (d[m] <= money_left) l = m; else r = m-1;↵
}↵
return c[l];↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin >> n >> m >> k;↵
cin >> x >> s;↵
a[0] = x;↵
b[0] = 0;↵
c[0] = 0;↵
d[0] = 0;↵
for (int i = 1; i <= m; i++) cin >> a[i];↵
for (int i = 1; i <= m; i++) cin >> b[i];↵
for (int i = 1; i <= k; i++) cin >> c[i];↵
for (int i = 1; i <= k; i++) cin >> d[i];↵
long long ans = 1LL * n * x;↵
for (int i = 0; i <= m; i++)↵
{↵
int money_left = s - b[i];↵
if (money_left < 0) continue;↵
ans = min(ans, 1LL * (n - max_complete(money_left)) * a[i]);↵
}↵
cout << ans << endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:734D]↵
↵
<spoiler summary="Код">↵
↵
~~~~~↵
#include <cstdio>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
inline char in_char()↵
{↵
char c = '\0';↵
while (c <= ' ')↵
c = getchar();↵
return c;↵
}↵
↵
inline int in_int()↵
{↵
int n;↵
scanf("%d", &n);↵
return n;↵
}↵
↵
struct figurine↵
{↵
char kind;↵
int x, y;↵
};↵
↵
int n;↵
int x0, y0;↵
figurine nearest[8];↵
↵
inline int dist(int x1, int y1, int x2, int y2)↵
{↵
return max(abs(x1 - x2), abs(y1 - y2));↵
}↵
↵
inline void upd_nearest(figurine& was, const figurine& cur)↵
{↵
if (was.kind == '?' ||↵
dist(x0, y0, cur.x, cur.y) < dist(x0, y0, was.x, was.y))↵
was = cur;↵
}↵
↵
inline int get_direction(const figurine& cur)↵
{↵
// vertical↵
if (cur.x == x0 && cur.y < y0) return 0;↵
if (cur.x == x0 && cur.y > y0) return 1;↵
// horizontal↵
if (cur.y == y0 && cur.x < x0) return 2;↵
if (cur.y == y0 && cur.x > x0) return 3;↵
// diagonal 1↵
if ((cur.y - y0) == (cur.x - x0) && cur.x < x0) return 4;↵
if ((cur.y - y0) == (cur.x - x0) && cur.x > x0) return 5;↵
// diagonal 2↵
if ((cur.y - y0) == (x0 - cur.x) && cur.y < y0) return 6;↵
if ((cur.y - y0) == (x0 - cur.x) && cur.y > y0) return 7;↵
// the piece doesn't lie on any of the eight directions↵
return -1;↵
}↵
↵
int main()↵
{↵
n = in_int();↵
x0 = in_int(); y0 = in_int();↵
for (int i = 0; i < 8; i++)↵
nearest[i].kind = '?';↵
// read and update nearest↵
for (int i = 0; i < n; i++)↵
{↵
figurine cur;↵
cur.kind = in_char(); cur.x = in_int(); cur.y = in_int();↵
int dir = get_direction(cur);↵
if (dir >= 0)↵
upd_nearest(nearest[dir], cur);↵
}↵
bool ans = false;↵
// check verticals and horizontals↵
for (int i = 0; i < 4; i++)↵
if (nearest[i].kind == 'R' || nearest[i].kind == 'Q')↵
ans = true;↵
// check diagonals↵
for (int i = 4; i < 8; i++)↵
if (nearest[i].kind == 'B' || nearest[i].kind == 'Q')↵
ans = true;↵
// output↵
puts(ans ? "YES" : "NO");↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:734E]↵
↵
<spoiler summary="Код">↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
int n;↵
vector <int> color;↵
vector < vector <int> > g;↵
vector <char> used;↵
vector <int> comp;↵
int n1;↵
vector < vector <int> > g1;↵
vector <int> dp;↵
int ans = 0;↵
↵
void dfs1(int v, int col, int cmp)↵
{↵
if (used[v]) return;↵
if (color[v] != col) return;↵
used[v] = true;↵
comp[v] = cmp;↵
for (int i = 0; i < g[v].size(); i++)↵
{↵
int to = g[v][i];↵
dfs1(to, col, cmp);↵
}↵
}↵
↵
void dfs2(int v, int p = -1)↵
{↵
int mx1 = 0, mx2 = 0;↵
for (int i = 0; i < g1[v].size(); i++)↵
{↵
int to = g1[v][i];↵
if (to == p) continue;↵
dfs2(to, v);↵
int val = dp[to] + 1;↵
mx2 = max(mx2, val);↵
if (mx1 < mx2) swap(mx1, mx2);↵
}↵
dp[v] = mx1;↵
ans = max(ans, mx1 + mx2);↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin >> n;↵
color.resize(n);↵
g.resize(n);↵
comp.resize(n);↵
used.assign(n, false);↵
for (int i = 0; i < n; i++) cin >> color[i];↵
for (int i = 1; i < n; i++)↵
{↵
int a, b; cin >> a >> b; a--, b--;↵
g[a].push_back(b);↵
g[b].push_back(a);↵
}↵
for (int i = 0; i < n; i++)↵
if (!used[i])↵
dfs1(i, color[i], n1++);↵
g1.resize(n1);↵
dp.resize(n1);↵
for (int i = 0; i < n; i++)↵
for (int j = 0; j < g[i].size(); j++)↵
{↵
int to = g[i][j];↵
if (comp[i] != comp[to])↵
g1[comp[i]].push_back(comp[to]);↵
}↵
dfs2(0);↵
cout << (ans + 1) / 2 << endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:734F]↵
↵
<spoiler summary="Код">↵
↵
~~~~~↵
#include <iostream>↵
↵
using namespace std;↵
↵
const int max_n = 300000;↵
↵
int n;↵
int b[max_n];↵
int c[max_n];↵
int a[max_n];↵
int d[max_n];↵
int b1[max_n];↵
int c1[max_n];↵
int bits[31][max_n];↵
int kbit[31];↵
↵
int main()↵
{↵
// input↵
ios_base::sync_with_stdio(false);↵
cin >> n;↵
for (int i = 0; i < n; i++) cin >> b[i];↵
for (int i = 0; i < n; i++) cin >> c[i];↵
for (int i = 0; i < n; i++) d[i] = b[i] + c[i];↵
↵
// searching for answer↵
long long sum = 0;↵
for (int i = 0; i < n; i++) sum += d[i];↵
sum /= (2 * n);↵
↵
for (int i = 0; i < n; i++) a[i] = (d[i] - sum) / n;↵
↵
// checking the answer↵
for (int i = 0; i < n; i++)↵
if (a[i] < 0)↵
{↵
cout << -1 << endl;↵
return 0;↵
}↵
↵
for (int i = 0; i < 31; i++)↵
for (int j = 0; j < n; j++)↵
if ((a[j] & (1LL << i)) == 0)↵
bits[i][j] = 0;↵
else↵
bits[i][j] = 1;↵
for (int i = 0; i < 31; i++)↵
{↵
kbit[i] = 0;↵
for (int j = 0; j < n; j++)↵
kbit[i] += bits[i][j];↵
}↵
↵
for (int i = 0; i < n; i++) b1[i] = 0;↵
for (int i = 0; i < n; i++) c1[i] = 0;↵
↵
for (int i = 0; i < 31; i++)↵
for (int j = 0; j < n; j++)↵
{↵
int bbase = bits[i][j] ? kbit[i] : 0;↵
int cbase = bits[i][j] ? n : kbit[i];↵
b1[j] += bbase << i;↵
c1[j] += cbase << i;↵
} ↵
↵
for (int i = 0; i < n; i++)↵
if (b1[i] != b[i] || c1[i] != c[i])↵
{↵
cout << -1 << endl;↵
return 0;↵
} ↵
↵
// output↵
for (int i = 0; i < n; i++) cout << a[i] << " ";↵
cout << endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:734A]↵
↵
<spoiler summary="Код">↵
↵
~~~~~↵
#include <iostream>↵
#include <string>↵
↵
using namespace std;↵
↵
int main()↵
{↵
int n; cin >> n;↵
string s; cin >> s;↵
int k_a = 0, k_d = 0;↵
for (int i = 0; i < n; i++)↵
if (s[i] == 'A') k_a++; else k_d++;↵
if (k_a > k_d) cout << "Anton" << endl;↵
if (k_a < k_d) cout << "Danik" << endl;↵
if (k_a == k_d) cout << "Friendship" << endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:734B]↵
↵
<spoiler summary="Код">↵
↵
~~~~~↵
#include <iostream>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
int main()↵
{↵
int k2, k3, k5, k6;↵
cin >> k2 >> k3 >> k5 >> k6;↵
int n256 = min(k2, min(k5, k6));↵
int n32 = min(k3, k2 - n256);↵
cout << 32 * n32 + 256 * n256 << endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:734C]↵
↵
<spoiler summary="Код">↵
↵
~~~~~↵
#include <iostream>↵
↵
using namespace std;↵
↵
const int max_n = 1000000;↵
↵
int n, m, k;↵
int x, s;↵
int a[max_n], b[max_n], c[max_n], d[max_n];↵
↵
inline int max_complete(int money_left)↵
{↵
int l = 0, r = k;↵
while (l < r)↵
{↵
int m = (l + r + 1) / 2;↵
if (d[m] <= money_left) l = m; else r = m-1;↵
}↵
return c[l];↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin >> n >> m >> k;↵
cin >> x >> s;↵
a[0] = x;↵
b[0] = 0;↵
c[0] = 0;↵
d[0] = 0;↵
for (int i = 1; i <= m; i++) cin >> a[i];↵
for (int i = 1; i <= m; i++) cin >> b[i];↵
for (int i = 1; i <= k; i++) cin >> c[i];↵
for (int i = 1; i <= k; i++) cin >> d[i];↵
long long ans = 1LL * n * x;↵
for (int i = 0; i <= m; i++)↵
{↵
int money_left = s - b[i];↵
if (money_left < 0) continue;↵
ans = min(ans, 1LL * (n - max_complete(money_left)) * a[i]);↵
}↵
cout << ans << endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:734D]↵
↵
<spoiler summary="Код">↵
↵
~~~~~↵
#include <cstdio>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
inline char in_char()↵
{↵
char c = '\0';↵
while (c <= ' ')↵
c = getchar();↵
return c;↵
}↵
↵
inline int in_int()↵
{↵
int n;↵
scanf("%d", &n);↵
return n;↵
}↵
↵
struct figurine↵
{↵
char kind;↵
int x, y;↵
};↵
↵
int n;↵
int x0, y0;↵
figurine nearest[8];↵
↵
inline int dist(int x1, int y1, int x2, int y2)↵
{↵
return max(abs(x1 - x2), abs(y1 - y2));↵
}↵
↵
inline void upd_nearest(figurine& was, const figurine& cur)↵
{↵
if (was.kind == '?' ||↵
dist(x0, y0, cur.x, cur.y) < dist(x0, y0, was.x, was.y))↵
was = cur;↵
}↵
↵
inline int get_direction(const figurine& cur)↵
{↵
// vertical↵
if (cur.x == x0 && cur.y < y0) return 0;↵
if (cur.x == x0 && cur.y > y0) return 1;↵
// horizontal↵
if (cur.y == y0 && cur.x < x0) return 2;↵
if (cur.y == y0 && cur.x > x0) return 3;↵
// diagonal 1↵
if ((cur.y - y0) == (cur.x - x0) && cur.x < x0) return 4;↵
if ((cur.y - y0) == (cur.x - x0) && cur.x > x0) return 5;↵
// diagonal 2↵
if ((cur.y - y0) == (x0 - cur.x) && cur.y < y0) return 6;↵
if ((cur.y - y0) == (x0 - cur.x) && cur.y > y0) return 7;↵
// the piece doesn't lie on any of the eight directions↵
return -1;↵
}↵
↵
int main()↵
{↵
n = in_int();↵
x0 = in_int(); y0 = in_int();↵
for (int i = 0; i < 8; i++)↵
nearest[i].kind = '?';↵
// read and update nearest↵
for (int i = 0; i < n; i++)↵
{↵
figurine cur;↵
cur.kind = in_char(); cur.x = in_int(); cur.y = in_int();↵
int dir = get_direction(cur);↵
if (dir >= 0)↵
upd_nearest(nearest[dir], cur);↵
}↵
bool ans = false;↵
// check verticals and horizontals↵
for (int i = 0; i < 4; i++)↵
if (nearest[i].kind == 'R' || nearest[i].kind == 'Q')↵
ans = true;↵
// check diagonals↵
for (int i = 4; i < 8; i++)↵
if (nearest[i].kind == 'B' || nearest[i].kind == 'Q')↵
ans = true;↵
// output↵
puts(ans ? "YES" : "NO");↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:734E]↵
↵
<spoiler summary="Код">↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
int n;↵
vector <int> color;↵
vector < vector <int> > g;↵
vector <char> used;↵
vector <int> comp;↵
int n1;↵
vector < vector <int> > g1;↵
vector <int> dp;↵
int ans = 0;↵
↵
void dfs1(int v, int col, int cmp)↵
{↵
if (used[v]) return;↵
if (color[v] != col) return;↵
used[v] = true;↵
comp[v] = cmp;↵
for (int i = 0; i < g[v].size(); i++)↵
{↵
int to = g[v][i];↵
dfs1(to, col, cmp);↵
}↵
}↵
↵
void dfs2(int v, int p = -1)↵
{↵
int mx1 = 0, mx2 = 0;↵
for (int i = 0; i < g1[v].size(); i++)↵
{↵
int to = g1[v][i];↵
if (to == p) continue;↵
dfs2(to, v);↵
int val = dp[to] + 1;↵
mx2 = max(mx2, val);↵
if (mx1 < mx2) swap(mx1, mx2);↵
}↵
dp[v] = mx1;↵
ans = max(ans, mx1 + mx2);↵
}↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin >> n;↵
color.resize(n);↵
g.resize(n);↵
comp.resize(n);↵
used.assign(n, false);↵
for (int i = 0; i < n; i++) cin >> color[i];↵
for (int i = 1; i < n; i++)↵
{↵
int a, b; cin >> a >> b; a--, b--;↵
g[a].push_back(b);↵
g[b].push_back(a);↵
}↵
for (int i = 0; i < n; i++)↵
if (!used[i])↵
dfs1(i, color[i], n1++);↵
g1.resize(n1);↵
dp.resize(n1);↵
for (int i = 0; i < n; i++)↵
for (int j = 0; j < g[i].size(); j++)↵
{↵
int to = g[i][j];↵
if (comp[i] != comp[to])↵
g1[comp[i]].push_back(comp[to]);↵
}↵
dfs2(0);↵
cout << (ans + 1) / 2 << endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:734F]↵
↵
<spoiler summary="Код">↵
↵
~~~~~↵
#include <iostream>↵
↵
using namespace std;↵
↵
const int max_n = 300000;↵
↵
int n;↵
int b[max_n];↵
int c[max_n];↵
int a[max_n];↵
int d[max_n];↵
int b1[max_n];↵
int c1[max_n];↵
int bits[31][max_n];↵
int kbit[31];↵
↵
int main()↵
{↵
// input↵
ios_base::sync_with_stdio(false);↵
cin >> n;↵
for (int i = 0; i < n; i++) cin >> b[i];↵
for (int i = 0; i < n; i++) cin >> c[i];↵
for (int i = 0; i < n; i++) d[i] = b[i] + c[i];↵
↵
// searching for answer↵
long long sum = 0;↵
for (int i = 0; i < n; i++) sum += d[i];↵
sum /= (2 * n);↵
↵
for (int i = 0; i < n; i++) a[i] = (d[i] - sum) / n;↵
↵
// checking the answer↵
for (int i = 0; i < n; i++)↵
if (a[i] < 0)↵
{↵
cout << -1 << endl;↵
return 0;↵
}↵
↵
for (int i = 0; i < 31; i++)↵
for (int j = 0; j < n; j++)↵
if ((a[j] & (1LL << i)) == 0)↵
bits[i][j] = 0;↵
else↵
bits[i][j] = 1;↵
for (int i = 0; i < 31; i++)↵
{↵
kbit[i] = 0;↵
for (int j = 0; j < n; j++)↵
kbit[i] += bits[i][j];↵
}↵
↵
for (int i = 0; i < n; i++) b1[i] = 0;↵
for (int i = 0; i < n; i++) c1[i] = 0;↵
↵
for (int i = 0; i < 31; i++)↵
for (int j = 0; j < n; j++)↵
{↵
int bbase = bits[i][j] ? kbit[i] : 0;↵
int cbase = bits[i][j] ? n : kbit[i];↵
b1[j] += bbase << i;↵
c1[j] += cbase << i;↵
} ↵
↵
for (int i = 0; i < n; i++)↵
if (b1[i] != b[i] || c1[i] != c[i])↵
{↵
cout << -1 << endl;↵
return 0;↵
} ↵
↵
// output↵
for (int i = 0; i < n; i++) cout << a[i] << " ";↵
cout << endl;↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
