http://pl.spoj.com/problems/AL_05_01/89 - zadanie
http://ideone.com/XELnHv143 - kod
Potrzebuje jakis testow dla ktorego program daje bledne odpowiedzi. Dobrze by bylo zeby podany byl by prawidlowy out.
Mar '17
Nov '21http://ideone.com/GwJFIp139
Poprawilem typ przyjmowanego argumentu we funkcji.
Out: 1.
Nadal WA ;/
Dostałem na PW poniższy list i pozwoliłem sobie, zacytować go w całości:
Cześć Ci Narbej,
Właśnie rozwiązałem zadanie z czarodziejskim lusterkiem i jestem w lekkim szoku.
Wpierw
użyłem stringa, żeby wrzucić do niego liczbę w postaci dwójkowej i
później od końca obliczałem nowo powstałą liczbę i się udało.
Później
wpadłem na pomysł, aby zrezygnować ze stringa i od razu w rekurencji
wyliczać nową liczbę. Też ten sposób zaliczył, ale z opóźnieniem od
starszego o około 8%. Kilka razy próbowałem zmienić co nieco, ale z
coraz gorszym skutkiem.
Patrzyłem na oba rozwiązania i byłem w 100%
pewny, że rezygnacja ze stringa jest szybszym rozwiązaniem i prawdę
mówiąc się zbulwersowałem.
Nie ufałem sędziemu, więc sprawdziłem na
kompie szybkość obu przypadków przy wariancie pesymistycznym. Okazało
się, że drugie rozwiązanie jest o około 30% szybsze.
W sumie to jest sztuka dla sztuki, ale chciałbym wiedzieć czemu tak się stało.Wybacz, że do Ciebie piszę z tym kłopotem, ale nie chciałem uderzać z
tym kłopotem na forum, żeby innym nie popsuć przyjemności z
rozwiązywania. Jeśli nie będzie miał chęci odpowiadać to za jakiś czas
zgłoszę się z problemem na forum.Dziękuję za jakąkolwiek odpowiedź.
Pozdrawiam
Konrad
Trochę Ci ułatwię. Jesteś już na forum 
Tu rekurencja nie jest potrzebna, a jej użycie [zamiast iteracji] spowalnia program. Mój negatywny stosunek do zmiennych globalnych jest stały i nie zmienny.Ale u Ciebie, może wszystkie zmienne, zaczniesz przekazywać jako zmienne globalne? W pamięci komputera liczby już są zapisane i pamiętane w formie bitowej, więc można i warto z teko skorzystać. ...Milczenie jest złotem, a czytanie?
Na temat tego zadania są dwa wątki: http://discuss.spoj.com/search?q=czarodziejskie%20lusterko%20category%3A52
Ale jak już się dokleiłeś do któregoś, to przynajmniej ten kontynuowany należało dokładnie przeczytać. Są w nim już dużo wcześniej, podane przez @mariusz193, dwa testy, z których twój program jednego nie przechodzi. Testy w większości zadań to niezbędne minimum, ale często nie gwarantują AC - należy dokładnie [i despacito] czytać treść zadania, specyfikacje wejścia i wyciągać wnioski [myśleć].
PS
Jako autor zadania, powinienem podkręcić “lekko” limit czasu, aby takie rozwiązania na stringach dostawały “z automatu” TLE, ale co z tymi wszystkimi biednymi rozwiązaczami w javie, pythonie, haskelu[!? 
] i wszystkich innych wolniejszych językach? No i po prostu nie chce mi się, trudno jeżeli początkujący koderzy [rozwiązywacze] są tacy jak każdy widzi, to przecież to wina koderów a nie autorów zadań, nieprawdaż?. Może kiedyś się nauczą?
Moim zdaniem jeżeli zadanie ma prawidłową złożoność i daje poprawne odpowiedzi powinno być akceptowane. Chyba, że w zamyśle autor chce żeby użytkownik użył takiej a nie innej struktury (albo języka).
Po pierwsze zanim sam zaczniesz coś komentować to sprawdź źródło. Widziałem, że są 2 takie wątki, a w rzeczywistości 1 - dlaczego? Sprawdź sam swój link.
Po drugie - gdy dokleiłem się do tego to czytałem wcześniejsze testy i wychodziło, że jest dobrze (widocznie źle sprawdziłem ten drugi test), teraz dostałem od Mariusza jeszcze jeden test, który pozwolił mi na znalezienie błędu.
Zadanie - AC.
Nie mam więcej pytań.
to usuń link do kodu, bo zbyt bliski prawidłowego rozwiązania (choć nie popieram metody działania na stringach, bo można szybciej i bardziej elegancko)
Z punktu widzenia osoby rozwiazujacej zadanie jedynym kryterium oceny poprawnosci rozwiazania jest AC. Estetyka kodu, styl rozwiazania a nawet jego wywalanie sie dla danych innych niz w testach autora (tak zwane slabe testy) nie moga byc omowione na forum ani nigdzie indziej.
Temu uwazam ze wstawiony kod powinien z automatu dostac TLE jako rozwiazanie algorytmicznie bezmyslne - to zwykly brut i tyle.
Ale to i tak nic w porownaniu z tym co przechodzi obecnie w zadaniu dotyczacym generowania liczb pierwszych.
tyle, że brut w Czarodziejskie lusterko jest praktycznie nieodróżnialny w kryterium czasowym od poprawnego rozwiązania - większość czasu to operacje wejścia/wyjścia
W zadaniu na liczby pierwsze można by wymusić poprawne rozwiązanie, ale oczywiście kosztem ograniczenia rozwiązań jedynie do C/C++
Że nie są, nie znaczy że nie mogą. A szkoda. Kiedyś, często, przy podpowiadaniu, przy okazji komentowałem też błędy “stylistyczne” w kodzie pytającego, ale że do tanga trzeba dwojga, więc zaprzestałem. Szkoda mi mojego czasu i zdrowia, bo czasami zamiast wdzięczności było tylko obrażanie się, za taką [przecież konstruktywną, a nie złośliwą?] krytykę. Więc chyba masz rację, że większość osób [na pewno nie wszystkie] interesuje tylko uzyskanie AC i: “nie mam więcej pytań”
PS
W tym zadaniu 2x long to o jeden bit za mało. Należy koniecznie użyć unsigned.
linux/python
>>> bin(4294967296)
'0b100000000000000000000000000000000'
>>> bin(4294967297)
'0b100000000000000000000000000000001'
>>> bin(18446744073709551615)
'0b1111111111111111111111111111111111111111111111111111111111111111'
>>> bin(18446744073709551616)
'0b10000000000000000000000000000000000000000000000000000000000000000'
>>>
Po zmianie wyjścia na double program przechodzi powyższy test. Jeśli chodzi o wejście to 2^64-1 powinno się mieścić w zakresie unsigned long long int. Niestety pokazuje WA.
No i się mieści
Do tego zadania wystarczy w zupełności ten typ, a stosowanie typu zmiennoprzecinkowego [float, double] jest niekonieczne, a nawet jest to błąd. Także string jest tu zupełnie zbędny.
Może przyda Ci się ten link, --> C++ kruczki i sztuczki, sorry, został “nieco” zaśmiecony, więc więcej sztuczek pewnie tam już nie będzie.
To:
if(k1==18446744073709551615) cout << "18446744073709551616" << endl;
oczywiście jest błędne, zobacz na mój wcześniejszy post.
Funkcja pow, jest typu double i działa na takiego typu liczbach, co może powodować i powoduje błędy zaokrągleń - pisałem, że typy zmiennoprzecinkowe nie są tu dobre.
Napisz więc swoją własną funkcję pow2(), typu unsigned long long lub stablicuj wszystkie [tylko 64] wartości potęgi 2
[0] = 1
[1] = 2
[2] = 4
…
[31] = 214748364
…
[64] = ?
Mam problem w zadaniu czarodziejskie lusterko z przekroczeniem limitu czasu na SPOJ-u, 1.próbowałem zrobić to zadanie na dwa sposoby przez konwersje z dec na bin, liczbe bin zapisałem do stringa i potem zrobiłem konwersje na dec. 2. wszystkie konwersje zrobilem na liczbach zapisanych w tablicach, czyli liczbe dec skonwertowana na bin zapisałem w tablicy , potem zrobiłem reverse i z tablicy zrobiłem konwersje na dec. Wyniki sie zgadzają ale limit czasu przekroczony :(. Ma ktoś pomysł jak można z tym sie uporać?
Zrobiłem podobnie jak w twoim punkcie 2, patrząc po czasie chyba nie najlepsze rozwiązanie ale nie było TLE.
Spróbuj bez reverse, jak dalej nie pójdzie to można jeszcze coś pokombinować żeby nie liczyć potęg dwójki (tylko trzeba się sporo napisać xD).
Popełniłem taki kod:
–>Tutaj był kod <–
Ktoś ma jakiś pomysł dlaczego wywala mi “Przekroczono limit czasu” na ideone pokazuje 0s.
Edit: usunięcie kodu 
Dziękuje @mariusz193 Poprawiłem, zadziałało, zaliczyło zadanie.
Cześć,
Podjąłem się zrobienia tego zadania w C#, jednak poległem na optymalizacji kodu, więc postanowiłem spróbować swoich sił z tym zadaniem w C++. Niestety błędna odpowiedź i nie potrafię znaleźć błędu. Problemem była funkcja pow(), jednak ograniczyłem ją do wykonywania potęg max 2^63, gdyż nie potrzeba więcej, przynajmniej tak napisano w poleceniu.
Kod: https://ideone.com/nWsB3k7
Out mamy identyczny.
Hmm… patrząc na kod na szybko nie wiem, co może być przyczyną błędu.
Może użycie funkcji pow, która zwraca double i w związku z tym może być kłopotliwa?
Nie wiem czy błąd leżał w tym co napisałeś, ale przerobiłem kod w ten sposób, że dałem wszystkie potęgi 2 w tablice i AC.
Twoja odpowiedź sugeruje, że dokładnie w rachunku epsilonów leżał błąd. Więc sprawdziłem zastępując funkcją ull pow(ull, ull) skopiowaną z neta.
AC w 0.5 sekundy.
Nie wiem, jak stoisz z doświadczeniem, ale na przyszłość: sprawdzaj deklaracje funkcji, których używasz, a zwłaszcza funkcji matematycznych w cmath. One nie są bezpieczne numerycznie bo nigdy nie miały być. Poza tym, o ile to tylko możliwe, nigdy nie używaj liczb zmiennoprzecinkowych.
Poniżej to, co wysyłam w każdym przypadku, gdy błąd jest związany z infinitezymalnymi:
A w Twoim przpadku: https://en.cppreference.com/w/cpp/numeric/math/pow3 lub http://www.cplusplus.com/reference/cmath/pow/2 (w tym temacie obojętnie które)
Ogólnie jestem samoukiem, kiedyś miałem w szkole podstawy C++, ale to tyle co nic. Coś tam wiem, ale jestem trochę oporny w czytaniu o języku i to jest chyba mój największy problem 
. Dziękuję za to, że poświęciłeś swój czas i mi to przedstawiłeś
Cześć,
Próbowałem już długi czas szukać błędu w moim programie, ale już się poddaję.
| Topic | Category | Replies | Views | Activity |
|---|---|---|---|---|
| MBPROB01 - History version in plaintext pl.spoj.com | Zbiór zadań | 6 | 175 | Jul '24 |
| FR_20_02 - Poszukiwacze skarbów - Błąd w testach? | Zbiór zadań | 1 | 96 | Apr 2 |
| PP0504B - StringMerge - w języku C | Zbiór zadań | 5 | 205 | Jun '24 |
| TFRACAL - Kalkulator ułamków | Zbiór zadań | 2 | 143 | Feb 1 |
| TOPSORTL - Porządek leksykograficzny w grafie | Zbiór zadań | 3 | 147 | Jul '24 |
