|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
19.07.2012, 12:07 | #1 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Минимальное число
И снова День добрый, господа архипелаги в безмятежном море программирования, вот нашел (уже давно) очень интересную задачу(мои оченки интересности могут существенно отличаться от Ваших).
Для составления алгоритма ушло овер недели. И "думали, думали и наконец придумали!". Сама задача : Минимальное число (Время: 1 сек. Память: 16 Мб Сложность: 25%) Требуется написать программу, которая из цифр двух натуральных чисел создает наименьшее возможное число, сохраняя при этом порядок следования цифр в этих числах. Входные данные Входной файл INPUT.TXT содержит два натуральных числа, записанных в двух строках. Числа больше нуля и меньше 10255. Выходные данные В единственную строку выходного файла OUTPUT.TXT нужно вывести наименьшее возможное число, удовлетворяющее условию задачи. И снова не красивая ссыль (http://acmp.ru/index.asp?main=task&id_task=548) Ну и маленькое лирическое отступление : сначала была идея рассмотреть все случаи, потом после усердных попыток она отпала, затем преподаватель рассмотрел идею создания алгоритма на основе сортировки "C влиянием" (но она подразумевает, что массив(куда заносим цифры) уже отсортирован => идея отпала), и наконец все общими усилиями появился на свет данный алгоритм : Код:
В данном алгоритме 1192 символа. Возможно это перебор. Но как не странно тесты проходит очень быстро (опять же acmp не славится хотя бы на 50% достоверными сведениями по поводу прохождения тестов). Но все же хочется красоты, изящности, оптимальности. Не могли бы, Вы, премного уважаемые Гении столько Важного Искусства, оказать маленькую (возможно) для Вас, но не оценимую (для меня) услугу. _________________________________ С уважением и почитанием, Poma][a. Последний раз редактировалось Poma][a; 19.07.2012 в 21:16. |
19.07.2012, 14:44 | #2 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
лень регистрироваться на acmp.ru, чтобы проверить своё решение, поэтому доверяю проверку Вам.
Зачем здесь вообще сортировка?! Так не проще? Код:
|
19.07.2012, 15:38 | #3 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Спасибо, за предоставленную возможность! Но насколько я помню, Вы там уже зарегистрировались Вот, если не ошибаюсь Ваш профиль (http://acmp.ru/?main=user&id=91869)
И Ваше решение рушится на 4 тесте (вот для него контрпример :32545 32545 ответ: 3232545455) И еще заметил : в условии сказано, что одно число не превышает 10^255 => результат может превышать эту планку Так же тест 1 10 не проходит Последний раз редактировалось Poma][a; 19.07.2012 в 15:46. |
19.07.2012, 15:56 | #4 | ||
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
Цитата:
снимаю своё решение, как профнепригодное! сорри! Последний раз редактировалось Serge_Bliznykov; 19.07.2012 в 16:03. |
||
19.07.2012, 20:28 | #5 |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
а такой вариант:
Код:
|
19.07.2012, 20:39 | #6 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
6 тест не проходит по времени, и опять же
Цитата:
Последний раз редактировалось Poma][a; 19.07.2012 в 21:15. |
|
19.07.2012, 22:22 | #7 | |
Старожил
Регистрация: 08.04.2012
Сообщений: 3,229
|
Цитата:
Почему 01 - ошибка? По времени - да, можно подобрать пример, на котором это будет работать очень долго. Мне кажется, что-то вроде "111111111111...11" + "11111111111111...11". По поводу >255 символов - алгоритм некритичен к длине строки и не использует специфические строковые функции - только чтение очередного символа и добавление в конец массива. Так что легко может быть переделан со string на pchar. Кстати, после этого, возможно, он будет работать быстрее. Кстати, если сделать строку, в которую мы складываем результат, глобальной переменной, скорость должна существенно возрасти из-за отсутствия копирования полукилобайта памяти при каждом рекурсивном вызове + гораздо более эффективное использование кэш-памяти. Так что интересно, насколько не устраивает по скорости - если величина не очень большая - раз в 10 - еще есть простор для оптимизации. |
|
20.07.2012, 00:18 | #8 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
чуток доработал своё первоначальное решение
Код:
Цитата:
p.s. и я думаю, что решения, которые висят в топе лучших по размеру исходного кода выполнены через рекурсию.. Последний раз редактировалось Serge_Bliznykov; 20.07.2012 в 00:22. |
|
20.07.2012, 04:06 | #9 |
Форумчанин
Регистрация: 05.09.2011
Сообщений: 869
|
Гм.
? (чтоб сообщение прошло по длине, пришлось пофлудить в скобках)
Предпочитаю на "ты".
|
20.07.2012, 08:21 | #10 | |
Забанен
Форумчанин Подтвердите свой е-майл
Регистрация: 01.11.2006
Сообщений: 420
|
Цитата:
Код:
Если ничто другое не помогает, прочтите, наконец, инструкцию! Аксиома Кана
|
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Почему то не считает минимальное число | Alekzinder | Помощь студентам | 0 | 06.05.2012 02:18 |
минимальное число членов сумма которых | АнюточкаАА | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 10.04.2012 19:33 |
Минимальное число выше главной диагонали... | Oliveyra | Общие вопросы C/C++ | 9 | 21.04.2011 22:31 |
Минимальное число | Progs1024 | Паскаль, Turbo Pascal, PascalABC.NET | 14 | 11.10.2009 21:21 |