ダンスカーペット
806 ワード
プッシュ
F[A]=F[B]+F[C];
F[B]=F[A]+F[C];
F[C]=F[A]+F[B];
F[A]=F[B]+F[C];
F[B]=F[A]+F[C];
F[C]=F[A]+F[B];
#include<stdio.h>
int f[1050][5];
void solve()
{
int i,j;
f[1][1]=0;
f[1][2]=1;
f[1][3]=1;
for(i=2;i<=1002;i++)
for(j=1;j<=3;j++)
{
if(j==3)
f[i][j]=(f[i-1][1]%10000+f[i-1][2]%10000)%10000;
else if(j==2)
f[i][j]=(f[i-1][1]%10000+f[i-1][3]%10000)%10000;
else
f[i][j]=(f[i-1][2]%10000+f[i-1][3]%10000)%10000;
}
}
int main()
{
int n,i,j;
solve();
while(scanf("%d",&n),n)
{
printf("%d
",f[n][1]);
}
}