Zadanie ze SPOJ

Zadanie ze spoja . Jest ktos w stanie podpowiedziec jak przyspieszyc ten program, albo jak rozwiazac to zadanie. Proboje juz kilku algorytmow i za kazdym razem przekraczam limit czasu (nawet w C++) przy tescie 8. Mimo ze wszytkie testy sa poprawne nadal nie wiem czy moj algorytm jest dobry. Czy musze tutaj zastosowac inne podejscie?

using System;
using System.Text;

namespace CSharpPlayground
{
    public class Program
    {
        static void Main()
        {
            string[] txt = Console.ReadLine().Split(' ');
            string numberN = txt[0];
            string numberK = txt[1];

            StringBuilder numberSB = new StringBuilder(numberN);
            int k = Int32.Parse(numberK);
            ulong n = ulong.Parse(numberN);


            ulong tmpN = n;   // Tutaj ustawiam
            tmpN = tmpN / 10; // cyfre jednosci
            tmpN *= 10; // na zero

            if (numberN.Length < k) // jesli liczba jest mniejsza niz liczba cyfr to ustawiam na najmniejsza z mozliwych
            {
                numberSB.Clear();
                for (int i = 0; i < k; i++)
                    numberSB.Append(5);

                Console.WriteLine(numberSB);
            }
            else if(CountFives(n + 1) >= k)
            {
                Console.WriteLine(n + 1);
            }
            else // szukam prawidlowej odpowiedzi iterujac co 5
            {
                ulong counter = 0;
                while (true)
                {

                    if (tmpN > n && CountFives(tmpN) >= k)
                    {
                        break;
                    }
                    else
                    {
                        tmpN += 5;
                        counter++;
                    }
                }

                Console.WriteLine(tmpN);
            }            
        }

        private static int CountFives(ulong n)
        {
            int counter = 0;
            ulong number = n;
            while(number != 0)
            {
                if (number % 10 == 5)
                    counter++;

                number = number / 10;
            }

            return counter;
        }
    }
}

No dobra, zaklepałeś tu bruta na pałe z tego co widzę i teraz się dziwisz że działa wolno? o_O Zastanów się, czy serio myślisz ze testowanie wszystkich liczb po kolei to dobre rozwiazanie?
Ja bym to zrobił zupełnie inaczej:

• zaczynamy od liczby n+1
• wymieniamy cyfry od końca na 5, ale jeśli dana cyfra była większa od 5 to musimy dodać 1 do wyższej cyfry (więc np. 16 zamieniamy na 25)
• robimy tak póki brakuje nam 5 (najlepiej policzyć ile ich mamy na początku a potem pamiętać ile nam dochodzi co krok)

Dzieki @Shalom. Teraz ten algorytm dziala na wszystkie mozliwe sposoby. Poza tym jest niesamowicie szybki dla dowolnie duzych n i k xD

Szkoda że teraz wygląda dramatycznie :D Wiesz ze dało się to zrobić trochę sprytniej za pomocą, uwaga, uwaga, dodawania! Nie tak trudno policzyć jak zmienia się k-tą cyfrę z x na 5 ;)
W praktyce wystarczy:

• pobrać tą cyfrę -> digit = number/(10**k) % 10
• policzyć missing = (5-digit) % 10
• dodać do początkowej liczby missing * (10**k)
• voila, zamieniliśmy k-tą cyfrę na 5, z zachowaniem przeniesienia!

Dzięki temu odpada cała ta zabawa w operacjami na liczbach w stringach i implementowanie dodawania pisemnego...

@Shalom no dobra Power() poprawiony, ale i tak sa zle wyniki. Poza tym wydaje mi sie ze to zadanie wymaga wiekszej liczby przypadkow niz tylko jeden.

using System;

namespace CSharpPlayground
{
    public class Program
    {
        static void Main()
        {
            string[] txt = Console.ReadLine().Split(' ');
            string numberN = txt[0];
            string numberK = txt[1];


            int k = Int32.Parse(numberK);
            ulong n = ulong.Parse(numberN);

            ulong digit;
            ulong missing;
            int len = CountDigits(n);

            for(int i = 0; i < len; i++)
            {
                digit = (n / Power(i)) % 10;
                missing = (5 - digit) % 10;
                n += missing * (Power(i));

                if (CountFivesOnUlong(n) >= k)
                    break;
            }

            Console.WriteLine(n);
        }


        private static int CountFivesOnUlong(ulong n)
        {
            int counter = 0;
            ulong number = n;
            while (number != 0)
            {
                if (number % 10 == 5)
                    counter++;

                number = number / 10;
            }

            return counter;
        }

        private static int CountDigits(ulong n)
        {
            int counter = 0;
            ulong number = n;
            while (number != 0)
            {
                counter++;
                number = number / 10;
            }

            return counter;
        }

        private static ulong Power(int k)
        {
            ulong tmp = 1;
            for (int i = 0; i < k; i++)
                tmp *= 10;

            return tmp;
        }
    }
}

@Shalom Bez przesady. Wystarczyloby powiedziec w ktorym miejscu robie blad a nie cala wine zwalac na jezyk xD bo w tej formie nie zadziala w zadnym jezyku

def main():
    n, k = tuple(map(int, raw_input("").split(" ")))
    i = 0
    while count_fives(n) < k:
        multiplier = (10 ** i)
        digit = n / multiplier % 10
        missing = (5 - digit) % 10
        if digit > 5:
            tmp_n = n + (10 - digit) * multiplier
            if count_fives(tmp_n) >= k:
                n = tmp_n
                break
        n += missing * multiplier
        i += 1
    print(n)


def count_fives(n):
    return len(filter(lambda x: x == '5', str(n)))


main()

To chyba powinno działać. Jest tam jeden corner-case niestety i nie widzę zeby dało się go prosto rozwiązać, bo może tak być że samo "wyzerowanie" kolejnej cyfry spowoduje propagacje która da tyle 5 ile chcemy i wtedy warto zostawić tą cyfrę na 0 a nie ustawiać na 5 ;]
Widać to zresztą w tym twoim przykładzie, kiedy mamy
495495995 5
Bo robimy po kolei:
495495995
495496055
495496555
i teraz gdybyśmy po prostu zamienili 6 na 5 propagacja tworzy nam nową 5:
495505555
a da sie lepiej bo zamiana tej 6 najpierw na 0 daje nam już
495500555
i jest to rozwiązanie lepsze, więc w przypadku kiedy będzie propagacja (czyli aktualna cyfra jest większa od 5) trzeba sprawdzić czy sama propagacja już nie spowoduje spełnienia warunku k