Разбиение числа на слагаемые

[p1r2o3]

Мне недавно попалась задачка про разбиения чила на не повторяющиеся слагаемые. Уже неделю как мучаюсь.. но без толку.. кто-нибудь знает как его решать? формулу-то я знаю.. вот как его применять это неизвестно.

[LeBron]

В чем конкретно задача? посчитать число разбиений? Или найти все разбиения (вывести их, к примеру)? В первом случае формулой или динамикой, во втором я чаще всего пишу циклическую генерацию лексикографически предидущего или лексикографически следующего разбиения (повторять до тех пор, пока возможно, и выводить, что получается).
Какие ограниения?.

[p1r2o3]

выводить количество. n может быть от 5ти до 500

[LeBron]

Так если у Вас формула, есть, то в чем проблема?
Хотя при 500 даже оптимально написанная кубическая динамика должна проходить в пределах секунды.

[p1r2o3]

по времени не совпадает..
а если ввести массив то по памяти не будет совпадать

[eoln]

Ну можно тупо в лоб и сразу на вывод. Памяти не требует, скорость - миллиард за 3 секунды обрабатывает

uses
  system;
var
  i, x: longint;
begin
  readln(x);
  i := 1;
  repeat
    x := x - i;
    write(i, ' ');
    inc(i)
  until x <= 2*i;
  writeln(x);
  writeln('count = ', i);
  readln
end.

P.S. Для чисел больше двух.

[Serebro]

нужен ли случай 0+n?

[LeBron]

Сообщение от eoln

Ну можно тупо в лоб и сразу на вывод. Памяти не требует, скорость - миллиард за 3 секунды обрабатывает

uses
  system;
var
  i, x: longint;
begin
  readln(x);
  i := 1;
  repeat
    x := x - i;
    write(i, ' ');
    inc(i)
  until x <= 2*i;
  writeln(x);
  writeln('count = ', i);
  readln
end.

P.S. Для чисел больше двух.

О_о Вы хоть тестировали это? Оно как бы не работает...

Сообщение от p1r2o3

выводить количество. n может быть от 5ти до 500

Задачка откуда? И важен ли порядок чисел в разбиении? Если нет - детски простая динамика пишется легко и точно проходит (взгляните на задачу 1017 на Тимусе, я использовал там именно такую динамику, ограничения по времени 1 секунда, по памяти 16 мб, проходит, у меня
1017 C++ Accepted
0.078 2 813 КБ).
Если да - надо подумать над более красивым решением, можно просунуть и такое, но его надо будет дописать и доделать в ущерб красоте и простоте.

[eoln]

Сообщение от LeBron

О_о Вы хоть тестировали это? Оно как бы не работает...

Я что-то не понял? Задача разбить на неповторяющиеся слагаемые. Вводим, например 19. 19=1+2+3+4+9. Всё! 9 не разбить уже, т.к 9 = 1+8 или 2+7 или 3+6 или 4+5.
В count'e количество слагаемых.
Зачем динамика? о_О

[LeBron]

Сообщение от eoln

Я что-то не понял? Задача разбить на неповторяющиеся слагаемые. Вводим, например 19. 19=1+2+3+4+9. Всё! 9 не разбить уже, т.к 9 = 1+8 или 2+7 или 3+6 или 4+5.
В count'e количество слагаемых.
Зачем динамика? о_О

Если речь идет именно о задаче, то

p1r2o3
выводить количество. n может быть от 5ти до 500

p1r2o3
про разбиения

Выводить количество - количество чего? Разбиений, как я понимаю.

И задача не про разбиение, а про разбиения, следовательно, от нас требуется не розбить, а найти количество всех.

Согласен, если бы "задача" была именно в выводе одного произвольного разбиения - Ваше решение верное, к нему особых претензий нету. Только тогда это назвать задачей трудновато, так как это кодинговое упражнение. И придумать "формулу" тоже трудно.