|
712 / 351 / 120
Регистрация: 09.12.2020
Сообщений: 918
|
||||||
Сложение дробей с округлением14.11.2021, 02:24. Показов 4854. Ответов 21
Метки нет (Все метки)
Здравствуйте. Решал задачу со следующим условием:
Дано целое число n. Найдите значение суммы (РИС. 1) Здесь ⌊x⌋ — это округление x вниз: наибольшее целое число, не превосходящее x. Формат входных данных В первой строке записано целое число n (2 <= n <= 10^18). Формат выходных данных В первой строке выведите одно целое число — значение суммы. Примеры ввод 3 вывод 2 ввод 10 вывод 11 решил сделать список числителей, знаменателей и потом все это дело поделить. Закономерно ошибка - тайм лимит. Подскажите, пожалкйста, как оптимизировать решение. Код:
0
|
||||||
| 14.11.2021, 02:24 | |
|
Ответы с готовыми решениями:
21
Сложение дробей |
|
712 / 351 / 120
Регистрация: 09.12.2020
Сообщений: 918
|
|
| 14.11.2021, 02:25 [ТС] | |
|
Ограничение по времени:2 секунды
Ограничение по памяти: 512 мебибайт
0
|
|
|
2431 / 1474 / 633
Регистрация: 01.11.2021
Сообщений: 2,269
|
|
| 14.11.2021, 14:12 | |
|
Удалено.
0
|
|
|
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
|
|||||||||||
| 14.11.2021, 14:29 | |||||||||||
|
alilxxey,
alilxxey, Думаю можно даже так.
0
|
|||||||||||
|
2431 / 1474 / 633
Регистрация: 01.11.2021
Сообщений: 2,269
|
||||||
| 14.11.2021, 14:34 | ||||||
|
Опыта для этого не много, просто было интересно.
Видимо задание для оптимизации вычисления степеней, наверно. Например, если округление в меньшую сторону, то если добавить условие, что числитель меньше знаменателя, то вычислять смысла нет, т.к. все время будет 0, а на это уходит большая часть времени. В 2сек уложиться невероятно, интересно посмотреть, если кто-то справится для 10** 18. Просто сумму посчитать можно и так, но мне кажется не в этом суть задания.
0
|
||||||
|
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
|
|
| 14.11.2021, 14:38 | |
|
Alexarh, мой код выходит за 2 сек, при n = 10^14
1
|
|
|
712 / 351 / 120
Регистрация: 09.12.2020
Сообщений: 918
|
||||||
| 14.11.2021, 14:42 [ТС] | ||||||
|
anton78spb, да, я уже написал похожий код:
0
|
||||||
|
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
|
||||||
| 14.11.2021, 15:07 | ||||||
|
alilxxey, Там правда у меня ошибочка небольшая. Стандартная, в конце диапазона единичку забыл. Там надо в к корню из n еще +1 добавить.
0
|
||||||
|
1190 / 766 / 277
Регистрация: 05.09.2021
Сообщений: 1,772
|
|
| 14.11.2021, 15:12 | |
|
alilxxey, попробуй еще из math извлечение корня и возведение импортнуть, глянь какой будет прирост.
0
|
|
|
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
|
||||||
| 14.11.2021, 15:16 | ||||||
|
alilxxey, Вот так еще на 10% быстрее. Но не в разы.
enx, У меня в коде корень берется только один раз, а в квадрат я возвожу простым умножением.
0
|
||||||
|
1190 / 766 / 277
Регистрация: 05.09.2021
Сообщений: 1,772
|
|
| 14.11.2021, 15:24 | |
|
anton78spb, конечно, я про другой вариант выше говорил.
0
|
|
|
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
|
|||||||||||
| 14.11.2021, 16:15 | |||||||||||
|
Че-то никак не пойму как это можно ускорить. Количество элементов необходимых для расчета суммы выбрано правильно, он равно корню из n. Т.е. лишних вычислений, с заведомо нулевым результатом не производится. Соответственно при максимальном n = 10^18, у нас получится ряд из 10^9, значений.
Первый элемент суммы всегда равен n - 1. Добавлено через 19 минут И еще вопрос. Почему вариант использующий исключительно целочисленное деление.
0
|
|||||||||||
|
1190 / 766 / 277
Регистрация: 05.09.2021
Сообщений: 1,772
|
|
| 14.11.2021, 16:20 | |
|
anton78spb, флоты медленные очень, в Питоне так вообще кошмар.
0
|
|
|
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
|
||||||
| 14.11.2021, 16:29 | ||||||
|
Вот такой вариант работает примерно на 25% быстрее предыдущих.
От куда берется этот десятичный разделитель? Мы же сначала делим "обычным" способом, а после делим "нацело", и соответственно результатом деления нацело должно получиться целое число. Добавлено через 55 секунд enx, Так прикол-то в том, что в данном примере они работают быстрее чем целочисленные вычисления.
0
|
||||||
|
1190 / 766 / 277
Регистрация: 05.09.2021
Сообщений: 1,772
|
|||||||||||
| 14.11.2021, 16:35 | |||||||||||
|
anton78spb, да все просто на самом деле:
Флоты они такие, всегда найдут способ пробраться )))
0
|
|||||||||||
|
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
|
|||||||
| 14.11.2021, 16:54 | |||||||
|
Короче, друзья. Все вышенаписанные варианты, это тупиковая ветвь. Т.к. при n = 10^15, даже сумма "простого ряда" от 1 до корня из n уже считается больше двух секунд. И это без каких-либо вычислений элементов этого ряда.
Добавлено через 4 минуты Также проверил, что sum работает быстрее чем суммировать "ручками" в цикле. И замена sum на fsum из модуля math практически не помогает.
0
|
|||||||
|
1190 / 766 / 277
Регистрация: 05.09.2021
Сообщений: 1,772
|
|
| 14.11.2021, 16:56 | |
|
anton78spb, глянь как будет на np.sum, он быстрее раз в 10 на таком массиве. Но суть верная, тут нужна формула, я ее не знаю к сожалению тоже. Может кто заглянет, подскажет.
0
|
|
|
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
|
|||
| 14.11.2021, 17:13 | |||
|
Добавлено через 5 минут
0
|
|||
|
1 / 1 / 0
Регистрация: 06.08.2021
Сообщений: 2
|
||||||
| 19.11.2021, 20:14 | ||||||
|
у меня вот этот код на 70 баллов зашел, тут надо математически решать, вряд ли с помощью индукции
1
|
||||||
|
712 / 351 / 120
Регистрация: 09.12.2020
Сообщений: 918
|
||
| 20.11.2021, 21:26 [ТС] | ||
|
RedHathacker, Да, у меня такой же почти код на 68 баллов зашел.
Добавлено через 1 минуту RedHathacker, напиши пожалуйста мне в лс
0
|
||
| 20.11.2021, 21:26 | |
|
Помогаю со студенческими работами здесь
20
сложение дробей
Сложение дробей Сложение дробей. Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Сумматор с применением элементов трёх состояний.
Hrethgir 26.03.2026
Тут.
https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc
Первый документ красиво выглядит, но без схемы.
Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
|
Автозаполнение реквизитов при создании документа
Maks 26.03.2026
Код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере".
Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита, которое может. . .
|
Команды "Заполнить" и "Очистить" на форме документа
Maks 26.03.2026
1. Команда формы "ЗаполнитьЗапчасти".
На примере нетипового документа разработанного в конфигурации КА2.
В качестве источника данных указан регистр накопления, в который записываются данные о. . .
|
Кому нужен AOT?
DevAlt 26.03.2026
Решил сделать простой ланчер
Написал заготовку:
dotnet new console --aot -o UrlHandler
var items = args. Split(":");
var tag = items;
var id = items;
var executable = args;. . .
|
|
Отправка уведомления на почту при изменении наименования справочника
Maks 24.03.2026
Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .
|
модель ЗдравоСохранения 5. Меньше увольнений- больше дохода!
anaschu 24.03.2026
Теперь система здравосохранения уменьшает количество увольнений.
9TO2GP2bpX4
a42b81fb172ffc12ca589c7898261ccb/
https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/
Слева синяя линия -. . .
|
Midnight Chicago Blues
kumehtar 24.03.2026
Такой Midnight Chicago Blues, знаешь?. .
Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
|
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++
8Observer8 24.03.2026
Содержание блога
Финальные проекты на Си и на C++:
finish-text-sdl3-c. zip
finish-text-sdl3-cpp. zip
|