Sunday 3 June 2012

UVa 10450 World Cup Noise Solution

#include <stdio.h>
unsigned  long long int dp[51][2];
unsigned long long int nSequence(int n,int last)
{

 if(dp[n][last]!=-1)
  return dp[n][last];
 else if(last)
  return dp[n][last] =nSequence(n-1,0);
 else
  return dp[n][last] = nSequence(n-1,1) + nSequence(n-1,0);
}
int main()
{
 int i,c,cc;
 for(i=0;i<51;i++)
  dp[i][0]=dp[i][1]=-1;
 dp[1][0]=2;
 dp[1][1]=1;
 cc = 1;
 scanf("%d",&c);
 while(c--)
 {
  scanf("%d",&i);
  printf("Scenario #%d:\n",cc++);
  printf("%llu\n\n",nSequence(i,0));
 }
 return 0;
}

No comments:

Post a Comment