Submission #490697

#	Time	Username	Problem	Language	Result	Execution time	Memory
490697		mihh	Kangaroo (CEOI16_kangaroo)	C++17	0 / 100	0 ms	204 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
/*
  tutorial :
  https://codeforces.com/blog/entry/47764
  (ctrl f it)
  N celule 1->n
  cangur celula cs
  sare in alta celula
  se opreste in celula cf
  n-1 sarituri arbritare
  schimba directia in care sare
*/

int n, cf, cs;

const int MOD=1e9+7, N=2e3+1;

int add(int x, int y){
    return (x+y)%MOD;
}
int mul(int x, int y){
    return (1LL*x*y)%MOD;
}

int dp[2][N];

int main(){
    ifstream fin("kangaroo.in");
    ofstream fout("kangaroo.out");
    fin>>n>>cs>>cf;
    fin.close();
    dp[0][0]=1;
    for(int i=1,x=1; i<=n; ++i,x=!x){
        for(int c=1;c<=i;++c){
            // dp[x][c]=0;
            if(!(i==cs or i==cf)){
                dp[x][c]=add(
                    mul(dp[!x][c-1], c-(i>cs)-(i>cf)),
                    mul(dp[!x][c+1], c)
                );
            }else{
                dp[x][c]=add(dp[!x][c-1],dp[!x][c]);
            }
        }
    }
    bool x=(n)%2;
    int ans=dp[x][1];
    fout<<ans;
}

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