Informatyka UJ forum

jagm · Wysłany: Sob 18:27, 11 Mar 2006 Temat postu:

mamy jakąś liczbę, powiedzmy 154031
dzielimy sobie naszą liczbę co 2 cyfry
15,40,31
teraz podstawiamy pod s nasz obecny wynik, czyli 0. Szukamy tegigo x, żeby było <= 15 (bo to są nasze pierwsze 2 cyfry). Czyli w naszym wypadku będzie to 3. Wyliczamy (20*0+3)*3=9 i tak jak w dzieleniu:

15,40,31
-09
----
06,40

Teraz nasz wynik to 3, więc dalej podstawiamy pod s i otrzymujemy 60. Szukamy takiego x, żeby było <= 640 (bo to jest nasza reszta). Wychodzi nam 9: (60+9)*9=621

15,40,31
-09
----
640
- 621
---------
1931

Nasz obecny wynik to 39, więc znów podstawiamy pod s i wychodzi 780. Szukany x to 2, bo (780+2)*2=1564

15,40,31
-09
----
640
- 621
---------
1931
- 1564
----------
367

I reszta nas nie obchodzi, bo już mamy wynik: 392

Krzysiek · Gość

pyt. Czy zerowanie tablicy z wynikami moze wplywac na TLE?
Wkoncu tylko zmieni sie wspolczynnik czy n jesli algorytm jest o zlozonosci liniowej?

Gość · Wysłany: Sob 18:31, 11 Mar 2006 Temat postu:

dzieki za pierwiastek. :)

hansu · Wysłany: Sob 18:38, 11 Mar 2006 Temat postu:

Ehhhh, skrzywili Was tym teoretyzowanie o zlozonoci. Wez pod uwage ze algortym o zlozonsci liniowej i stalej 100000000000000 bedzi prawie zawsze wolniejszy od tego o zlozonosci n^2 i stalej 1 (tzn. dla pewnego duuuzego zbioru "pocztakowych" danych). W tych zadaniach nie chodzi tylko o to zeby algorytm mial taka a nie inna zlozonosc ale takze o to zeby byl WYDAJNY. Zeby nie robil tego co niepotrzebne (vide R3 i rzutowanie na Inty64 zawsze albo tylko w przypadku nie znalezienia i koniecznosci szukania najblizszego, albo R5 i moj TLE przy dwoch roznych zapisach tego samego...). Wielu przypadkach testy sa tak zrobione ze napisanie algorytmu o porzadanej zlozonosci to dopiero polowa sukcesu (bo zaden o zlozonosci wyzszej ne przejdzie) - trzeba go jeszcze porzadnie zoptymalizowac...

chlebek · Wysłany: Sob 19:31, 11 Mar 2006 Temat postu:

Pawel Str. · Wysłany: Sob 19:59, 11 Mar 2006 Temat postu:

exeman · Wysłany: Sob 20:06, 11 Mar 2006 Temat postu:

Wybaczcie mi glupie pytanie, ale jak zrealizowac optyamalne dzielenie ? :>

Madras · Wysłany: Sob 20:41, 11 Mar 2006 Temat postu:

Myślę nad tym od jakichś 3 godzin :>.

Sobek · Wysłany: Sob 21:56, 11 Mar 2006 Temat postu:

A ja to olałem... Wyjechałem na weekend do domu, nie myślę w ogóle o A i teraz gdy zajrzałem do tego topicu wiem, że zrobiłem dobrze :]

Gość · Wysłany: Sob 23:42, 11 Mar 2006 Temat postu:

ile czasu wasze programy licza(i na jakich kompach): /users/sgistudent/2005/kwiatekm/testerka/io/A-in/53_max.in ? To jest 10 duzych testow na mnozenie

Spectro · Wysłany: Sob 23:44, 11 Mar 2006 Temat postu:

Gość · Wysłany: Nie 0:13, 12 Mar 2006 Temat postu:

niezle :-)

hansu, Ty zdaje sie miales reprezentacje cyfrowa - Tobie tez tak szybko liczy?

hansu · Wysłany: Nie 0:14, 12 Mar 2006 Temat postu:

0,82 s

Ja mam reprezentacje na longintach po 4 cyfry w komorce. ALe mi sie optymalizowac nie chcialo za bardzo wiec jest te 0,82 s.

Gość · Wysłany: Nie 0:23, 12 Mar 2006 Temat postu:

czy komu przeszlo na ansistringach?

Gość · Wysłany: Nie 1:14, 12 Mar 2006 Temat postu:

Wiem, ze paru osobom przeszlo na buforze byte'ow.

Ja jestem ciekaw jaki czas w powyzszym tescie maja te osoby, ktore nie robily na long-intach, maja zwykle mnozenie szkolne i im przeszlo?

bo mi blizej do 10 sekund niz do sekundy :D w tym tescie

exeman · Wysłany: Nie 3:31, 12 Mar 2006 Temat postu:

A dla 51_max jakie macie czasy? Cos mi sie wydaje, ze dodawanie mam nieoptyjmalne :/

hansu · Wysłany: Nie 3:51, 12 Mar 2006 Temat postu:

0,21 s

exeman · Wysłany: Nie 3:58, 12 Mar 2006 Temat postu:

Ja mam 0,51, czyli w sumie logicznie dluzej, bo robie na byte'ach nie na longintach. Ale 53_max idzie mi masakrycznie wolno, prawie minute :/ A robie wszystko na mnozeniu binarnym, kurde :/ Macie pomysl, co moze byc zle?

hansu · Wysłany: Nie 3:59, 12 Mar 2006 Temat postu:

Jakim mnozeniu?? Binarnym?? A jak to konkretnie wyglada??

exeman · Wysłany: Nie 4:11, 12 Mar 2006 Temat postu:

No takie co lembas pokazywal z div2, if odd(costam) to costam. Bylo na WDI.

Gość · Wysłany: Nie 5:04, 12 Mar 2006 Temat postu:

jagm · Wysłany: Nie 12:29, 12 Mar 2006 Temat postu:

Moje czasy na virgo:
[link widoczny dla zalogowanych]

Zadanie mi przeszło przez sprawdzaczkę i mam OK

wuodi · Wysłany: Nie 14:30, 12 Mar 2006 Temat postu:

zrobilem to zadanie na ... ansistringach... jak myslicie przejdzie? :>
dziala w miare...
mam pytanie jaki algorytm odejmowania zastosowaliscie?
Ja mam ten od dr Lembasa z cwiczen i nie wiem czy to nie bedzie plagiat jak go sobie uzyje.

Gość · Wysłany: Nie 14:59, 12 Mar 2006 Temat postu:

A jak on dziala? ;-) chyba opuscilem te cwiczenia

wuodi · Wysłany: Nie 15:04, 12 Mar 2006 Temat postu:

Tak wyglada petla:
cyfra:=a-b + cyfra
writeln(cyfra+10 mod 10);
cyfra:=(cyfra-9) div 10;

w zmiennej cyfra jest zapamietywana zarowno cyfra wyniku jak i pozyczka.