Записи в блоге

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Блог пользователя mainyutin

Видимость участников-призраков в группе

Автор mainyutin, история, 6 месяцев назад, По-русски

Есть ли возможность сделать так, чтобы участники приватной группы с отдельным доменом могли видеть в положении контеста участников-призраков? На данный момент призраки видны в статусе, но не в положении группы.

Вот, что видят участники группы:

А хочется, чтобы видели такую таблицу:

Это возможно сделать, если убрать в адресе "/groupmates/true", но кнопка "Положение" всё равно добавляет эту опцию и показывает результаты группы.

Полный текст и комментарии »

groups, ghosts

-1

mainyutin
6 месяцев назад
1

Codeforces Round 938 (Div. 3) Разбор

Автор mainyutin, история, 7 месяцев назад, По-русски

1955A - Акция на йогурты

Идея: mainyutin, разработка: mainyutin

Разбор

Решение

#include <bits/stdc++.h>
 
using ll = signed long long int;
 
using namespace std;
 
void solve() {
    ll n, a, b;
    cin >> n >> a >> b;
    ll ans = n * a;
    if (b < 2 * a) {
        ans = (n / 2) * b + (n % 2) * a;
    }
    cout << ans << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955B - Прогрессивный квадрат

Идея: ssor96, mainyutin, разработка: Vladosiya

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) (x).begin(), (x).end()
 
using ll = signed long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
 
void solve() {
    int n;
    ll c, d;
    cin >> n >> c >> d;
    vl a(n * n);
    for (int i = 0; i < n * n; ++i) {
        cin >> a[i];
    }
    sort(all(a));
    vl b(n * n);
    b[0] = a[0];
    for (int i = 1; i < n; ++i) {
        b[i] = b[i - 1] + c;
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            b[i * n + j] = b[(i - 1) * n + j] + d;
        }
    }
    sort(all(b));
    cout << (a == b ? "YEs" : "nO") << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955C - Обитатель морских глубин

Идея: ssor96, Vladosiya, разработка: mainyutin

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()

using ll = signed long long int;

void solve() {
    int n;
    ll k;
    cin >> n >> k;
    deque<ll> dq(n);
    for (int i = 0; i < n; ++i) {
        cin >> dq[i];
    }
    while (dq.size() > 1 && k) {
        ll mn = min(dq.front(), dq.back());
        if (k < 2 * mn) {
            dq.front() -= k / 2 + k % 2;
            dq.back() -= k / 2;
            k = 0;
        } else {
            dq.front() -= mn;
            dq.back() -= mn;
            k -= 2 * mn;
        }
        if (dq.front() == 0) {
            dq.pop_front();
        }
        if (dq.back() == 0) {
            dq.pop_back();
        }
    }
    int ans = n - dq.size();
    cout << ans + (dq.size() && dq.front() <= k) << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955D - Неточный поиск подперестановки

Идея: mainyutin, Vladosiya, разработка: mainyutin

Разбор

Решение

#include <bits/stdc++.h>
 
using ll = signed long long int;
 
#define all(x) (x).begin(), (x).end()
 
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
 
using namespace std;
 
void solve() {
    int n, m;
    size_t k;
    cin >> n >> m >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    multiset<int> todo, done, extra;
    for (int j = 0; j < m; ++j) {
        int b;
        cin >> b;
        todo.insert(b);
    }
    for (int j = 0; j < m; ++j) {
        if (todo.find(a[j]) != todo.end()) {
            todo.erase(todo.find(a[j]));
            done.insert(a[j]);
        } else {
            extra.insert(a[j]);
        }
    }
    int ans = (done.size() >= k);
    for (int r = m; r < n; ++r) {
        int old = a[r - m];
        if (extra.find(old) != extra.end()) {
            extra.erase(extra.find(old));
        } else if (done.find(old) != done.end()) {
            done.erase(done.find(old));
            todo.insert(old);
        }
        if (todo.find(a[r]) != todo.end()) {
            todo.erase(todo.find(a[r]));
            done.insert(a[r]);
        } else {
            extra.insert(a[r]);
        }
        ans += (done.size() >= k);
    }
    cout << ans << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955E - Длинное инвертирование

Идея: ssor96, разработка: Vladosiya

Разбор

Решение

#include <bits/stdc++.h>
 
using ll = signed long long int;
 
#define all(x) (x).begin(), (x).end()
 
using pii = std::array<int, 2>;
using pll = std::array<ll, 2>;
using vi = std::vector<int>;
using vl = std::vector<ll>;
 
using namespace std;
 
void solve() {
    int n;
    string s;
    cin >> n >> s;
    for (int k = n; k > 0; --k) {
        vector<char> t(n), end(n + 1);
        for (int i = 0; i < n; ++i) {
            t[i] = s[i] - '0';
        }
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            cnt -= end[i];
            t[i] ^= (cnt & 1);
            if (t[i] == 0) {
                if (i + k <= n) {
                    ++end[i + k];
                    ++cnt;
                    t[i] = 1;
                } else {
                    break;
                }
            }
        }
        if (*min_element(all(t)) == 1) {
            cout << k << '\n';
            return;
        }
    }
    assert(false);
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955F - Нечестная игра

Идея: mainyutin, разработка: mainyutin

Разбор

Решение

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 201;
 
int dp[N][N][N];
 
void precalc() {
    dp[0][0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < N; ++k) {
                int prev = 0;
                if (i) prev = max(prev, dp[i - 1][j][k]);
                if (j) prev = max(prev, dp[i][j - 1][k]);
                if (k) prev = max(prev, dp[i][j][k - 1]);
                dp[i][j][k] = prev;
                int xr = ((i & 1) * 1) ^ ((j & 1) * 2) ^ ((k & 1) * 3);
                if (xr == 0 && (i || j || k)) {
                    ++dp[i][j][k];
                }
            }
        }
    }
}
 
void solve() {
    vector<int> cnt(4);
    for (int i = 0; i < 4; ++i) {
        cin >> cnt[i];
    }
    cout << dp[cnt[0]][cnt[1]][cnt[2]] + cnt[3] / 2 << '\n';
}
 
int main() {
    precalc();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955G - НОД на клетчатом поле

Идея: ZergTricky, разработка: mainyutin

Разбор

Решение

#include <bits/stdc++.h>
 
using ll = signed long long int;
 
#define all(x) (x).begin(), (x).end()
 
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }
    int ans = 1, g = gcd(a[0][0], a[n - 1][m - 1]);
    vector<vector<char> > dp(n, vector<char>(m));
    for (int x = 1; x * x <= g; ++x) {
        if (g % x > 0) {
            continue;
        }
        vector<int> cand = {x, g / x};
        for (int el : cand) {
            for (int i = 0; i < n; ++i) {
                dp[i].assign(m, 0);
            }
            dp[0][0] = 1;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (a[i][j] % el > 0) {
                        continue;
                    }
                    if (!dp[i][j] && i) {
                        dp[i][j] = (dp[i - 1][j] == 1 ? 1 : 0);
                    }
                    if (!dp[i][j] && j) {
                        dp[i][j] = (dp[i][j - 1] == 1 ? 1 : 0);
                    }
                }
            }
            if (dp[n - 1][m - 1]) {
                ans = max(ans, el);
            }
        }
    }
    cout << ans << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955H - Самая безбашенная оборона

Идея: vmanosin7, разработка: mainyutin

Разбор

Решение

#include <bits/stdc++.h>
 
using ll = signed long long int;
 
#define all(x) (x).begin(), (x).end()
 
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
 
using namespace std;
 
const int R = 12, INF = 2e9;
 
bool check(int x, int n) { return (0 <= x && x < n); }
 
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<string> gr(n);
    for (int i = 0; i < n; ++i) {
        cin >> gr[i];
    }
    vector<pii> cord(k);
    vector<int> p(k);
    for (int i = 0; i < k; ++i) {
        cin >> cord[i].first >> cord[i].second >> p[i];
        --cord[i].first;
        --cord[i].second;
    }
    vector<vector<int> > cover(k, vector<int>(R + 1));
    for (int i = 0; i < k; ++i) {
        int x = cord[i].first;
        int y = cord[i].second;
        for (int r = 1; r <= R; ++r) {
            for (int dx = -r; dx <= r; ++dx) {
                for (int dy = -r; dy <= r; ++dy) {
                    int nx = x + dx;
                    int ny = y + dy;
                    if (!check(nx, n) || !check(ny, m)) {
                        continue;
                    }
                    if ((x - nx) * (x - nx) + (y - ny) * (y - ny) <= r * r) {
                        cover[i][r] += (gr[nx][ny] == '#');
                    }
                }
            }
        }
    }
    vector<vector<int> > dp(k + 1, vector<int>(1 << R, -INF));
    dp[0][0] = 0;
    for (int i = 1; i <= k; ++i) {
        for (int mask = 0; mask < (1 << R); ++mask) {
            dp[i][mask] = dp[i - 1][mask];
            for (int r = 1; r <= R; ++r) {
                int j = r - 1;
                if (!(mask & (1 << j))) {
                    continue;
                }
                dp[i][mask] = max(dp[i][mask], dp[i - 1][mask ^ (1 << j)] +
                                                   p[i - 1] * cover[i - 1][r]);
            }
        }
    }
    int ans = 0;
    for (int mask = 0; mask < (1 << R); ++mask) {
        int hp = 0, mlt = 3;
        for (int j = 0; j < R; ++j) {
            if (mask & (1 << j)) {
                hp += mlt;
            }
            mlt *= 3;
        }
        for (int i = 0; i <= k; ++i) {
            ans = max(ans, dp[i][mask] - hp);
        }
    }
    cout << ans << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Полный текст и комментарии »

Разбор задач Codeforces Round 938 (Div. 3)

div 3, round 938

mainyutin
7 месяцев назад
164

Codeforces Round 938 (Div. 3)

Автор mainyutin, история, 7 месяцев назад, По-русски

Привет! В Apr/08/2024 17:35 (Moscow time) начнётся Codeforces Round 938 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Задачи были придуманы и написаны нашей командой: mainyutin, vmanosin7, ssor96 и ZergTricky.

Также большое спасибо:

Vladosiya за помощь с идеями и прекрасную координацию раунда;
FairyWinx, sevlll777 за красное тестирование раунда;
ace5, Nickir, senjougaharin, vladmart за жёлтое тестирование раунда;
natalina за синее тестирование раунда;
bitthal04 за бирюзовое тестирование раунда;
Alequisk, Mohamed_Hesham за зелёное тестирование раунда;
MikeMirzayanov за системы Polygon и Codeforces.

Всем удачи!

UPD: В задаче G была допущена ошибка с валидацией взломов, но сейчас она уже исправлена. Все успешные взломы будут перетестированы. Ошибка не затронула претесты, они не будут изменены.

UPD2: Разбор опубликован.

Полный текст и комментарии »

Анонс Codeforces Round 938 (Div. 3)

div 3, round 938

mainyutin
7 месяцев назад
385

Мусор вместо кириллицы

Автор mainyutin, история, 14 месяцев назад, По-русски

Ранее таких проблем не возникало. Что могло пойти не так и как это исправить?

Существующие пользователи тоже сломались Положение

Полный текст и комментарии »

группы, пользователи, домен

mainyutin
14 месяцев назад
2

Картинки в заголовке

Автор mainyutin, история, 19 месяцев назад, По-русски

Как добавить картинку в заголовок для условий контеста в pdf?

Например, логотип ВУЗа рядом с названием контеста, местом и датой проведения

Полный текст и комментарии »

polygon

mainyutin
19 месяцев назад
5

Пробелы в Polygon

Автор mainyutin, история, 4 года назад, По-русски

Как сделать тесты чувтсвительные к каждому пробелу? Мне нужно, чтобы программы умели работать с лишними пробелами, но я не могу сделать такой тест, потому что Polygon удаляет лишние пробелы

Полный текст и комментарии »

mainyutin
4 года назад
1