[cpp] Optymalizacja

[Kidjamkas]

Od niedawna bawię sie w rozwiązywanie zadan na pl.spoj.pl,

w zasadzie to od jakiś 2 godzin :P

I próbuje rozwiązac pewne zadanie, lecz co ważne kod programu musi wykonać sie w maks. 1 sekunde.

 

I w tym cały problem, mój kod działa dobrze (tak mi się przynajmiej wydaje) lecz jest zbyt wolny - nie mieści się w 1 sekundowym limicie.

 

Treść zadania :

 

Niech n będzie nieujemną liczbą całkowitą. Liczbę n! (czytaj n-silnia) definiuje się następująco. Jeśli n ≤ 1, to n! = 1. Dla n > 1, n! jest równe iloczynowi wszystkich liczb od 1 do n, czyli n! = 1 * 2 * ... * n. Na przykład 4! = 1*2*3*4 = 24.

 

Zadanie

Napisz program, który:

wczyta ze standardowego wejścia nieujemną liczbę całkowitą n,

policzy cyfrę dziesiatek oraz cyfrę jedności w zapisie dziesiętnym liczby n!,

wypisze wynik na standardowe wyjście.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowia D (1≤D≤30), oznaczjąca liczbę przypadków do rozważenia. Opis każdego przypadku składa się z jednej linii, w której znajduje się jedna nieujemna liczba całkowita n (0 ≤ n ≤ 1 000 000 000).

 

Wyjście

Dla każdego przypadku z wejścia. Twój program powinien wypisać w osobnej linii dokładnie dwie cyfry (oddzielone pojedynczą spacją): cyfrę dziesiątek i cyfrę jedności liczby n! zapisanej w systemie dziesiętnym.

 

Przykład

Dla danych wejściowych:

2

1

4

poprawną odpowiedzią jest:

0 1

2 4

 

 

Bez wgłebiania sie w treść zadania - trzeba zoptymalizować funkcje liczącą silnie, lub/i funkcje licząca ilość dziesiątek.

Zrobiłem wszystko co potrafiłem aby ten kod działał jak najszybciej, lecz nadal za wolno :/

Mam nadzieje że ktoś bardziej doświadczony doradzi mi co tu jeszcze można, i jak, zoptymalizować

 

Mój kod :

 

 

 

To jest ukryta treść, proszę

• Zaloguj się
• lub
• Zarejestruj się

 

[No ja]

Podejrzewam, że zbyt długo wykonuje się funkcja silnia. Spróbuj odcinać zawsze dwa ostatnie znaki wyniku (skoro i tak reszta liczby nie jest istotna) i mnożenie wykonywać tylko na tych dwóch ostatnich.

Myślę, że to jest klucz do sukcesu

 

Napisz koniecznie, jak wynik zmian

[jatokor]

W tym zadaniu trzeba coś zauważyć (o ile dobrze pamiętam).

[spider44]

>> tak mi się przynajmiej wydaje

Nie wiem jak to wygląda na windows, na linux wpisujesz sobie

$ time ./twoj_program

i masz podany dokładny czas wykonania.

 

Swoją drogą, człowiek, który pisał to zadanie, najwyraźniej miał problemy z myśleniem. Trochę koliduje mi to:

>> musi wykonać sie w maks. 1 sekunde.

z tym:

>> Napisz program, który:

>> wczyta ze standardowego wejścia nieujemną liczbę całkowitą n,

Najsłabszą częścią tego mechanizmu będzie człowiek, bo trzeba mieć spory refleks, by wpisać liczbę w niecałą sekundę od pojawienia się komunikatu O zatwierdzeniu enterem nie wspomnę.

 

Na twoim miejscu poszukał bym pomocy w kręgu jakiś niskopoziomowych programistów i cały program uczynił jedną wielką wstawką Assemblerową. Czas wykonania powinien znacznie spaść.

[jatokor]

up: te zadania są tak zaprojektowane, że sprawdza je automat, czyli automat podaje dane wszystkie do programu. Ja zmieściłem to w 57 linijkach c++, ale pewnie można mniej, bo nie patrzyłem na zwięzłość kodu.

[Kidjamkas]

zauważyłem zę

liczba mod 10 = liczba jedności

 

pozwoliło mi to usunąc nie optymalną funkcje licząca dziesiątki lecz nadal jest za wolno ;/

 

kurde nie mam już pomysłów ;/

 

@No ja

nie rozumiem o co Ci chodzi

 

nowy optymalniejszy kod (lecz wciąż za wolny) :

 

To jest ukryta treść, proszę

• Zaloguj się
• lub
• Zarejestruj się

[jatokor]

Mogę dać małą podpowiedź, ale to zepsuje pewnie zabawę. Bdw to był kod w C, co raczej niewiele zmienia :P

[Kidjamkas]

Zauważyłem coś takiego :

 

5! = 120

6! = 720

 

wyjśćie :

 

12 0 (czyli 120, tylko ta spacja)

72 0 (czyli 720, tylko ta spacja)

 

ale żeby to wykorzystać musiałbym chyba to konwertować na chary i rozdzielać a to chyba by tylko spowolniło

[jatokor]

Idziesz w dobrą stronę , zauważaj więcej

[4ggr35510n]

Cyfra dziesiątek oraz cyfra jedności liczby n!, dla n > 9 są obie równe zero.

 

Ponieważ:

(X jest pomocniczą liczbą całkowitą, której wartość nas jebie)

10! == 1 * 2 * ... * 9 * 10 == 10 * 2 * 5 * X == 10 * 10 * X == 100 * X

 

Jako, że X jest liczbą Całkowitą. ostatnie dwie cyfry liczby 100*X będą zerami.

 

A więc, jeśli 10! kończy się dwoma zerami, to także każde n! > 10! kończyć się będą dwoma zerami, ponieważ

n! (n>10) = n! * (n-1)! * (n-2)! * ..... * 10!

 

- - - - -

 

W tym momencie pozostaje nam rozpatrzenie pozostałych dziewięciu przypadków (dla n >= 1 <= 9).

Jako, że to dziewięć przypadków, a zależy nam na optymalizacji czasu wykonywania, najlepszym sposobem będzie po prostu stworzenie tabeli z zapisynymi informacjami na temat cyfry jedności i dziesiątek liczby n! z zakresu n 1 do 9.

 

 

- - - - -

Dowód na lemat pogrubioną czcionką jest prosty, ale uważam, że jest to intuicyjne, więc nie warto się rozdrabniać.