SPOJ - ACODE - AlphaCode

23 April 2013   185 words   ~1 min
#SPOJ #Dynamic Programming #Sport Programming

Table of Contents

Problem Description - http://www.spoj.com/problems/ACODE/
\\ Approach :
\\

  1. Initialize an Array of Size N with 0 and element 0 as 1\\
  2. Loop through all the elements\\
  3. If it is a valid single digit number, Copy the previous element's value to the current element (DP[i] = DP[i-1])\\
  4. If it is a valid two digit number, Add the previous to previous element's value to the current element (DP[i] += DP[i-2])\\

\\ In one line : DP[i] = DP[i-1] {if valid single digit number} + DP[i-2] {if current and previous elements make a valid two digit number}
\\ Solution:\\

 1# include <cstdio>
 2# include <cstring>
 3char Input[5001] = "";
 4unsigned long long DP[5001];
 5int main()
 6{
 7 freopen ("Input.txt", "r", stdin);
 8 freopen ("Scratch.txt", "w", stdout);
 9 scanf ("%s", Input);
10 while (strcmp(Input, "0"))
11 {
12  int Len = strlen (Input), Index = 1;
13  memset (DP, 0, sizeof DP);
14  DP[0] = 1;
15  while (Index  9) DP[Index] += DP[Index-2 < 0?0:Index-2];
16   //printf ("%d\t%llu\n",Index, DP[Index]);
17   Index++;
18  }
19  //printf ("%llu\t%s\n", DP[Len-1], Input);
20  printf ("%llu\n", DP[Len-1]);
21  scanf ("%s", Input);
22 }
23}
← prev next →