English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Temat: Jedynki - testy
Czy można już odkryć ukryte posty? Chodziło oczywiście o schemat Hornera, pi razy oko wystarczy 75 jedynek do zapisu każdej liczby z zadania. Pytałem o jakąś dużą liczbę pierwszą, dla 10**9 też przechodziło.
Tak, schemat Hornera to rozwiązuje. Niech b_i będzie binarnym zapisem liczby B. Wtedy B = \sum b_i x^i = b0+x(b1+x(b2...) dla x=2 ;-) W najgorszym przypadku w ostatniej postaci zastępujesz x przez (1+1) i b_ przez 1. Dla 30 bitowej liczby byłoby to 30 + 29*2 = 88, ale 30 zapalonych bitów to więcej niż 10^9, więc maksimum to 87 dla liczb w rodzaju 2^30-1-2^28 = 805306367
U mnie było top 86, bo "3" wypisywałem jako (1+1+1) a nie jako 1+(1+1)*1, tak było łatwiej ;-)
Edit: http://pastebin.com/2cLE178h [dość krótkie]
U mnie było top 86, bo "3" wypisywałem jako (1+1+1) a nie jako 1+(1+1)*1, tak było łatwiej ;-)
Edit: http://pastebin.com/2cLE178h [dość krótkie]
Dla liczby 805306367 mam 69 jedynek, ale ja użyłem czegoś innego. Nie wiem czego.
O, ciekawe, też użyłem schematu Hornera, ale dla systemu trójkowego. Najgorszy przypadek to:
2 + 3*(2 + 3*(… + 3*(2 + 3*2))…), gdzie mamy nie więcej niż 19 dwójek i 18 trójek, czyli 19*2 + 18*3 = 92 jedynki.
A tutaj można policzyć optymalny rozkład, gdyby ktoś był zainteresowany:
http://expmath.lumii.lv/wiki/index.php?title=Special%3AComplexity
2 + 3*(2 + 3*(… + 3*(2 + 3*2))…), gdzie mamy nie więcej niż 19 dwójek i 18 trójek, czyli 19*2 + 18*3 = 92 jedynki.
A tutaj można policzyć optymalny rozkład, gdyby ktoś był zainteresowany:
http://expmath.lumii.lv/wiki/index.php?title=Special%3AComplexity
Teoretycznie najmniej się powinno dać w 67 jedynek. Pierwsza liczba która wymaga co najmniej 68 jedynek wynosi 1006290359.
https://oeis.org/A005520
https://oeis.org/A005520/b005520.txt
https://oeis.org/A005520
https://oeis.org/A005520/b005520.txt