Привет всем.
Сразу приведу ссылку на задачу http://informatics.mccme.ru/moodle/mod/statements/view.php?id=2307.
Как такое вообще возможно?
Или же это специфика функции math.sqrt() реализированной в питоне?
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3390 |
| 6 | Um_nik | 3387 |
| 7 | tourist | 3384 |
| 8 | heuristica | 3322 |
| 9 | turmax | 3319 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 4 | AmShZ | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | maroonrk | 134 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 07.10.2026 02:43:03 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
Может там сыграть на переполнении?
На питоне? Со встроенное длинкой? Или же длинка только для целых?
Я конечно кривой , но гугл не знает различий в питоне 2.7 и питоне 3 в выполнении sqrt. Я так понимаю что в направлении различия версий питона нужно покопать)
На питоние 2.7 ответ такой же как на 3.1 (
Посылкимои посылки)< sarcasm> Ну да, ну да, "со встроенной длинкой". И
оно вам в длинке точно посчитает. И sin(1). < /sarcasm>
Не надо надеяться на магию, и надо понимать, как работает используемый вами инструмент. ИМХО, это большой минус языков вроде питона (точнее, даже не языка, а культуры, сложившейся вокруг него). Многие "программисты" полностью полагаются на магию, не понимая, как оно работает на самом деле.
меня при изучении питоне удивило что не могу найти за сколько работает какая-нибудь функция встроеная. Есть ли аналог сайту для с++. Конкретно интересует время выполнения.А то нет понимания как написаны функции питона и получается такой себе кот в мешке.
На официальном сайте есть.
Upd: извиняюсь, асимптотики алгоритмов там нет.
длинка только для целых. для вещественных в обеих версиях используется обычный сишный double, так что не очень понятно, для чего именно третий думаю, что и в корне различий не должно быть..
В темах указан бинарный поиск по ответу. Вот и нужно думать в этом направлении.
Казалось бы, не очевидно почему бы этой штуке быть монотонной по x, если не понятно, когда это верно.
Поищите например минимальное неотрицательное целое такое, что
x/2*2!=xтаким спосоом (деление целочисленное)А разве для целочисельного деления — ответ не 1? Или смысл в том, что бы найти его бинпоиском?
Смысл в том, что бинпоиском его нельзя искать по понятным причинам и прежде чем искать бинпоиском ответ на исх.задачу(как советовали) хорошо бы для начала понять почему бинпоиск будет работать.
Она не монотонная. Для 5x1018 + 1 и 5x1018 - 1 ответ: !=, для 5x1018 ответ: ==
Magic : http://ideone.com/9tHg25
Мне кажется, фича в том, что считается это в нецелых, которые вроде не длинка, а обычные даблы со всеми вытекающими ошибками. Например при
i = int(1e230)уже даже нельзя вызватьmath.sqrt(i*i)Кто-то пробывал уже отослать с идеей переполнения?)
Долбил с другом эту задачу. Сдали. Прошла с первой попытки. В первой правке подсказка.
Мда уж. Задача простая же.
Подсказка в первой правке.
Может докажете почему это работает? Почему если для числа 100 все хорошо, то для числа 97 тоже?
Я не опирался на монотонность функции, или особенностях даблов. Просто искал верхнюю границу ответа while (math.sqrt (x * x) == x) x++. Где в виде x подставлял степени 10ки. Как только на 10 ^ 16 ответ нашелся быстро (10 ^ 16 + 1). Начал уменьшать старшие разряды, и просто брутфорсом проверял, быстро ли ответ найдется. То есть брал например 9 * 10 ^ 15, и увеличивал или уменьшал в зависимости от того, быстро нашелся ответ или нет. Я не знаю, как доказать это, скажем так, само как — то вышло :)
вот вы посмотрели, для 100 все хорошо, для 1000 все хорошо ... , плохо для 10^16+1, и начали искать на промежутке 10^15...10^16, так? А почему для числа 578 все верно?
Что вы имеете ввиду под 578? Я смотрел числа от 10 ^ 15 до 10 ^ 16, последовательно справа налево строя префикс числа, проверяя быстро ли находится ответ, где то по 1.5 — 2 секунды на каждое изменение числа, за это время мы пройдемся по внушительному количеству чисел с заданным префиксом, и поэтому интуитивно понимая, что число нужно брать больше.
578 — любое число, меньшее 10^15, не являющееся степенью десятки
Я предположил, что поскольку все дело в точности, то чем больше число, тем больше в его окрестности "плохих" чисел. Вверху NurlashKO сдал бинпоиск по окрестности точек, что то такое, только конструктивом сделал я :)
Решение в одну строку
Обоснование
Т.е. питон хранит вещественные числа < 253 + 1 несократимой дробью?
Это особенности типа double. http://en.wikipedia.org/wiki/Double-precision_floating-point_format