| 41 Стрекаловский Олег [ВГПУ], 21 мая 2011 г. 14:44:01 |
| Вычисляйте корень методом Ньютона(касательных) для целочисленного ответа и не парьте себе мозг ;)
|
|
|
| 42 Даньшин Антон Анатольевич [MIPT], 28 августа 2010 г. 5:06:23 |
| Боже мой я ето сделал.... ух!
|
|
|
| 43 Сафаров У. Б., 11 марта 2010 г. 19:59:36 |
Как я понимаю от администратора помощь не дождусь.
Я бы посоветовал Вам прочитать разбор задачи.
|
|
|
| 44 Лунёв Антон Андреевич, 05 августа 2009 г. 22:49:06 |
Мое решение с ID 457083 укладывается в тайм лимит даже для 50000-значных чисел.
И там я использую систему счисления с основанием 10000,
а очередную цифру нахожу всего за две пробы (цифра здесь - это число от 0 до 9999),
причем вторая проба нужна крайне редко.
To admin: Если интересно, можете взглянуть.
|
|
|
| 45 Степанов Егор Владимирович, 30 июля 2009 г. 22:50:26 |
| Хм, на Джаве достаточно просто аксептится :))))
|
|
|
| 46 Соболев Евгений, 28 июня 2009 г. 16:33:18 |
| Все равно TimeLimit. Скорее всего из-за медленной инициализации новых значений корня...Надо будет переписать на С++ :)
|
|
|
| 47 Соболев Евгений, 28 июня 2009 г. 16:10:49 |
| Думал, что писал решение из разбора с бинпоиском по очередной цифре :) Посмотрел код - оказалось нет... Видимо думал ускорение максимум в два раза...
|
|
|
| 48 Соболев Евгений, 16 июня 2009 г. 16:59:02 |
По ходу трудно на Java сдать решение, которое описано здесь...Почему то бинпоиск по ответу работает быстрее чем решение в разборе :)
по идее бинарный поиск "в лоб" не может работать. вот усовершенствование в сторону подбора очередной цифры бин. поиском, - это другое дело.
|
|
|
| 49 C.C.M., 25 мая 2009 г. 12:41:25 |
Блин, сколько ж раз я отправлял свои код? Надо было сразу делать K*K+2*K*b+b*b! Админ есть легче решение которое меньше писать?
Решения легче не знаю, я могу только еще более сложное, но более быстрое предложить :) Раз я не поленился это написать, то и вам не следует.
|
|
|
| 50 Баширов Ренат Маратович, 19 февраля 2009 г. 10:13:04 |
а вы длинные числа в строках или в массивах хранили?
вряд ли в этой задаче разумно хранить длинное число в строке, ведь это не увеличивает скорость выполнения программы, а здесь это весомый фактор.
|
|
|
| 51 Южанин Денис Сергеевич, 29 января 2009 г. 19:39:47 |
Кстати, а очередную цифру можно же логарифмически искать. Тогда общая сложность будет n*ln(n)
Это вряд ли. На каждом шаге требуется умножение длинного на короткого, т.е n*ln(n) - это сложность нахождения одной цифры, т.е. общая сложность n*n*ln(n). Если не верите, попробуйте ка решить эту задачу для чисел из миллиона цифр, думаю, что это нереально.
|
|
|
| 52 Мухамадеев Руслан Азатович [Orsk Team], 05 октября 2008 г. 14:14:53 |
Интересно, здесь нужно использовать десятичную систему исчисления либо другую? Если другую, то как осуществить сдвиг в умножении при сумировании?
Десятичную разумеется, не представляю как вам тут другая система счисления помочь может.
|
|
|
| 53 Нагин Сергей Юрьевич, 19 августа 2008 г. 11:24:31 |
O((len(s)+1)/2*log(10)*((len(s)+1)/2^2+1))
Это и есть квадратичная сложность: O((len(s)+1)/2*log(10)*((len(s)+1)/2^2+1))=O(len(s)^2). В худшем случае может тут прийти идея дихотомии и это будет O(N*N*ln(N)). Но раз есть решение, то ведь понятно, что там перебор по всем цифрам, а для определения каждой цифры достаточно несколько линейных операций, что и дает нам квадрат и быстрее никак, но этот квадрат тоже надо оптимально реализовать все же N достаточно велико и неаккуратная реализация приводит к TLE.
|
|
|
| 54 Нагин Сергей Юрьевич, 10 августа 2008 г. 11:01:06 |
админ на эту задачу на всех сайтах ограничения на n=10**100 может исправиш недостаток.
Нет уж, я ее специально усложнил, чтобы не "расслаблялись" и использовали один из эффективных алгоритмов :) кстати в решении вроде бы есть описание сиего процесса, который подразумевает еще дальнейшую доработку. Мое решение (хоть и не самое оптимальное) проходит, его можно ускорить еще как минимум вдвое.
|
|
|
| 55 Artem, 05 мая 2008 г. 17:37:39 |
Скажите пожалуйста я взял разбор этой задачи с сайта olympiads.ru? скажите, разбор не совсем коректный или реализация плохая?
Разбор корректный, я именно по этому разбору и написал сам :). Кстати, написал я неоптимально, чего хватило "за глаза". Я текущую цифру подбираю простым перебором, а можно дихотомией (половинным делением), что могло бы ускорить программу еще раза в 2-3.
|
|
|
| 56 Самсонов Иван, 06 ноября 2007 г. 2:45:48 |
Бинарный поиск на java-е не проходит по времени :'(
Там есть еще более быстрое решение, но боюсь, что действительно на джаве это может не пройти по времени. Но вполне вероятно, что может "прокатить". Это еще надо проверить, а то как то несправедливо по отношению к языку Java.
|
|
|
