Informatyka UJ forum

hansu · Wysłany: Nie 19:15, 05 Mar 2006 Temat postu:

Ja przepisalem moj dotychczasowy program na longinty. Przedtem mialem tablice shortintow i w kazdym trzymalem 1 cyfre. Teraz w kazym longincie trzymam 4 cyfry. Czyli mam jakby zapisz liczby w systemie pozycyjnym o podstawie 10000. 4 cyfry dlatego zeby mnozenie bylo zawsze wykonalne bez ryzyka przpelnienia. I powiem Wam ze to bardzo dobrze dziala. Obiektywne testy wykonane przez niezalezna instytucje (thx Insane ;)). Wykazaly ze moj program przy najbardziej pesymistycznych danych do potegowania przyspieszyl z ponad 8,5 s do.... 0,7 s. Czyli warto bylo. Teraz przede mna dzielenie i pierwiastkowanie, bedzie troche trudniej na tych longintach ale mam juz jakas tam powiedzmy koncepcje. Dam znac jak mi sie cos urodzi... :D

oinopion · Wysłany: Pon 1:17, 06 Mar 2006 Temat postu:

Pascal to *&^@&#!^$%#$^*!)!}{{!@#. HKD!
Hans, myślę, że czas zrobic porządne posiedzenie TBS i zebrać się w te całe nasze 4 osoby i przegadać to, ew. zaprogramować grupowo. To nie jest dobre zadanie. Czai się w nim zło skomplikowania i zagmatwania. Musimy znaleź proste i szybkie rozwiązanie, takie, które by pozwoliło na szybkie operowanie na np. bitach. Wspominałeś o systemie z podstawą 256... tam np. można zrobic szybko << i >> oraz &1.

hansu · Wysłany: Pon 1:29, 06 Mar 2006 Temat postu:

To jest bez sensu bo zeby zapisac z postaci 256-kowej musialbys te liczby dzielic... Czyli od najwiekszej kobyly (czytaj: dzielenia) i tak sie nie uchronisz, bo bedziesz je musial zaprogramowac na systemie dziesietnym lub jakims pochodnym (100,1000,...). Ja w kazdym razie zostaje przy systemie 10000 bo jest niewyobrazalnie szybki a i dzielenie w nim nie wydaje sie takie straszne. Tak mysle, bo jeszcze go nie zaczalem pisac :P

A co do spotkania TBS... Hmmm, ja zawsze jestem chetny, tylko mam takie pobozne zyczenie coby nie bylo tak hmmmm intensywne jak to piatkowe... ;) (Insane na sam dzwiek slowa marchewka zielenieje ze strachu :D) Zwalszcza jesli mamy o algorytmach dyskutowac. :P

oinopion · Wysłany: Pon 1:35, 06 Mar 2006 Temat postu:

Proponuję po analizie. Chyba, że Wy coś tam macie.... To w takim wypadku, wieczorem w II; tam jest miejsce i swiatło. Kompy dostepne do 22.

oinopion · Wysłany: Pon 19:41, 06 Mar 2006 Temat postu:

Tak w ogóle, to jaka jest koncepcja dzielenia całkowitego? Jakoś nie potrafię opanowć dzielenia, które nie jest zero-symetryczne.
Dodam, że chodzi mi głównie o sprawy związane ze znakami.

hansu · Wysłany: Pon 21:30, 06 Mar 2006 Temat postu:

Szybki przyklad:

62 div 10 = 6 r 2
62 div -10 = -6 r 2
-62 div 10 = -7 r 8
-62 div -10 = 7 r 8

Ogolnie rzecz biorac: wykonujemy dzielenie na wartosciach bezwzglednych. Jezeli dzielna jest ujemna zwiekszamy wynik o jeden a reszte ustawiamy na dzielnik - reszta. Dopiero potem ustalamy znak ilorazu (tak jak w mnozeniu - dwa minusy daja plus, plus i minus to minus);

UWAGA!!!!! Operator div w pascalu dziala inaczej!!!! Ale my to mamy zrobic tak....

Pawel Str. · Wysłany: Pon 22:59, 06 Mar 2006 Temat postu:

hansu · Wysłany: Pon 23:57, 06 Mar 2006 Temat postu:

Oczywiscie masz racje. Szczerze mowiac jeszcze o tym nie myslalem, jestem jeszcze na etapie kodowania dzialan na wartosciach bezwzglednych. Ale dzieki za wskazowke, na pewno sie nie zmarnuje ;)

Pawel Str. · Wysłany: Wto 0:12, 07 Mar 2006 Temat postu:

Swoją drogą dzielenie też implementujesz w sytemie o podstawie 10000? Nadal wydaje mi się, że do dzielenia jest to nieoptymalne. Chyba, że robisz to jakoś inaczej niż ja, czyli nie system przesunięć i odjęć (przesuń w lewo dzielnik tak, aby był tej samej długości co dzielna (uzupełniając zerami),odejmuj jak długo się da, przesuń o jedno 0 w prawo i na wyjściu też zakończ daną liczbę). Wychodzi mi, że koszt dzielenia to długość zapisu liczby * maksymalna wartość cyfry. W dziesiątkowym jest to log10 x / 9, w 10000 jest to log10000 x/ 9999, co jest znacznie większe.

hansu · Wysłany: Wto 0:53, 07 Mar 2006 Temat postu:

Tez robie w 10000.
Na poczatku robie sobie 3 nowe liczby: dzielnik razy 10, razy 100 i razy 1000.

Mam tak to zaimplementowane ze liczba nie musi byc na poczatku w tablicy, tylko trzymam jej poczatek i koniec w osobnych polach rekordu. W ten sposob to taki slupkowe spisywanie z dzielnej w dol robie dekrementujac jednego longinta (nie musze nic przesuwac).
Tak w ogole to wszystkie operacje robie na dzielnej in citu. Na poczatku ustawiam ja jako jednosegmentowa i zwiekszam jej rozmiar az bedzie wieksza od dzielnika. Wtedy odejmuje od niej kolejno dzielnik1000, dzielnik100 itd. tyle razy ile sie da. Kazdy wynik zapisuje w osobnej zmiennej (c1000, c100 itd). Potem do odpowiedniego pola ilorazu wstawiam tylko 1000*c1000 + 100*c100 itd...

Wiem ze to wyglada na zakrecone ale dziala (dlatego ze algorytm dzielenia pisemnego jest sluszny dla systemu pozycyjnego o kazdej podstawie). I dziala naprawde szybko - pesymistyczny wariant, czyli 2000 dziewiatek przez 1 idzie mniej niz 1 sekunde.

Pawel Str. · Wysłany: Wto 2:00, 07 Mar 2006 Temat postu:

Jesteś pewien, że to jest poprawne? Nie widzę, gdzie uwzględniasz przeniesienie przy dzieleniu.

OK, odpowiadam sam sobie. Masz rację.

pstryczek · Wysłany: Wto 22:40, 07 Mar 2006 Temat postu:

czy komus zaliczylo zwykla reprezentacje (tablica cyfr)?

jagm · Wysłany: Wto 22:54, 07 Mar 2006 Temat postu:

Gość · Wysłany: Wto 22:56, 07 Mar 2006 Temat postu:

hansu · Wysłany: Śro 2:19, 08 Mar 2006 Temat postu:

Uffffff, przepchnalem to wreszcie! Juz myslalem, ze sie nie uda... Niestety, zaliczylem 5 bombek, co niestety wiaze sie ze strata 5 balsamow na rzecz Insane'a ale coz..... On tez juz pare bombek ma :P Wiec szykuje sie impreza :D

Garsc rad, ktorymi moge sie podzielic po dluuugiej i zmudnej walce z tym parszywym zadaniem:

1. Jest wredne, parszywe, ochydne, oblesne i sukinsynskie. Pisze sie je MINIMUM 3 dni, bez testow i debugowania. Straszna kobyla.

2. Przede wszystkim przetestujcie swoje programy na serwerze virgo. Tam jest taki sam Free Pascal jakiego uzywa sprawdzaczka. Jest on troche inny niz ten ktorego my mamy (my mamy 2.0.2 a tam jest 1.9.4 - w weekend maja to zmienic) i to moze generowac powazne bledy (jak w moim przypadku - ale o tym za chwile). Adres serwera to virgo.ii.uj.edu.pl, login i haslo jak na elfa. Nie mozna tego robic na elfie bo tam nie ma fpc :/

2. Jezeli uzywacie zmiennych dynamicznych to zawsze i wszedzie INICJALIZUJCIE je na pocztaku. Ja przez to mialem 5 * RTE bo nie inicjalizowalem sobie jednej zmiennej i pod windows wszystko bylo ok ale na virgo raz ona byla 0 a raz 137 milionow. Dodam ze to byl modyfikator do indeksu tablicy i jak sie probowalem odwolac do komorki 137 milionow to mi wypluwal RE 216. Takze zawsze i wszedzie po new(zmienna) nadawajcie jej wartosci poczatkowe...

3. To juz sie tyczy scislej tego zadania. Otoz chodzi o zwracanie jako wynik -0 co oczywiscie jest bledem. Jesli wydaje sie wam ze sie przed tym zabezpieczyliscie to sprobujcie sobie podzielic np 7 przez -10 i zobaczcie co wyjdzie. Ja tez bylem baaaardzo zdziwiony.

Disclaimer: Tak naprawde osoba ktora wylapala w moim kodzie bledy 2. i 3. byl Mateo, za co jestem mu niewymownie wdzieczny, jak rowniez za wszystkie rady i testy, ktorymi mnie wspomogl. Bez niego pewnie jeszcze dlugo bym sie meczyl z tym paskudztwem. WIELKIE DZIEKI i morze piwa dla Ciebie :D

AMD · Wysłany: Śro 2:59, 08 Mar 2006 Temat postu:

Widzę hansu że ostro pracowałeś nad tą 7.

oinopion · Wysłany: Śro 3:18, 08 Mar 2006 Temat postu:

Jak zwykle... Pogratulować, kolejny raz: wiwat TBS (szkoda, że mi tak mało wiwatów przypada...).

Gość · Wysłany: Śro 20:50, 08 Mar 2006 Temat postu:

Ja poiersole moje dodawanie i odejmowanie w czasie liniowym jest za wolne czy to jest mozliwe? <rotfl>

hansu · Wysłany: Śro 21:08, 08 Mar 2006 Temat postu:

Jest mozliwe. Moze sie zdarzyc ze dla jakiegos parszywego zestawu danych sie zapetla.... Ale moze byc tez tak, ze Twoj kod jest skrajnie nieoptymalny i naprawde mimo ze poprawnie liczy to sie w czasie nie miesci... Ale cos mi sie w to nie chce wierzyc skoro timelimity do tego zadania sa ustawione na 5* wzorcowka a ona dziala na shortintach....

smas · Wysłany: Śro 21:31, 08 Mar 2006 Temat postu:

wzorcówka działa na bajtach

hansu · Wysłany: Śro 21:42, 08 Mar 2006 Temat postu:

Bajty czy shortinty, jeden diabel. Wazne ze trzyma kazda cyfre osobno a nie np. po 4 w komorce tak jak ja .

Robson · Wysłany: Śro 21:47, 08 Mar 2006 Temat postu:

Mam pytanie. Jak wczytujecie dane? Czy jako jeden duzy string (AnsiString)? Czy raczej znak po znaku.
Bo ja robie tak:
1. wczytuje znak po znaku do tablicy dopoki na wejsciu są znaki z zakresu 0-9 lub minus.
2. Biorę ta tablicę i idąc od konca dopisuję to do mojej tablicy longintów od początku (podstawe systemu mam 1000000)
3. Wykonuję na nich działania...

przykład wczytję 12345678901234567890.
w tablicy longintów ląduje
t[0] = 567890
t[1] = 901234
t[2] = 345678
t[3] = 12

czyli mam zapisaną liczbę 1000000^0*567890 + 1000000^1*901234 + 100000^2*345678 + 1000000^3*12

czy mozliwe że przez kroki 1-2 dostaję TLE ? (bo dwa razy chodzę po tablicy znaków...?)?

hansu · Wysłany: Śro 23:40, 08 Mar 2006 Temat postu:

Ja to robie tak ze wczytuje i na biezaco dodaje do tablicy kolejne komorki a potem robie switcha. Wiec de facto to chyba to samo.... Chociaz, nie, bo Ty dwa razy przelatujesz cala tablice charow i jeszcze longinty, a ja tylko 2 razy longinty (1,5 raza wlasciwie).

Jesli zas chodzi o Twoje TLE to wydaje mi sie ze przyczyna moga byc Inty64. Jak juz parokrotnie pisalem one sa BEZCZELNIE wolne. A Ty przy mozeniu za kazdym razem robisz pewnie rzutowanie na Inty64. A mnozenie to najdluzsza z tych operacji (tzn. maxymalny test mnozenia ma najwieksze timelimity bo po prostu dziala najdluzej). Proponje uzyc Mateowej sprawdzaczki i tam jest w glownych testach m.in. test na maksymalne mnozenie...

Ziom · Gość

omg:/ Ja sie juz cieszylem ze mi A1 poszlo bo 3h nie moglem znalesc o jednego readln za duzo a teraz TLE na A :P

Swoja droga czas <2s na a64 1800mhz przy mnozeniu maxow to znosny jeszcze? bo mam na bytach i slabo mi sie widzi przepisywanie tego ;/

Natomiast co mozna inteligentnego zrobic z sqrt jak wywala TLE? bo dla MAXa to liczy z minute chyba :P Zna ktos jakis fast algorytmik na Sqrt? ;]