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

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

Codechef/MCO16204

#include <bits/stdc++.h>
 
int main() {
    size_t cnt = 0;
    std::cin >> cnt;
    std::vector<int64_t> lst(cnt), rst(cnt);
    for (auto it = lst.rbegin(); it != lst.rend(); ++it) {
        std::cin >> *it;
    }
    for (auto it = rst.rbegin(); it != rst.rend(); ++it) {
        std::cin >> *it;
    }
 
    auto dim = cnt + 1;
    std::vector<int64_t> dp_ans(dim * dim);
    dp_ans[0 * dim + 0] = 0;
    for (size_t i = 1; i < dim; ++i) {
        dp_ans[i * dim + 0] = lst[i - 1] - dp_ans[(i - 1) * dim + 0];
        dp_ans[0 * dim + i] = rst[i - 1] - dp_ans[0 * dim + (i - 1)];
    }
 
    for (size_t l = 1; l < dim; ++l) {
        for (size_t r = 1; r < dim; ++r) {
            dp_ans[l * dim + r] = std::max(lst[l - 1] - dp_ans[(l - 1) * dim + r],
                                           rst[r - 1] - dp_ans[l * dim + (r - 1)]);
        }
    }
 
    std::cout << dp_ans.back() << '\n';
 
    return 0;
}
 
/*
import numpy as np
 
if __name__ == '__main__':
    cnt = int(input())
    lst = np.fromiter(map(int, input().split()), dtype=np.int64)[::-1]
    rst = np.fromiter(map(int, input().split()), dtype=np.int64)[::-1]
    dim = cnt + 1
    dp_ans = np.zeros(dim * dim, dtype=np.int64)
    dp_ans[0 * dim + 0] = 0
    for l in range(1, dim):
        dp_ans[l * dim + 0] = lst[l - 1] - dp_ans[(l - 1) * dim + 0]
    for r in range(1, dim):
        dp_ans[0 * dim + r] = rst[r - 1] - dp_ans[0 * dim + (r - 1)]
    for l in range(1, dim):
        for r in range(1, dim):
            dp_ans[l * dim + r] = max(lst[l - 1] - dp_ans[(l - 1) * dim + r], \
                                      rst[r - 1] - dp_ans[l * dim + (r - 1)])
    print(dp_ans[cnt * dim + cnt])
*/

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.