Слабые тесты / weak tests

Правка ru1, от Fenekiro, 2026-09-17 23:41:51

В данной задаче https://codeforces.me/group/BI1D9pvdKX/contest/716883/problem/E тесты покрывают не все случаи. Так, например, следующий код сработает корректно для всех тестов данного задания:

#include <iostream>
#include <vector>

int main() {
    int n;

    std::cin >> n;

    std::vector<int> y(n, 0);

    for (int i = 0; i < n; ++i) {
        std::cin >> y[i];
    }

    int energy_spent = 0;
    int i = 0;

    while (i != n - 1) {
        if (i < n - 2) {
            int single_jumps_energy = std::abs(y[i] - y[i + 1]) + std::abs(y[i + 1] - y[i + 2]);
            int double_jump_energy = 3 * std::abs(y[i] - y[i + 2]);

            if (single_jumps_energy < double_jump_energy) {
                energy_spent += single_jumps_energy;
            } else {
                energy_spent += double_jump_energy;
            }

            i += 2;
        } else {
            energy_spent += std::abs(y[i] - y[i + 1]);
            i += 1;
        }
    }

    std::cout << energy_spent;
}

Однако на тесте 4 0 1 100 2 повалится (по коду будет 198, а по факту до лжно быть 4), поскольку алгоритм некорректен в общем случае (алгоритм перебирает не все оптимальные пути).

Теги problem

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский Fenekiro 2026-09-17 23:41:51 1261 Первая редакция (опубликовано)