|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
19.03.2015, 15:59 | #21 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
да, программа то есть, но она настолько корявая, что мне аж стыдно её показывать...
у меня в данный момент нет никакой IDE(Pascal/Delphi) под рукой, так я тоже на ideone пытался гонять код. Но не очень успешно, там ограничение на 5 секунд на выполнение кода стоит. А для данной задачи это чрезвычайно мало. впрочем, сделаем вид, что это не я писал, а нашёл где-то чей-то чужой кривой код извольте код: Код:
буду рад выслушать предложения/мнения по алгоритмам решения данной задачи! я бы всё таки копал в сторону математической теории. Очевидно, что минимальная разница сумм модулей не может быть меньше единицы. И, на мой взгляд, решать задачу нужно двигаясь от N одновременно и в сторону уменьшения и в сторону увеличения. Вопрос только - с каким шагом (всегда ли движение с шагом 1 оправдано) и, главное, когда можно прерывать цикл. |
19.03.2015, 16:11 | #22 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Супер! Спасибо!
А я за такой вариант.. Заменять простые множители на большие\меньшие.. |
19.03.2015, 16:21 | #23 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
|
19.03.2015, 16:49 | #24 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Не надо тут теории. Идем в цикле N-1,N-2,..,N-i,.. и вычисляем минимум пока i не станет больше или равен минимуму, дальше нет смысла, минимум в эту строну нашли. Аналогично N+1,N+2,...,N+i,.. То есть интервал не фиксированный какой-то формулой, а плавающий
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 19.03.2015 в 16:56. |
19.03.2015, 16:54 | #25 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
N = 12
12 = 2*2*3 Ищем K Давайте заменим 3-ку на новый простой делитель.. Это 5 2*2*5 = 20 Не очень.. А давайте замени на произведение двух простых делителей.. 2*2*2*2 = 16.. Классно, да? Давайте 71 : тут уже след. простое - 73.. Давайте 27 = 3*3*3 Снова 3*3*2*2=9*4=36 плохо.. Давайте в другую сторону 3*3*2 = 9*2 = 18 это 21+18 = 39. Ответ для 27 - 40.. Классно, да? Давайте тест из примера : 900.. Sum = 1921 SN = 1921+900=2821.. Так.. 900=2*2*3*3*5*5 Наше любимое занятие - заменять одну тройку на две двойки.. 2*2*2*2*3*5*5=1200 Summ 2644 .. Чет не ахти.. Давайте двойку на треху.. 2*3*3*3*5*5 = 1350 Summ 2370.. Лучше.. Но А давайте из 2*2*3*3*5*5 заберем 6-ку и добавим 7-ку.. 2*3*5*5*7 = 1050.. Sum 1926 С ответом сошлось.. Давайте ради прикола след. пример : 2*2*2*2*3*3*5*7 = 5040 Sum 14304 SN = 19344 Давайте 2*2*3=12 -> 13 2*2*3*5*7*13 = 5460 Sum 13356 Ну хорошо.. Давайте еще побалуемся.. 2*2*2*3*5*7*7 = 5880 Sum 14640 О! уже лучше.. Давайте еще.. Свернем 7-ку в 8-ку 2*2*2*2*2*2*2*3*3*5 = 5760 Sum 14130.. А теперь давайте прибавим.. SK = 14130 +5760 = 19890 Как-то так.. Правда как это все делать.. пока не понятно.. Цитата:
32 SN = 63.. 31 SN = 32 30 SN = 72 29 SN = 30 28 SN = 56 Последний раз редактировалось Poma][a; 19.03.2015 в 16:56. |
|
19.03.2015, 17:15 | #26 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Ромаха ты забыл про Abs(N-K)+Abs(SN-SK)
Код:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 19.03.2015 в 17:25. |
19.03.2015, 17:28 | #27 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Эт да.. Воистину печалька..
А для фанатов ideone можно маленький коммент? |
19.03.2015, 17:33 | #28 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
ideone чего это?
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
19.03.2015, 17:37 | #29 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
What is Ideone?
Ideone is an online compiler and debugging tool which allows you to compile source code and execute it online in more than 60 programming languages. Если вкратце, то у меня нет дельфина, у Сержа нет дельфина.. Поэтому осознать всю божественность кода в посте 26 - малясь проблематично.. Поэтому было бы прекрасно, если бы Вы его шушуть прокомментировали.. |
19.03.2015, 17:42 | #30 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Дык в #24 вроде идея и описана, переведи на паскаль, на выходе t и есть искомое k. Все пять тестов из условия прошли, max время не помню, или 2, или 3 минуты, для предпоследнего. SumDel оптимизировать еще - цикл до корня квадратного
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Вычислить произведение чисел, неравных заданному числу Z | Hug | Помощь студентам | 4 | 12.11.2013 23:27 |
найти кол-во трехзначных чисел сумма простых делителей которых кратна 5 (на Делфи) | anzorchik | Помощь студентам | 2 | 02.10.2011 16:18 |
Определить ближайший элемент массива к заданному числу | wowan | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 28.05.2011 23:21 |