Tutorial for the tasks of the contest. If something isn't clear, you can write in comments :)
Tutorial is loading...
Code
#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;
}
Tutorial is loading...
Code
#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;
}
Tutorial is loading...
Code
#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;
}
Tutorial is loading...
Code
#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;
}
Tutorial is loading...
Code
#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;
}
Tutorial is loading...
Code
#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;
}