![]() |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
![]() |
Huver |
![]()
Сообщение
#1
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Репутация: ![]() ![]() ![]() |
Задача:
Дано N целых чисел A1, A2 ... An. Требуется найти кол-во различных сумм вида k1A1 + k2A2 + ... + knAn. Ввод из файла sums.in. В первой строке находится число N, во второй - A1, A2 ... An через пробел. Вывод в файл sums.out. Вывести одно число - количество различных значений сумм. Пример 1: Ввод 1 3 1 1 2 Вывод 1 5 Пример 2: Ввод 2 5 49 100 98 49 0 Вывод 3 10 Заранее спасибо. Сообщение отредактировано: Huver - 14.11.2005 18:39 |
![]() ![]() |
c-ch |
![]()
Сообщение
#2
|
Новичок ![]() Группа: Пользователи Сообщений: 13 Пол: Мужской Репутация: ![]() ![]() ![]() |
прошу прощения за поднимание явно древней темы
![]() уточняю условие задачи: Дано N целых чисел A1, A2, ..., AN. Требуется найти количество различных значений сумм вида k1A1 + k2A2 + ... + kNAN. Входные данные Входной файл INPUT.TXT в первой строке содержит число N, во второй - A1, A2, ..., AN через пробел. Ограничения: все числа целые, 1 <= N <= 500, 0 <= Ai <=100, 0 <= ki <= 1. Выходные данные В выходной файл OUTPUT.TXT выведите количество различных значений сумм. т.е., для приведённого примера с числами 1, 1, 2 правильный ответ будет 5, т.к. суммы будут следующие: 0, 1, 2, 3, 4 (все к=0, к1=1 остальные=0, к3=1 остальные=0, 1+2, 1+1+2) я написал программку, решающую эту задачу, что называется, "в лоб" program qq; проблема в том, что этот алгоритм очень трудоёмок и при N=500 вычисления, мягко говоря, затягиваются ![]() у меня же одним из условий является ограничение по времени и памяти - 1 сек и 16 Мб соответственно прошу помощи у корифеев алгоритмизации ![]() хотелось бы получить рабочий исходник, т.к. времени мало осталось, но буду рад и ценным указаниям (желательно с примерами) спасибо |
Lapp |
![]()
Сообщение
#3
|
![]() Уникум ![]() ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: ![]() ![]() ![]() |
проблема в том, что этот алгоритм очень трудоёмок и при N=500 вычисления, мягко говоря, затягиваются Этих ресурсов тут во много раз больше, чем достаточно (для тех пределов, которые в условии). Вот эта программка обходится примерно 50 КБ и 0.05 сек на моем ноуте (Turion 1.8 GHz) ![]() у меня же одним из условий является ограничение по времени и памяти - 1 сек и 16 Мб соответственно ![]() const -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
![]() ![]() |
![]() |
Текстовая версия | 24.06.2025 2:36 |