Informatyka UJ forum

trywialna

Głupie zadanie, przy czyszczeniu wyszłam poza zakres tablicy i ANS:/ dzieki Spectro :wink:

Spectro

Ponieważ to nie pierwszy przypadek problemu z zerowaniem tablicy, to polecam funkcję:

Rogal

Spectro: Jak piszesz takie rzeczy, to napisałbyś to już dokładniej :D

Dla całkowitych liczb większych niż 1-bajtowe ustawianie memsetem działa tylko w przypadku wartości 0 i -1. Dzieje się tak, ponieważ liczby są ustawiane nie po całości tylko po 1 bajcie, i jeślibyśmy np. chcieli ustawić liczbę int (4 bajty) przez memset na 1, to dostaniemy coś takiego

Spectro

Cupek

- 1 godzina na znalezienie bledu ze sie wczytuje do &x a nie x
- 2 godziny na znalezienie bledu ze short inta sie nie czyta przez %d
- jeszcze troche na obczajenie bledu przy zmianie wiersza w petli
- OK na Atenie - bezcenny :D

Sa rzeczy ktorych nie mozna kupic, za wszystkie inne zaplacisz bezsensowna praca. :?

liffe

Spectro

@liffe:
dla 5 ścian:
P = p2 * p6 + p3 * (p5 + p6)

Po prostu wyliczamy prawdopodobieństwa w kolejnym rzucie dla dokładnie n ścian, n+1 ścian, n+2 ścian, itd., a następnie je sumujemy. Dla n=4 liczyliśmy prawdopodobieństwo wypadnięcia dokładnie 4 ścian (p1 * p6 + p2 * p5 + p3 * p4), 5 ścian (p2 * p6 + p3 * p5) i 6 ścian (p3 * p6). Ten wzór ładnie przekształcamy i wychodzi to, co napisał kg86. Czasami trzeba przyjąć, że cząstkowe prawdopodobieństwo wynosi zero (za mało rzutów dla określonej ilości ścian lub za mała ilość ścian kostki). W przykładzie kg86 akurat p3 = 0 i p6 = 0, ale pewnie chodziło mu stan po 3 rzutach kostką, wtedy te prawdopodobieństwa są > 0 ;) .

liffe

Ja to chyba jestem głąbem, skoro do mnie matematyka nie dociera (zresztą nigdy nie lubiłem prawdopodobieństw), a siedzę z tym już ponad dwie godziny. Wszystko jedno nie rozumiem jak to ma działać.
Z poprzedniego postu :
P6 = p3*p6
P5 = P6 + (p2*p6 + p3*p5) = p2*p6 + p3*(p5+p6)
P4 = P5 + (p1*p6 + p2*p5 + p3*p4)=p1*p6 + p2*(p5+p6) + p3*(p4+p5+p6)
Wtedy:
P3 = ??? <może P3 = P4 + (p1*p5+p4*p2)> :?
P2 = ??? <moze P2 = P3 + (p1*p4) = 1 (no bo inaczej sie nie da)> :?

Spectro

@liffe:
Zgadza się :) . Prawdopodobieństwo wypadnięcia liczby ścian mniejszej niż 3 na obu kostkach już po pierwszym rzucie wynosi 1. A te iloczyny rzeczywiście się sumują do jedynki.

liffe

No teraz mam nadzieję, że się uda.
Na razie nie chce mi wczytywać doubla z wejscia, nie moge sprawdzic tego, co napisałem :-)

liffe

RTE hmmmmmmm

Skrobocik

Napiszę Wam fazę, jaka mnie spotkała z tym zadaniem:
siedziałem nad nim długo, przyznaję, bo nie mogłem wykminić jak zrobić to na trzech wymiarach. Dopiero jak przeczytałem na forum ten post Konrada, to wymysliłem sobie, że jednak zrobię oddzielnie dla każdej kostki, a potem przemnażanie po macierzach. Wykminiłem, napisałem, potestowałem i siedziałem dwa dni szukając błędów, gdyż dla danych wejściowych:

Madras

Bo to są najbardziej skrajne, i najbardziej wredne dane, dla których wyniki mogą się różnić w zależności od zastosowanego algorytmu - ze względu na przybliżenia.

Uff, nie ma to jak udany submicik. A bałem się, że będzie TLE, bo mój algorytm był maxymalnie kiepski O( wynik * ( sc1 * sc1 + sc2 ) ) (należy zwrócić uwagę na sc1*sc1, dla danych 100 2 wykonywał zagnieżdżone 10k operacji, a nie 200 ;>). Co prawda wiedziałem, jak zrobić O( wynik * ( sc1 + sc2 ) ), ale jestem naprawdę leniwym człowiekiem :>.

liffe

RTE => TLE => BLE-BLE-BLE... wkurza. Czy moglby ktos zobaczyc w kod, co robie nie tak, bo mam TLE. Ktos mowil o wyliczaniu prawdopodobienstwa w jednej petli, a nie w dwoch, a ja nie wiem jak to zalatwic :?

Sobek

Podrzuć na priva.

kg86

@liffe - a robisz to tym sposobem z liczeniem prawdopodobienstwa odzielnie dla dwoch kostek? :) ja tam zrobilem z obliczaniem tej kombinacji prawdopodobienstwa w 2 petlach [n^4? :D] a smigalo az milo :) nie mialem jakis specjalnych optymalizacji - zaczynalem obliczac to prawdopodobienstwo od momentu wykonania minimalnej liczby ruchow, kiedy przekroczyc wartosc 0 :) np. jesli mamy 2 kostki 100-scienne, a musimy obliczyc prawdopodobienstwo dla 200 scian... to wiadomo, ze dopiero po 100 rzutach obiema kostkami prawdopodobienstwo wyrzucenia 200 scian w sumie przekroczy 0 :)
tak samo nie warto podczas obliczania tej kombinacji isc po wszystkich polach, tzn.
for (i = 1; i <= liczba_wyrzuconych_scian_na_pierwszej_kostce; i++)
for(j = 1; j <= liczba_wyrzuconych_scian_na_drugiej_kostce; j++)
if(i+j >= oczekiwana_liczba_scian) suma += kostka1[i]*kostka2[j];

tylko najpierw obliczyc ograniczenia dla tych petli, aby zawsze i+j dawalo conajmniej oczekiwana liczbe scian :)
ponadto warto najpierw zsumowac wszystkie wartosci po j w kostka2[j], a dopiero potem pomnozyc to przez kostka1[i] :)
i teraz mozna zauwazyc, ze nie musimy w kazdej petli i, od nowa sumowac tego wszystkiego po j, bo w kazdej kolejnej petli i, suma bedzie roznila sie o jeden wyraz, takze w ten sposob mozna zrezygnowac z petli j, zastepujac ja doliczaniem do pewnej sumy kolejnego wyrazu z kostka2...
nie wydaje mi sie to zbyt zrozumiale, wiec przyklad:
kostka1[i] - prawdopodobienstwo wyrzucenia i scian na kostce 1
kostka2[j] - prawdopodobienstwo wyrzucenia j scian na kostce 2
niech kostka1 bedzie 4-wymariowa, a kostka2 5-wymiarowa :)
chcemy policzyc prawdopodienstwo dla 7 scian, jest ono rowne:
kostka1[2] * kostka2[5] + kostka1[3] * (kostka2[4] + kostka2[5]) + kostka1[4] * (kostka2[3] + kostka2[4] + kostka2[5])
wiec, z kazdym zwiekszeniem indeksu i, dla kostka1[i], suma po j, dla kostka2[j] przez ktora mnozymy kostka1[i], zwieksza sie o jeden wyraz :) wiec petle obliczajaca sume po j, mozna zastapic dodawaniem jednego wyrazu do sumy po j, obliczonej w poprzedniej petli :) nie umiem tego prosciej wyjasnic :P