#include <stdio.h>
int memo[100000] = {0};
rec(int n)
{
if(n<=2) return memo[n] = 1;
if(memo[n]!=0) return memo[n];
return memo[n] = (rec(n-1)+rec(n-2))%10009;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", rec(n%10009));
}
#include<stdio.h>
int rec(int n,int r)
{
if(r==0 || n==r) return 1;
return rec(n-1,r-1)+rec(n-1,r);
}
int main()
{
int n,r;
scanf("%d %d", &n, &r);
printf("%d", rec(n,r));
}
#include<stdio.h>
int memo[1000][1000] = {0};
int rec(int n,int r)
{
if(r==0 || n==r) return 1;
if(memo[n][r]!=0) return memo[n][r];
return memo[n][r] = rec(n-1,r-1)+rec(n-1,r);
}
int main()
{
int n,r;
scanf("%d %d", &n, &r);
printf("%d", rec(n,r));
}
#include<stdio.h>
int memo[10000]= {0};
int rec(int n)
{
if(n<=3) return n;
if(memo[n]!=0) return memo[n];
return memo[n] = rec(n-1)+rec(n-2);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", rec(n));
}
#include <stdio.h>
int map[9][9]={},cnt=0,part=0;
int i,j;
void dfs(int x, int y, int color)
{
if(map[x][y]==color)
{
map[x][y]=-1;
part++;
dfs(x,y+1,color);
dfs(x,y-1,color);
dfs(x+1,y,color);
dfs(x-1,y,color);
}
}
int main()
{
for(i = 1; i<=7; i++)
{
for(j = 1; j<=7 ;j++)
{
scanf("%d",&map[i][j]);
}
}
for(i = 1; i<=7; i++)
{
for(j = 1; j<=7 ;j++)
{
if(map[i][j]!=-1)
{
part = 0;
dfs(i,j,map[i][j]);
if(part>=3)
{
cnt++;
}
}
}
}
printf("%d\n", cnt);
return 0;
}
#include<stdio.h>
int map[27][27]={},home[100]={};terr=0,cnt=0,temp,n;
void sort()
{
int i,j;
for(i=1;i<cnt;i++)
{
for(j=1;j<cnt;j++)
{
if(home[j]>home[j+1])
{
temp = home[j];
home[j] = home[j+1];
home[j+1] = temp;
}
}
}
}
void dfs(int x,int y)
{
if(map[x][y]==1)
{
map[x][y]=-1;
terr++;
dfs(x,y+1);
dfs(x,y-1);
dfs(x+1,y);
dfs(x-1,y);
}
}
int main()
{
int i,j;
scanf("%d", &n);
for(i=1;i<n+1;i++)
{
for(j=1;j<n+1;j++)
{
scanf("%1d", &map[i][j]);
}
}
for(i=1;i<n+1;i++)
{
for(j=1;j<n+1;j++)
{
if(map[i][j]==1)
{
terr=0;
dfs(i,j);
cnt++;
home[cnt]=terr;
}
}
}
printf("%d\n", cnt);
sort();
for(i=1;i<=cnt;i++)
{
printf("%d\n", home[i]);
}
}
#include<stdio.h>
char map[102][102]={};
int main()
{
int w,h,i,j;
scanf("%d %d", &w, &h);
for(i=1;i<h+1;i++)
{
for(j=1;j<w+1;j++)
{
scanf(" %c", &map[i][j]);
}
}
for(i=1;i<h+1;i++)
{
for(j=1;j<w+1;j++)
{
printf(" %c", map[i][j]);
}
printf("\n");
}
}