Abra's blog

By Abra, 13 years ago, translation, In English
Today's date recalls one interesting task from spoj.pl.
It's easy - just print as many correct Pi decimal digits as possible.
I've tried a lot of methods
from easiest (~200 digits)

through funny (~1000 digits)
 

to the most effective I've found (~7300 digits)




Also I have an idea to use this tricky formula

to find hexadecimal digits and convert them to decimal.

My best solution is written in Java and uses BigDecimal and self-written sqrt.

May be I should optimize long arithmetics? Or search for new methods?

Please help me to calculate billion digits =)

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it

By Abra, 13 years ago, translation, In English
Привет, мир! Это мой первый разбор, просьба сильно не пинать. =)
A. Разведка 2
Нахождение минимума в массиве, с одим дополнительным сравнением первого и последнего элементов.
B. Распродажа
Отрицательные элементы складываем в массив, сортируем, находим сумму m наибольших по модулю.
C. Список
Решается массивом булей, единственная заковыка - с выводом, но вполне преодолима.
D. Карта дорог
Создаем динамическую матрицу смежности, например, массивом стеков, заполняем. Потом волновым алгоритмом из r2, пробегаясь по каждой вершине один раз, пролучаем результирующий массив.
E. Столкновения
Заведем переменную времени ct, которая вначале равна 0.
Начинаем моделировать:
Пусть dt равен t - ct, просматриваем все пары шариков, по формуле 
x1 + v* dt = x2 + v2 * dt
dt = (x1 - x2) / (v2 - v1)
находим минимальную dt - промежуток времени, через который какие-нибудь шарики столкнуться, или время моделирования закончится.
Сдвигаем шарики на этот промежуток времени, снова просматриваем все пары, если координаты двух совпадают, меняем их скорости по формуле из условия.
Повторять, пока ct не сравняется с t.
Особое внимание стоит уделить точности, наверное на этом и подловили RAVEman'а с ACRush'ем. =)
В принятом решении я использовал double и точность сравнений 10-10.

Удачи в контестах!

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it