Задача лестницы

У маленького мальчика есть набор из N кубиков (5 ≤ N ≤ 500). Из этих кубиков можно сложить различные лестницы. Лестницы имеют ступени различного размера, следующие в порядке возрастания этого размера (обратите особое внимание на то, что лестница не может иметь две одинаковые ступени). Каждая лестница должна иметь минимум две ступени, и каждая ступень должна состоять минимум из одного кубика.

Найдите число Q различных лестниц, которые маленький мальчик может построить ровно из N кубиков.
Исходные данные
Число N
Результат
Число Q

0

http://acm.timus.ru/problem.aspx?space=1&num=1017
Хоть задача и не очень сложная, но врят ли кто-то будет здесь скрипеть мозгами, чтобы вам ее решить

0

Сообщение от ya_noob http://acm.timus.ru/problem.aspx?space=1&num=1017 Хоть задача и не очень сложная, но врят ли кто-то будет здесь скрипеть мозгами, чтобы вам ее решить

что вы хотели этим сказать я там ее и нашел

0

to many bukv. Давайте сами с начала мозги напрягите и попытку решить покажите, а дальше будем разбираться, с тем, что не получается...

0

я понимаю условие но я не могу придумать как её решить( подскажите пожалуйста хотя б направление алгоритма

0

Готово. Только это прекальк чистой воды.
С динамическим программированием я тоже решил и получил AC, но не покажу, догадайся сам.

#include <iostream>

using namespace std;

int main()
{
unsigned long long a[ 501 ] = {
0,0,0,0,0,2,3,4,5,7,9,11,14,17,21,26,31, 37,45,53,63,75,88,103,
121,141,164,191,221,255,295,339,389,447, 511,584,667,759,863,981,
1112,1259,1425,1609,1815,2047,2303,2589, 2909,3263,3657,4096,4581,
5119,5717,6377,7107,7916,8807,9791,10879 ,12075,13393,14847,16443,
18199,20131,22249,24575,27129,29926,3299 1,36351,40025,44045,48445,
53249,58498,64233,70487,77311,84755,9286 3,101697,111321,121791,
133183,145577,159045,173681,189585,20684 7,225584,245919,267967,
291873,317787,345855,376255,409173,44479 2,483329,525015,570077,
618783,671417,728259,789639,855905,92740 5,1004543,1087743,1177437,
1274117,1378303,1490527,1611387,1741520, 1881577,2032289,2194431,
2368799,2556283,2757825,2974399,3207085, 3457026,3725409,4013543,
4322815,4654669,5010687,5392549,5802007, 6240973,6711479,7215643,
7755775,8334325,8953855,9617149,10327155 ,11086967,11899933,12769601,
13699698,14694243,15757501,16893951,1810 8417,19406015,20792119,22272511,
23853317,25540981,27342420,29264959,3131 6313,33504745,35839007,38328319,
40982539,43812109,46828031,50042055,5346 6623,57114843,61000703,65139007,
69545357,74236383,79229675,84543781,9019 8445,96214549,102614113,109420548,
116658615,124354421,132535701,141231779, 150473567,160293887,170727423,
181810743,193582641,206084095,219358314, 233451097,248410815,264288461,
281138047,299016607,317984255,338104629, 359444903,382075867,406072421,
431513601,458482687,487067745,517361669, 549462335,583473183,619503295,
657667583,698087423,740890785,786212445, 834194699,884987528,938748851,
995645335,1055852589,1119555487,11869490 55,1258238719,1333640709,
1413383025,1497705767,1586861605,1681116 851,1780751882,1886061683,
1997357055,2114965119,2239229959,2370513 985,2509198527,2655684607,
2810394453,2973772211,3146284869,3328423 935,3520706303,3723675325,
3937902687,4163989457,4402567323,4654300 705,4919887991,5200062975,
5495597247,5807301631,6136027873,6482671 321,6848172603,7233519618,
7639750521,8067955711,8519280127,8994926 601,9496158207,10024300889,
10580747263,11166959337,11784471547,1243 4895063,13119920927,13841323581,
14600965704,15400801855,16242882559,1712 9359743,18062490973,19044644145,
20078303619,21166075135,22310691191,2351 5017983,24782061069,26114971539,
27517053881,28991772485,30542758737,3217 3819903,33888946599,35692320959,
37588326641,39581557439,41676826623,4387 9178239,46193897031,48626519093,
51182844671,53868949521,56691197083,5965 6252986,62771098023,66043042087,
69479740553,73089209119,76879839743,8086 0419135,85040145749,89428647939,
94036004867,98872765937,103949971455,109 279176297,114872472063,120742510606,
126902530815,133366383847,140148559929,1 47264218617,154729217535,162560142889,
170774343641,179389964241,188425979303,1 97902232211,207839472389,218259394655,
229184682869,240639052285,252647294207,2 65235325351,278430235903,292260340223,
306755232573,321945841663,337864488191,3 54544947721,372022512607,390334057171,
409518108689,429614917631,450666531449,4 72716874731,495811828758,519999315039,
545329385791,571854313989,599628687917,6 28709513215,659156314787,691031243769,
724399192575,759327910199,795888123109,8 34153664939,874201606889,916112394269,
959969992703,1005862035460,1053879977631 ,1104119260917,1156679479969,
1211664556453,1269182924647,132934771918 9,1392276971519,1458093818815,
1526926715867,1598909656577,167418240914 7,1752890755071,1835186738751,
1921228932215,2011182704477,210522050277 1,2203522150409,2306275150209,
2413675001277,2525925533945,264323925148 7,2765837686783,2893951778821,
3027822257407,3167700044479,331384667724 7,3466534741117,3626048321047,
3792683476991,3966748730793,414856557365 8,4338469000205,4536808055807,
4743946406975,4960262940967,518615238086 3,5422025926435,5668311927091,
5925456572863,6193924614093,647420011647 9,6766787237063,7072211032063,
7391018303853,7723778471935,807108447944 3,8433553742946,8811829129613,
9206579974149,9618503143423,100483241324 43,10496798204735,10964711585279,
11452882689343,11962163400705,1249344040 7999,13047636581997,13625712407807,
14228667481437,14857542052793,1551341862 9883,16197423654281,16910729229127,
17654554915429,18430169607103,1923889346 5515,20082099930207,20961217816575,
21877733480959,22833193070487,2382920486 9147,24867441720077,25949643542055,
27077619952639,28253252977151,2947849986 2527,30755396009351,32086058000383,
33472686745953,34917570760096,3642308954 5253,37991717107135,39626025614145,
41328689178999,43102487785005,4495031137 2459,46875164062333,48880168540671,
50968570620479,53143743957459,5540919494 4511,57768567802879,60225649845545,
62784376939519,65448839185791,6822328679 2199,71112136167456,74119976256079,
77251575089317,80511886581727,8390605759 4563,87439435240797,91117574462853,
94946245905983,98931444061527,1030793957 13069,107396568710143,
111889681043071,116565710254335,12143190 3212543,126495786222431,
131765175508647,137248188100781,14295325 3093375,148889123320639,
155064887475475,161489982646591,16817420 7315549,175127734845951,
182361127438193,189885350594523,19771178 8129023,205852257695743,
214319026883033,223124829910883,23228288 4904959,241806911798585,
251711150901901,262010382112695,27271994 4823231,283855758565429,
295434344369602,307472846894367,31998905 7373737,333001437357055,
346529143303467,360592052080639,37521078 7343945,390406746862529,
406202130845495,422619971245763,43968416 2112801,457419491051263,
475851671764997,495007377762303,51491427 7284171,535601069436937,
557097521610169,579434508247039,60264405 0950308,626759360010787,
651814877431175,677846321430325,70489073 2521791,732986521245023
};
int n;
cin >> n;
cout << a[ n ] << endl;

return 0;
}

	Комментарий модератора
	Внимание, модераторы раздела! По невыясненным на текущий момент причинам, обрамление приведенного кода в теги языка C++ приводит к ошибке сервера. Убедительная просьба до решения проблемы с постом ничего не делать. Благодарю за понимание.

Добавлено через 1 час 40 минут
Круто, сервак не справляется с моим кодом.
А почему после 60-го символа в строке появляется пробел? Ограничение на длину строки что-ли?

Добавлено через 4 минуты
тоесть на длину слова?

1

0

0

Сообщение от ya_noob Готово. Только это прекальк чистой воды. С динамическим программированием я тоже решил и получил AC, но не покажу, догадайся сам.

Да вы чего издеваетесь??? Я ж для этого тему создал! Я просто так сюда не прусь, я уже всю бошку сломал!!!

0

не надо так нервничать. я же намекнул на динамические программирование. если хотите помощи, покажите что уже сделали.

Добавлено через 8 минут
алгоритм то простой: надо перебрать все возможные комбинации кубиков (рекурсивно)

1

Сообщение от ya_noob не надо так нервничать. я же намекнул на динамические программирование. если хотите помощи, покажите что уже сделали. Добавлено через 8 минут алгоритм то простой: надо перебрать все возможные комбинации кубиков (рекурсивно)

ну я вообще не могу придумать идею а рекурсивно я не понимаю можете на цыклах показать? И неужели попроще не выйдет?

Добавлено через 14 секунд
формула там какая?

0

Сообщение от HardLogin а рекурсивно я не понимаю можете на цыклах показать

такую рекурсию просто так в циклы не переделать (дополнительно нужно использовать стек).

Перед решением таких задач нужно иметь определенные знания по алгоритмам и структурам данных. Если решение этой задачи стало для вас делом чести, то я рекомендую вам почитать про рекурсию, деревья и динамическое программирование. Мне очень понравилось описание этих вещей у Седжвика в главе 5, минимум формул и с картинками.

0

ну хорошо почитаем, а можете в таком случае на рекурсии показать?

Добавлено через 23 часа 23 минуты
ну и

0