Witam. Chciałbym się podpiąć pod powyższy temat. Nad zadaniem MPOWER siedzę już dość długo (chyba wybrałem sobie za trudne zadanie, jak na moje niewielkie póki co doświadczenie) i najlepszy czas jaki uzyskałem dotychczas to 5,79s (język: C++).
Ale po kolei: nie chcę, żeby wyszło, że jestem leniem, który szuka prostej metody na wymasterowanie czasu w zadanku. Nic z tych rzeczy - chcę po prostu zgłębić tajniki algorytmiki, które musiały mi umknąć (różnica 5,79s a 0,00s raczej nie wynika z prostej jakiejś optymalizacji...).
Zacząłem od kombinowania nad algorytmem, który podołałby wyzwaniu. Wyprowadziłem sobie nawet wzorki, żeby mieć podparcie od strony matematycznej.
Wyszedł mi taki kodzik: http://ideone.com/2q10Db - kod trochę niezbyt czytelny dla osoby postronnej, bo jest tu masa własnej arytmetyki. Kod ten nieźle się spocił podczas próby siły: 5,92s.
Dwa dni wytężonej pracy później przeszedłem już chyba przez wszystkie możliwe podejścia do tego zadania... Ale dotarłem trochę okrężną drogą na skraj "hiperoptymalizacji" wcześniejszego kodu. Czas? 5,79s. Załamałem się w tym momencie.
Kodzik: http://ideone.com/u1vFG8
Sporo zmieniłem, choć idea w sumie podobna.
Czytając tutaj wątek ucieszyłem się nawet, zwłaszcza poniższą wypowiedzią:
W sumie to byłem blisko, nawet bardzo blisko A jednocześnie tak daleko.
Doszedłem do wniosku, że najwięcej problemu w programie sprawia funkcja dzieląca liczbę (zapisaną w stringu) przez 2.
void DzielPrzezDwa(string& my)
{
int a, b=0;
for(int i=0; i<my.length(); i++)
{
a = (int)my[i] - 48 + b;
b = 0;
my[i] = (a/2) + 48;
if(a%2==1) b = 10;
}
if(my[0]==48) my.erase(0, 1);
}
A sprawia tyle kłopotu dlatego, że musi być wywoływana niesamowicie dużą ilość razy... a to marnuje zasoby, dużo, bardzo dużo zasobów.
Dlatego też próbowałem bawić się w przekształcenie liczby od razu na system binarny. Wczytywać każdą cyfrę wykładnika osobno; razy 10; wczytaj następną i dodaj ją do liczby, którą masz w pamięci; razy 10; wczytaj następną i dodaj ją do liczby, którą masz w pamięci; i tak aż do napotkania chara odpowiadającego spacji.
Kodzik: http://ideone.com/ZfRM6a
- uwaga! kod strasznie bije po oczach, zwłaszcza, że liczbę w systemie binarnym trzymam tu w stringu.
Ale i tutaj także spotkał mnie zawód. time limit exceeded ;/ Chciałem się pozbyć dzielenia przez dwa, a tymczasem zmieniłem go po prostu na inny problem, tyle że gorszy.
Lista rzeczy, których próbowałem:
- własna arytmetyka - póki co na drodze ewolucji kodu dało mi to najlepszy czas
- konwersja dec -> bin - zbyt czasochłonna
- arytmetyka modularna - w sumie sam doszedłem do podobnego algorytmu, zanim się jeszcze dowiedziałem, że jest coś takiego
- twierdzenie eulera - liczby muszą być względnie pierwsze...
- chińskie twierdzenie o resztach - niestety nie potrafię dojść do tego jak to może mi pomóc.
Ah. Podsumujmy to może trochę, bo już ta wypowiedź urosła do pokaźnych rozmiarów.
Co ja tu robię nie tak? Czy czegoś nie dostrzegam? Czego mi brakuje?