#include <iostream>
using namespace std;
int dp[12][10];
int main() {
int n;
cin>>n;
for(int i=1; i<=9; i++)
dp[1][i]=1;
for(int len=2; len<=n; len++){
for(int val=0; val<=9; val++){
if(val<9)dp[len][val]+=dp[len-1][val+1];
if(val>0)dp[len][val]+=dp[len-1][val-1];
dp[len][val]+=dp[len-1][val];
}
}
int ans=0;
for(int i=0; i<=9; i++)
ans+=dp[n][i];
cout<<ans<<endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgZHBbMTJdWzEwXTsKaW50IG1haW4oKSB7CglpbnQgbjsKCWNpbj4+bjsKCWZvcihpbnQgaT0xOyBpPD05OyBpKyspCgkJZHBbMV1baV09MTsKCWZvcihpbnQgbGVuPTI7IGxlbjw9bjsgbGVuKyspewoJCWZvcihpbnQgdmFsPTA7IHZhbDw9OTsgdmFsKyspewoJCQlpZih2YWw8OSlkcFtsZW5dW3ZhbF0rPWRwW2xlbi0xXVt2YWwrMV07CgkJCWlmKHZhbD4wKWRwW2xlbl1bdmFsXSs9ZHBbbGVuLTFdW3ZhbC0xXTsKCQkJZHBbbGVuXVt2YWxdKz1kcFtsZW4tMV1bdmFsXTsKCQkJCgkJCQoJCX0KCX0KCWludCBhbnM9MDsKCWZvcihpbnQgaT0wOyBpPD05OyBpKyspCgkJYW5zKz1kcFtuXVtpXTsKCWNvdXQ8PGFuczw8ZW5kbDsKCXJldHVybiAwOwp9
MQ==
1
language:
C++ (gcc 8.3)
created:
22 days ago
Discover > Sphere Engine API
The brand new service which powers Ideone!
Discover > IDE Widget
Widget for compiling and running the source code in a web browser!
