Submission #1293915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293915		saidshikhov	Kangaroo (CEOI16_kangaroo)	C++20	0 / 100	0 ms	332 KiB

kangaroo

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MOD = 1000000007;

int main() {
    int N, cs, cf;
    cin >> N >> cs >> cf;
    
    // dp[l][r] = количество способов посетить все клетки от l до r
    // l - левая граница посещенного непрерывного отрезка
    // r - правая граница посещенного непрерывного отрезка
    vector<vector<int>> dp(N + 2, vector<int>(N + 2, 0));
    
    // Инициализация: начинаем с начальной клетки
    // Мы можем пойти как влево, так и вправо
    if (cs == cf) {
        // Если начальная и конечная совпадают - только если N=1, но по условию N>=2 и cs != cf
        cout << 0 << endl;
        return 0;
    }
    
    // Начинаем с отрезка [cs, cs]
    dp[cs][cs] = 1;
    
    // Будем расширять отрезок
    for (int len = 1; len <= N; len++) {
        for (int l = 1; l <= N; l++) {
            int r = l + len - 1;
            if (r > N) continue;
            
            if (dp[l][r] == 0) continue;
            
            // Расширяем влево
            if (l > 1) {
                // Проверяем условие смены направления
                // Если последний прыжок был направо, то следующий должен быть налево
                // Это выполняется автоматически при расширении влево
                dp[l - 1][r] = (dp[l - 1][r] + dp[l][r]) % MOD;
            }
            
            // Расширяем вправо
            if (r < N) {
                // Проверяем условие смены направления  
                // Если последний прыжок был налево, то следующий должен быть направо
                // Это выполняется автоматически при расширении вправо
                dp[l][r + 1] = (dp[l][r + 1] + dp[l][r]) % MOD;
            }
        }
    }
    
    // Ответ - количество способов, когда весь отрезок [1, N] посещен
    // и последняя клетка - cf
    // Но нам нужно убедиться, что маршрут заканчивается в cf
    
    // Альтернативный подход: ДП с учетом направления
    vector<vector<int>> dp_left(N + 2, vector<int>(N + 2, 0));
    vector<vector<int>> dp_right(N + 2, vector<int>(N + 2, 0));
    
    // Инициализация
    if (cs < cf) {
        dp_right[cs][cs] = 1; // начинаем, идя направо
    } else {
        dp_left[cs][cs] = 1; // начинаем, идя налево
    }
    
    for (int len = 1; len <= N; len++) {
        for (int l = 1; l <= N; l++) {
            for (int r = l; r <= N; r++) {
                if (r - l + 1 != len) continue;
                
                // Расширяем влево из состояния "направо"
                if (l > 1 && dp_right[l][r] > 0) {
                    dp_left[l - 1][r] = (dp_left[l - 1][r] + dp_right[l][r]) % MOD;
                }
                
                // Расширяем вправо из состояния "налево"  
                if (r < N && dp_left[l][r] > 0) {
                    dp_right[l][r + 1] = (dp_right[l][r + 1] + dp_left[l][r]) % MOD;
                }
                
                // Также расширяем влево из состояния "налево" (меняем направление)
                if (l > 1 && dp_left[l][r] > 0) {
                    dp_right[l - 1][r] = (dp_right[l - 1][r] + dp_left[l][r]) % MOD;
                }
                
                // Расширяем вправо из состояния "направо" (меняем направление)
                if (r < N && dp_right[l][r] > 0) {
                    dp_left[l][r + 1] = (dp_left[l][r + 1] + dp_right[l][r]) % MOD;
                }
            }
        }
    }
    
    // Ответ: сумма способов закончить в cf
    int answer = 0;
    for (int l = 1; l <= cf; l++) {
        for (int r = cf; r <= N; r++) {
            if (l <= cf && cf <= r) {
                answer = (answer + dp_left[l][r]) % MOD;
                answer = (answer + dp_right[l][r]) % MOD;
            }
        }
    }
    
    cout << answer << endl;
    
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 30
• Subtask 3: 0 / 15
• Subtask 4: 0 / 49