| 1 coder, 29 сентября 2010 г. 17:30:23 | |
|
Да, но это также требует тщательной и аккуратной реализации.
|
|
|
| 2 Герасимов Виталий Игоревич, 29 сентября 2010 г. 17:02:50 | |
Также С можна решать динамическим программированием:
dp[i][j][k] - количество чисел длины i с суммой цыфр j, произведением k.
|
|
|
| 3 coder, 29 сентября 2010 г. 16:55:16 | |
|
Спасибо, понял. Но мне кажется, что такое решение все-таки посложнее, чем просто найти все ответы.
|
|
|
| 4 Демиденко Виталий, 29 сентября 2010 г. 16:54:03 | |
|
Да, только ещё следует учитывать, что если сумма<произведения, то последовательность нужно добить еденичками, если это возможно
|
|
|
| 5 coder, 29 сентября 2010 г. 16:51:55 | |
|
То есть, рассматриваем все возможные суммы цифр от 0 до 180, смотрим все разложения этих чисел на множители, считаем общее количество перестановок цифр в каждом разложении по формуле перестановок с повторениями, а также находим минимальное число. Так что-ли?
|
|
|
| 6 Демиденко Виталий, 29 сентября 2010 г. 16:49:17 | |
|
Перебираешь (да да перебираешь) все различные разложения чисел от 1 до 180 на множители. Дальше понадобится комбинаторика. Я ещё во время этого перебора запоминал минимальное число.
|
|
|
| 7 coder, 29 сентября 2010 г. 16:47:12 | |
|
А как решать С не перебором?
|
|
|
| 8 Демиденко Виталий, 29 сентября 2010 г. 16:45:06 | |
|
Меня просто удивило, что ты решив D, не придумал решения C. Но прекалк тоже имеет место.
|
|
|
| 9 coder, 29 сентября 2010 г. 16:42:13 | |
|
Да, понятно, что можно написать очень эффективный перебор по этой задаче. Но я, чтобы особо не думать над оптимизациями во время контеста, улучшил его до такой степени, чтобы можно было ответы сгенерировать быстро.
|
|
|
| 10 Демиденко Виталий, 29 сентября 2010 г. 16:39:06 | |
|
Ну тут нужно смотреть, что именно под перебором понимается:) Я вот вроде написал перебор, но прошёл он за 0.15 сек.
|
|
|
| 11 coder, 29 сентября 2010 г. 16:38:26 | |
|
Если Вы в том смысле, что можно и побыстрее чем 1 мин., то на самом деле он работает у меня меньше 10 сек. Это я так, вверх до минуты округлил.
|
|
|
| 12 coder, 29 сентября 2010 г. 16:35:00 | |
|
Что значит - не оптимизированный перебор. По-моему весьма нормально оптимизированный! Или Вы в том смысле, что нельзя столь хороший перебор написать?
|
|
|
| 13 Демиденко Виталий, 29 сентября 2010 г. 16:23:50 | |
|
1 минута - это не оптимизированный перебор
|
|
|
| 14 coder, 29 сентября 2010 г. 15:58:42 | |
|
Да не за что...
|
|
|
| 15 Гость, 29 сентября 2010 г. 15:54:46 | |
|
Ух ты(!), не знал. Спасибо)
|
|
|
| 16 coder, 29 сентября 2010 г. 15:49:58 | |
|
Каждый участник в разделе "Сдать задачу" может посмотреть итоговые баллы по каждой сданной на проверку задаче после окончания олимпиады.
|
|
|
| 17 Гость, 29 сентября 2010 г. 15:46:00 | |
|
А как Вы узнали результаты?
|
|
|
| 18 coder, 29 сентября 2010 г. 15:41:59 | |
|
Да, в сумме 400. Я отправил Вам решение на почту. Оно пришло?
|
|
|
| 19 Герасимов Виталий Игоревич, 29 сентября 2010 г. 15:41:55 | |
|
Спасибо за решение
|
|
|
| 20 Герасимов Виталий Игоревич, 29 сентября 2010 г. 15:39:21 | |
|
А сколько у Вас в сумме? 400? (если не секрет :) )
|
|
|
