Разбор Codeforces Round #379 (Div. 2)
Разница между ru1 и ru2, 1 символ(ов) изменены
Разбор задач контеста. Если что будет непонятно, смело пишите в комментариях! :)↵

[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>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский gepardo 2016-11-15 22:43:56 1 (опубликовано)
en1 Английский gepardo 2016-11-15 22:30:23 7170 Initial revision for English translation
ru1 Русский gepardo 2016-11-15 22:25:05 7145 Первая редакция (сохранено в черновиках)