zadacha

[Boyov]

Zdarova lyudi,

Goda 2 nazad na olimpiade po informatike mne popalas' sleduyuschaya zadacha:

Dano chislo N (N<=200) nujno nayti skol'kimi sposobami eto chislo mojno predstavit' v vide summi nepovtoryayushixsya natural'nix chisel.

Naprimer dlya N=10 eto chishlo budet 10.

1.10=10+0
2.10=1+9
3.10=8+2
4.10=7+3
5.10=6+4
6.10=1+2+7
7.10=1+3+6
8.10=1+4+5
9.10=2+3+5
10.10=1+2+3+4

po moemu vse.

Koroche eta zadacha 'legko :) ' reshaetsya esil delaesh sami naitupeishi perebor (tipa 26(!!!) vlojennix ciklov), no estestvenno eto reshenie nel'zya schitat' "xelqin motik".

Kakie u vas budut idei ?

Spasibo

Boyov

[di0phantus]

xorsho bi utochnit' odnu vazhuyu detal'...
predlogaetsya pokazat' vse resheniaya, ili prosto vivesti chislo vsevozmozhnix predstavlenii`?

[Griffon2-7]

Если учитывается вариант 10+0=10, то почему не учитываются остальныер варианты, где фигурирует 0?

Например: 0+1+2+3+4=10

Может 0 вообще не надо учитывать? Число вариантов уменьшится в 2 раза :D

[Boyov]

Originally posted by di0phantus:
xorsho bi utochnit' odnu vazhuyu detal'...
predlogaetsya pokazat' vse resheniaya, ili prosto vivesti chislo vsevozmozhnix predstavlenii`?nujno prosto vichislit' kolichestvo

Boyov

[di0phantus]

int getCount (int number){
return getIt(number, number);
}

int getIt(int number, int pieces){
if (pieces == number)
return 1;
return getForEveryPieces(number, pieces) + getIt(number, pieces-1);
}a eto funkciaya vozvrashyaet reshenie zadachi s myachami, po kombinatorike
formulu ne pomnyu nado vivesti. zadacha takaya.
SUM(x[i]) = N, i = 1, ..., k.
x[i] >= a; pri lyubom i.
(a=1 eto nash sluchay)no eto reshenie vklyuchaet takzhe povtori, tipa
primer N=5, k=3, a=1
1+2+2
2+1+2
2+2+1tak chto nado otvet razdelit na k!.
int getForEveryPieces (int number, int pieces){
}naverno tak.

[Grigor]

Можно так.
Здесь counts[i][j] - количество вариантов разложений числа i, в которых числа меньше j.
Используется следующее рекуррентное соотношение counts[i][j] = counts[i][j-1] + counts[i - j + 1][j-1]


#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> intVec;

int main()
{
int n;
cin >> n;

vector <intVec> counts;
counts.resize(n+1);
for (int i = 0; i < n + 1; i++)
counts[i].resize(n + 2);

for (int i = 1; i < n + 1; i++)
counts[i][1] = 0;
for (int i = 2; i < n + 2; i++)
counts[1][i] = 1;

for (int i = 2; i <= n; i++)
for (int j = 2; j <= n+1; j++)
if (j > i)
counts[i][j] = counts[i][i] + 1;
else
counts[i][j] = counts[i][j-1] + counts[i-j+1][j-1];

cout << counts[n][n+1] << endl;

return 0;
}
Временная сложность этого алгоритма O(N²), что при N <= 200 приемлимо.