Ilotrzyny bis

ďťż

Ilotrzyny bis

Anna Piekarska - 8 mar 2010, o 00:06
" />Przy okazji myślenia nad zadaniem "Ilotrzyny" przyszedł mi do głowy pewien, dość podobny, problem. Rozwiązanie, które wymyśliłam zdaje mi się być ładniejsze i ciekawsze od mojego rozwiązania oryginalnego zadania (mam tylko nadzieję, że jest poprawne:)). Dlatego chciałabym się podzielić problemem i zadać Wam pytanie, czy macie jakieś fajne pomysły (taki After Party Challenge).
Oto zmiany w zadaniu:
Zamiast iloczynu trzech liczb pytamy się o iloczyn wszystkich poza trzema. Żeby wynik nie wyszedł za duży, zróbmy to modulo. Żeby rozwiązanie "wymnóż wszystko i zapamiętaj, każdą liczbę x zastąp liczbą 1/x, rozwiąż wersję oryginalną" nie działało, niech liczba m (modulo) będzie podana wśród danych wejściowych. Żeby uniknąć możliwości faktoryzacji do chińskiego tw. o resztach, niech ta liczba będzie duża (~10^18).
Zapraszam do zabawy - rozwiązanie jest dośc podobne, ale jest w nim jeden piękny fragment
Kiedyś, jak będą chętni, podzielę się moją ideą.

Wojtek Nadara - 9 mar 2010, o 20:53
" />Na mój gust, to chyba będzie coś takiego:
Przez il0 oznaczę iloczyn liczb na przedziale il, przez il1 iloczyny liczb na przedziale il bez jednej itd. Przez A i B oznaczmy przedziały, z których przetwarzamy dane, a przez przedział C sumę tychże przedziałów.
Mamy tutaj zależności:
C0=A0*B0
C1=A0*B1+A1*B0
C2=A0*B2+A1*B1+A2*B0
C3=A0*B3+A1*B2+A2*B1+A3*B0
Od tego momentu nie ma już chyba żadnych różnic z rozwiązaniem ilotrzynów, na mój gust modulo nam w niczym nie przeszkadza.

Tylko to rozwiązanie jest wręcz tożsame z rozwiązaniem ilotrzynów, więc się trochę obawiam o jego poprawność .

Darmowy hosting zapewnia PRV.PL