Calculation of the distance to the next space station

Question

I've made a solution for this problem:

Task:

Write a program for calculation of the distance to the next space station.

Algorithm:

First base is located at the distance equal to SMK from the beginning of the path (Sirius in our case). The next station is located at the distance of F(SMK) from the first. Third station — at the distance of F(F(SMK)) and so on. Here \$F\$ — is the Top Secret Mars Function (TSMF). Its value is the sum of the cubes of digits its argument in decimal notation (for example \$F(12) = 1^3 + 2^3 > = 9\$). So if the distance from the (\$I − 1\$)-th to \$I\$-th stations is \$X\$, then the distance between \$I\$-th and (\$I + 1\$)-th stations is \$F(X)\$. Your cruiser is located between (\$N − 1\$)-th and \$N\$-th space stations at the distance of \$L\$ from (\$N − 1\$)-th station. Taking \$N\$, \$K\$ (Secret Mars Key) and \$L\$ as input your program should output the distance \$M\$ between your cruiser and \$N\$-th station. Oh, by the way! The value of SMK is always divisible by 3.

Input:

Number \$T\$ (\$2 ≤ T ≤ 33333\$) is placed in the first line of input — it is the number of tests for your program. It followed by the next \$T\$ lines.

Each of these \$T\$ lines contains 3 integer numbers:

\$N\$ (\$2 ≤ N ≤ 33333\$), \$K\$ (\$3 ≤ K ≤ 33333\$) and \$L\$ (\$L ≥ 1\$)

Output:

\$T\$ lines. \$I\$-th line contains the calculated value of \$M\$ for \$I\$-th test case.

It has to run in less than one second and take up less than 16 megabytes of memory.

Sample:

http://img33.imageshack.us/img33/502/81219587.jpg

Here is the compiled code:

static void Main()
{         
    int T = Convert.ToInt32(Console.ReadLine());
    for (int k = 0; k < T; k++)
    {
        string[] split = (Console.ReadLine()).Split(new Char[] { ' ' });
        int N = Convert.ToInt32(split[0]);
        double K = 0;
        string Kst = split[1];
        double POST = 0;

        for (int i = 0; i < N - 1; i++)
        {
            for (int j = 0; j <= Kst.Length - 1; j++)
            {
                int Kindex = int.Parse(Convert.ToString(Kst[j]));
                K = K + Kindex*Kindex*Kindex;
            }
           POST = K; 
            Kst = Convert.ToString(K);
            K = 0;
        }
        Console.WriteLine(POST - Convert.ToDouble(split[2]));
    }
}

But this code doesn't go through the time limit of 1.0 second. How can I improve the speed of this solution?

Answer 1

Here are a few tips:

• Instead of getting each character, creating a new string from it, and then parse the string into a number, just get the character and convert the character code into the number.

• Alternatively, parse the whole number once, then get the digits numerically using modulo.

• There are only ten digits, so you can easily set up an array of precalculated cube values.

• K is a double, but there are no floating point operations here. Use an int, or a long if needed.

Example:

int T = Convert.ToInt32(Console.ReadLine());
int[] cube = { 0, 1, 4, 9, 16, 25, 36, 49, 64, 81 };
for (int k = 0; k < T; k++) {
  string[] split = Console.ReadLine().Split(' ');
  int N = Convert.ToInt32(split[0]);
  int Kst = Convert.ToInt32(split[1]);
  int K = 0;
  for (int i = 0; i < N - 1; i++) {
    K = 0;
    while (Kst > 0) {
      K += cube[Kst % 10];
      Kst /= 10;
    }
    Kst = K;
  }
  Console.WriteLine(K - Convert.ToInt32(split[2]));
}

Answer 2

static void Main()
{         
int T = Convert.ToInt32(Console.ReadLine());
for (int k = 0; k < T; k++)

That is a confusing of k, because K is used for something quite different. I suggest using t (of course for non contest code, you should have longer names.

{
    string[] split = (Console.ReadLine()).Split(new Char[] { ' ' });
    int N = Convert.ToInt32(split[0]);
    double K = 0;
    string Kst = split[1];
    double POST = 0;

Its odd that you decided to capitalize all the letters in this

    for (int i = 0; i < N - 1; i++)
    {
        for (int j = 0; j <= Kst.Length - 1; j++)
        {
            int Kindex = int.Parse(Convert.ToString(Kst[j]));

That's not a index, don't call it Kindex. As Guffa noted is not a great idea to convert between strings and integers all the time like that. It'll be a speed killer. Instead, I suggest using modulo and division to extract the digits

            K = K + Kindex*Kindex*Kindex;
        }
       POST = K; 
        Kst = Convert.ToString(K);
        K = 0;

Do this at the beginning of the loop, that makes more sense

    }
    Console.WriteLine(POST - Convert.ToDouble(split[2]));

I'd have done this conversion back at the beginning with the other conversions. }

}

As for your actual algorithm, I don't want to just give you the answer, because the point is to figure out. But, I can give you a hint. Print out the sequences of F(K), F(F(K)), etc for various K and see what happens.