Geome try/codechef KAN13F — различия между версиями

Версия 02:39, 19 мая 2022

Codechef/KAN13F

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
uint64_t solve(size_t deg, const std::vector<uint64_t>& seq) {
    uint64_t ans = 0;
    size_t cnt = seq.size();
    auto steps = (cnt - 1 + deg - 2) / (deg - 1);
    std::priority_queue<uint64_t, std::vector<uint64_t>, std::greater<uint64_t>> vals;
    for (auto val : seq) {
        vals.push(val);
    }
 
    size_t curr_deg = deg;
    for (auto rest_steps = steps, rest_cnt = cnt;
            rest_steps > 0 && rest_cnt > 1;
            rest_cnt -= (curr_deg - 1), --rest_steps) {
        curr_deg = 2;
        if (rest_cnt - 2 > (rest_steps - 1) * (deg - 1)) {
            curr_deg = rest_cnt - (rest_steps - 1) * (deg - 1);
        }
 
        uint64_t sum = 0;
        for (size_t i = 0; i < curr_deg && !vals.empty(); ++i) {
            sum += vals.top();
            vals.pop();
        }
        ans += sum;
        vals.push(sum);
    }
 
    return ans;
}
 
int main() {
    size_t tests = 0;
    // std::cin >> tests;
    scanf("%llu", &tests);
    std::vector<uint64_t> answers(tests);
    for (auto& ans : answers) {
        size_t cnt = 0, deg = 0;
        // std::cin >> cnt >> deg;
        scanf("%llu %llu", &cnt, &deg);
        std::vector<uint64_t> seq(cnt);
        for (auto& val : seq) {
            // std::cin >> val;
            scanf("%llu", &val);
        }
        ans = solve(deg, seq);
    }
 
    for (size_t idx = 0; idx < tests; ++idx) {
        // std::cout << "Case " << idx + 1 << ": " << answers[idx] << '\n';
        printf("Case %llu: %llu\n", idx + 1, answers[idx]);
    }
 
    return 0;
}

StasFomin 02:39, 19 мая 2022 (UTC): Вы невнимательны и игнорировали и курс и задания. Решения ожидается только на Python.

Концептуально:

• Win-Win!
• Абсолютно практические задачи с собеседований.
  • LeetCode
  • CodeChef
  • SpojCode
  • Сотни решенных и нерешенных
• Условно поделены на «Dynamic Programming», «Greedy», «Random», «Sorting», «Numbers»
• Нужно быть залогиненным
  • Скрыто из интернета
• Изучайте Решенные практические задачи (Их там 1370)
• Надо решить N задач из 4 разных разделов. На Python.
  • 8 если до 2024-11-01
  • А если нет, просто блокируется доступ к другим квестам (отчисляем).
    • Кроме может ОЧЕНЬ особых случаев.
• Старайтесь сделать максимально читаемое решение, и тут хороший повод потренировать стиль PEP-8, см. Blog:Advanced_Algorithms/Python-решения_—_давайте_потренируемся_их_сделать_питонистей
• За задачи из CodeChef и SpojCoding будут дополнительные бонусные очки (1 балл из настоящей 10 бальной оценки!), их решать сложнее, там не подсказывают тест вызвавший ошибку, там могут быть жесткие TL, надо больше стараться, и да, их надо решать именно на Python (любом, который есть на сервисе, хоть PyPy) оптимизировать вам могут помочь статьи:
  • Blog:Advanced_Algorithms/Python-оптимизация_жадного_алгоритма_из_codechef
  • Blog:Advanced_Algorithms/Python-оптимизация_алгоритма_динамического_программирования_из_codechef
  • Blog:Advanced_Algorithms/Путь_хакера_—_решение_задачи_с_codechef_на_питон._С_машинным_кодом
• Бонусные задачи вполне решаются, если их не боятся → вот из последних решений → Участник:Mishaglik/Solutions/Spoj/FRQPRIME

• Выбирайте задачи из Открытые практические задачи, переходите к редактированию по «Беру…» →

• • помечайте их как {{reserve-task|~~~~~}}
• Зарезервированные задачи убираются в Зарезервированные практические задачи

(Их там 118)

• • Не нужно брать десятки задач на себя сразу, и освобождайте то, что не получается.
• Решенное
  • Ну смотрите, как оформлено в прошлые годы
  • Решение на подстранице вашей личной страницы
    • Вики-ссылка на задачу
    • Python-код в «<source lang="python"></source>»
    • Метка «{{checkme}}», когда решите.

• • • Внизу вставка всего этого по клику →
• Они попадут в Категория:На проверку

(Их там 12)

• Как легче решать Python
  • Загрузка данных
  • Выбирайте более свежий CPython или PyPy.