192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
1

Сколько различных способов есть у зайца добраться до вершины лестницы?

25.07.2016, 14:56. Показов 24366. Ответов 20
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы. К - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.
Например:
HTML5
1
2
3
1    3  -   1
2    7  -   21
3    10  -   274
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.07.2016, 14:56
Ответы с готовыми решениями:

Сколько существует способов добраться из исходной точки до правого верхнего угла
Имеется клетчатое поле размером m × n. В левом нижнем углу сидит черепашка. Она умеет ходить только...

Сколько различных путей существует добраться из левого верхнего угла в правый нижний?
Всем привет! Недавно решал одну любопытную задачу, но к сожалению не смог решить на 100%. Вот...

Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А....

Определить сколько существует различных способов выбрать три текста из имеющихся так, чтобы их эпичность возрастала
Невероятно, но Макса пригласили на Versus Battle — соревнование среди рэп-исполнителей, ставшее в...

20
Заблокирован
25.07.2016, 15:47 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void    jump(int k,int n,int nj,int l,int *aj,int&njmp)
{
    for(int i=1; i<=k && l+i<=n; i++)
    {
        aj[nj]=i;
        if(l+i==n)
        {
            for(int j=0; j<=nj; j++) cout<<(j?"+":"")<<aj[j];
            cout<<endl;
            njmp++;
            return;
        }
        jump(k,n,nj+1,l+i,aj,njmp);
    }
}
void main(int argc,char* argv[])
{
    setlocale(LC_ALL,"Rus");
    int k,n;
    cout<<"K и N через пробел:";
    cin>>k>>n;
    int *aj=new int[n];
    int njmp=0;
    jump(k,n,0,0,aj,njmp);
    cout<<njmp<<endl;
    delete[] aj;
    system("pause");
    return;
}
1
4819 / 2284 / 287
Регистрация: 01.03.2013
Сообщений: 5,961
Записей в блоге: 29
25.07.2016, 21:09 3
Тупо в лоб, экспоненциальная рекурсия без динамики и мемоизации:
C++
1
2
3
4
5
6
7
int f(int, int);
 
int l(int k, int n, int i) {return i ? f(k,n-i) + l(k,n,i-1) : n<=k;}
 
int f(int k, int n) {return n<=0 ? 0 : l(k,n,k);}
 
int main() {cout<<f(3,4)<<'\n'<<f(1,3)<<'\n'<<f(2,7)<<'\n'<<f(3,10);}
3
1647 / 1095 / 488
Регистрация: 17.07.2012
Сообщений: 5,356
25.07.2016, 21:51 4
Это же классическая задача динамического программирования. a[i] = сумма предыдущих K. Только автор не написал ограничений, а ограничения там такие, что еще придется писать длинную арифметику.

Не по теме:

На Питоне зато легко решается.

Python
1
2
3
4
5
k, n = map(int, input().split())
a = [1, 1]
for i in range(2, n + 1):
    a.append(sum(a[len(a) - min(k, len(a)):]))
print(a[n])

2
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
25.07.2016, 22:14  [ТС] 5
Новичок
длинная арифметика присутствует! "Записаны два натуральных числа K и N (1 ≤ K ≤ N ≤ 300)".
MansMI

Да знаю я. Но я не понял что и как использовать (сочетание, перестановка, сочетания)??

Добавлено через 1 минуту
Вам то легко говорить! А я только учусь, мне главное смысл объясните, алгоритм решения!
0
4819 / 2284 / 287
Регистрация: 01.03.2013
Сообщений: 5,961
Записей в блоге: 29
25.07.2016, 22:50 6
берем "самый крутой язык" (С), пишем
Haskell
1
2
3
f (k,n) | n<=0      = Left 0
        | otherwise = Right (zip (repeat k) [n-k..n-1], incif.sum)
        where incif x | n<=k = x + 1::Integer | otherwise = x
потом пишем мемоизированное вычисление любой примитивно-рекурсивной функции, скармливаем это ядро мемоизатору - и получаем обычную функцию :
Код
f 300 300 =
1018517988167243043134222844204689080525734196832968125318070224677190649881668353091698688
1
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
25.07.2016, 23:06 7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
///////////////////////////////////////////////////////////////////////////////
//4.
///////////////////////////////////////////////////////////////////////////////
//Зайчик
//(Время: 1 сек. Память: 16 Мб Сложность: 55%)
 
//В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно,
//директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик
//может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет
//определенное количество ступенек N. Заяц может одним прыжком преодолеть
//не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый
//путь к вершине лестницы. Директору любопытно, сколько различных способов есть
//у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите
//директору написать программу, которая поможет вычислить это количество.
//Например, если K=3 и N=4, то существуют следующие маршруты:
//1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях
//у зайца всего 7 различных маршрутов добраться до вершины лестницы.
 
//Входные данные
 
//В единственной строке входного файла INPUT.TXT записаны два натуральных
//числа K и N (1 ≤ K ≤ N ≤ 300). К - максимальное количество ступенек, которое
//может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.
//Выходные данные
 
//В единственную строку выходного файла OUTPUT.TXT нужно вывести количество
//возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы
//без ведущих нулей.
 
//Примеры
//№     INPUT.TXT OUTPUT.TXT
//1     1   3       1
//2     2   7       21
//3     3   10      274
///////////////////////////////////////////////////////////////////////////////
#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::vector     < int   >   T_big_num_val;
///////////////////////////////////////////////////////////////////////////////
class   T_big_num
{
    //-------------------------------------------------------------------------
    static  const   int     DIG_MIN     =   0;
    static  const   int     DIG_MAX     =   9;
    //-------------------------------------------------------------------------
    T_big_num_val   big_num_val_;
    //-------------------------------------------------------------------------
public:
    //-------------------------------------------------------------------------
    T_big_num( int  val     =   0 )
        :
        big_num_val_( 1, val )
    {}
    //-------------------------------------------------------------------------
    T_big_num   &   operator*=  ( int   R )
    {
        for( auto   &   dig     :   big_num_val_ )
        {
            dig     *=  R;
        }
 
        normalize();
        return  *this;
    }
    //-------------------------------------------------------------------------
    T_big_num   &   operator-=  ( T_big_num     const   &   R )
    {
        for( size_t  i{}; i < R.big_num_val_.size(); ++i )
        {
            big_num_val_[i]     -=  R.big_num_val_[i];
        }
 
        normalize();
        return  *this;
    }
    //-------------------------------------------------------------------------
private:
    //-------------------------------------------------------------------------
    void    normalize()
    {
        for( size_t  i{}; i < big_num_val_.size(); ++i )
        {
            while   (
                            big_num_val_[i]
                        <   DIG_MIN
                    )
            {
                big_num_val_    [ i     ]   +=  10;
                --big_num_val_  [ i + 1 ] ;
            }//while
 
            while   (
                            big_num_val_[i]
                        >   DIG_MAX
                    )
            {
                big_num_val_[i]  -=  10;
 
                if  (
                        i   ==  big_num_val_.size()     -   1
                    )
                {
                    big_num_val_.push_back(0);
                }
 
                ++big_num_val_[ i + 1 ];
            }//while
        }//for
 
        while   (
                        big_num_val_.size()     >   1
                    &&  big_num_val_.back()     ==  0
                )
        {
            big_num_val_.pop_back();
        }
    }
    //-------------------------------------------------------------------------
    friend
    std::ostream    &   operator<<
        (
            std::ostream            &   ostr,
            T_big_num       const   &   big_num
        )
    {
        std::copy
            (
                big_num.big_num_val_.rbegin     (),
                big_num.big_num_val_.rend       (),
                std::ostream_iterator<int>      ( ostr )
            );
 
        return  ostr;
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
typedef std::vector     < T_big_num     >   T_route_options_counts;
///////////////////////////////////////////////////////////////////////////////
T_big_num     route_options_total
    (
        int     K_jump_max,
        int     N_ladder_size
    )
{
    T_route_options_counts  route_options_counts{1, 1};
 
    int                     ind_prev    =       int(    route_options_counts.size()    )
                                            -   1
                                            -   K_jump_max;
 
    while   (
                    int(    route_options_counts.size()    )
                <   N_ladder_size   +   1
            )
    {
        route_options_counts.emplace_back
            (
                route_options_counts.back()
            );
 
        route_options_counts.back()    *=  2;
 
        if  (
                ind_prev    >=  0
            )
        {
            route_options_counts.back()    -=  route_options_counts[ ind_prev ];
        }
 
        ++ind_prev;
    }//while
 
    return  route_options_counts.back();
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    int     K_jump_max      {};
    int     N_ladder_size   {};
 
    std::cin    >>  K_jump_max
                >>  N_ladder_size;
 
    std::cout   <<  route_options_total
                        (
                            K_jump_max,
                            N_ladder_size
                        )
 
                <<  std::endl;
}
1
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
26.07.2016, 10:16  [ТС] 8
Ребят Спасибо за ответы и коды присланные вами но мне хотелось бы понять смысл решения этой задачи. Через комбинаторику я что-то не понял! Ваши коды тоже не понял! Мне суть объясните плиззз.

Добавлено через 3 минуты
Цитата Сообщение от _Ivana Посмотреть сообщение
пишем мемоизированное вычисление любой примитивно-рекурсивной функции, скармливаем это ядро мемоизатору - и получаем обычную функцию
можете объяснить по человеческий что вы там наделали))) что это за функции такие? Они специально созданы именно для длинной арифметики?
0
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
26.07.2016, 10:39  [ТС] 9
Цитата Сообщение от Mr.X Посмотреть сообщение
См. мое решение, оно проходит на сайте.
Да оно проходит. Как это через динамику?

Добавлено через 5 минут
MansMI
Ваша задача тоже правильна но сайт не принимает её из-за отсутствие длиной арифметики
0
90 / 88 / 33
Регистрация: 20.07.2016
Сообщений: 403
26.07.2016, 10:48 10
Вот еще вариант решения:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <numeric>
#include <algorithm>
 
//==============================================================
int main ()
{
    size_t K = 3, N = 10;
 
    if (K == 1)
        std::cout << 1 << std::endl;
    else if (N <= K)
        std::cout << std::pow(2, N - 1) << std::endl;
    else
    {
        size_t* arr = new size_t[K];
        arr[0] = 1;
 
        for (size_t j = 1; j != K; ++j)
            arr[j] = 2 * arr[j - 1];
        
        for (size_t j = 0; j != N - K; ++j)
        {
            size_t next = std::accumulate(&arr[0], &arr[K], 0);
            std::rotate(&arr[0], &arr[1], &arr[K]);
            arr[K - 1] = next;
        }
 
        std::cout << arr[K - 1] << std::endl;
 
        delete[] arr;
    }
 
 
    return 0;
}
Цитата Сообщение от no swear Посмотреть сообщение
но мне хотелось бы понять смысл решения этой задачи
есть несколько способов решить эту задачу... используйте гугл, на многих сайтах довольно внятно объясняют "что? как? и почему?"... на самом деле ничего сложного, немножко мат индукции, немножко чисел Фибоначчи и вуаля - задача решена... удачи)
3
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
26.07.2016, 11:26 11
Лучший ответ Сообщение было отмечено no swear как решение

Решение

Цитата Сообщение от no swear Посмотреть сообщение
Да оно проходит. Как это через динамику?
Пусть fi – количество вариантов на лестнице с i ступеньками.
Очевидно, что f0 = f1 = 1.
Пусть k – это максимальный прыжок.
Если первый прыжок равен 1, то на оставшихся ступеньках количество вариантов равно f(i - 1),
если 2, то f(i - 2),
если k, то f(i - k),
т.е. получаем рекуррентную формулу
f(i) = f(i - 1) + f(i - 2) + … + f(i - k).********************(1)
Если применять ее непосредственно, то многократно будут вычисляться перекрещивающиеся подзадачи, поэтому надо применить динамическое программирование, т.е. вычислить их один раз и сложить в вектор.
В нем два первых элемента единицы, а каждый следующий равен сумме предыдущих k, или всех предыдущих, если их меньше k.
Из формулы (1) имеем
f(i + 1) = f(i) + f(i - 1) + … + f(i – k + 1)****************(2)
т.е.
f(i + 1) = f(i) + f(i - 1) + … + f(i – (k - 1))***************(3)
откуда, согласно (1), получим:
f(i + 1) = f(i) + f(i) – f(i – k)
т.е.
f(i + 1) = 2 * f(i) – f(i – k)
или
f(i) = 2 * f(i - 1) – f(i – k - 1).
Разумеется, второй член вычитаем, если его индекс неотрицательный.
По этой формуле заполняем вектор, пока не дойдем до нужного нам индекса, равного заданной длине N лестницы. Значение по этому индексу и будет ответом для заданных N и k.
5
245 / 139 / 53
Регистрация: 23.11.2015
Сообщений: 394
26.07.2016, 11:41 12
вот как школьники(и я) бы решали эту задачу. и вот это действительно в лоб.
будет падать на длинной арифметике.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
// 1 <= K <= N <= 300
bool getKN(int& K, int& N)
{
    std::cin >> K >> N;
    if (1 <= K && K <= N && N <= 300)
        return true;
    return false;
}
 
int getNumberOfCombs(int K, int N)
{
    std::vector<unsigned> combs(N + 1);
    for (auto& t : combs) t = 0;
    std::fill(combs.begin(), combs.end(), 0);
    combs[0] = 1;
    for (int i = 1; i < N + 1; ++i)
        for (int j = i - 1; j >= (i - K) && j >= 0; --j)
            combs[i] += combs[j];
    return combs[N];
}
 
int main()
{
    int K = 3, N = 10;
    if (!getKN(K, N))
        return 1;
    std::cout << getNumberOfCombs(K, N) << std::endl;
    return 0;
}
Добавлено через 1 минуту
https://www.cyberforum.ru/cgi-bin/latex.cgi?f(n)=f(n-1)+f(n-2)+...+f(n-k)
2
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
26.07.2016, 11:48  [ТС] 13
Mr.X,
СПАСИБО большое, и всем остальным тоже спасибо за ответы!!! Теперь всё стало окончательно ясно
0
245 / 139 / 53
Регистрация: 23.11.2015
Сообщений: 394
26.07.2016, 11:48 14
блин, хотел algorithm заголовок выбросить, fill переписал, но не выкинулась - 16 строчка не нужна
1
Заблокирован
26.07.2016, 11:53 15
у а кто то обсчитал K=300 N=300 (вроде как 1<=K<=N<=300)?
при 30 30 ~0.6G вариантов, интересен же ответ
1
90 / 88 / 33
Регистрация: 20.07.2016
Сообщений: 403
26.07.2016, 12:13 16
Цитата Сообщение от MansMI Посмотреть сообщение
у а кто то обсчитал K=300 N=300 (вроде как 1<=K<=N<=300)?
для K = 300, N = 300 ответ 2^299
1
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
26.07.2016, 15:37 17
Цитата Сообщение от MansMI Посмотреть сообщение
у а кто то обсчитал K=300 N=300 (вроде как 1<=K<=N<=300)?
при 30 30 ~0.6G вариантов, интересен же ответ
Цитата Сообщение от _Ivana Посмотреть сообщение
10185179881672430431342228442046890805257341968329681253180702246771906498816683 53091698688
А мою программу что мешает запустить?
10000 10000
99753155844037919244187108134179254191174841594309622742600447492647194151109733
15959980842018097298949665564711604562135778245674706890558796892966048161978927
86502339689726338262327563302994776027504345909665577125430423030905234275453743
30448124440452449474190046269708166289253107841547369512784561940326125483219372
20523379935813492726611434269080847157887814820381418440380366114267545820738091
97819072948473194970542048026813391053231071366669701826278282476530157134011748
47001679671583257296488866398328878030862910157039970990898036891228418811400186
51442743625950417232290727325278964800707416960807867294069628547689884559638900
41347886783722206153100937891816275136416189463535518690143319651571406662070081
20978358452870307098271711623194006244280736526037159961298058981250654964301208
54170403802966160080634246144248127920656422030768369475743557128157555544872757
10165691010146582047879823237800520292292078303602248143350825753096031550209321
11379543354502873032089284759557280275341256252030037599211309490296185590272223
94036453197621274169610991353702236581188380423306516889353019901706598566746827
31135028158496872775412089048640549164565720178593876238425492863846896321661079
96999384433304041844189190138216413875861368287863723920561471948669054308037116
26645987406560098802089140982848737949082265629217067979931392065064092703141738
32454434526052379044130791198099288506120352216529153793451965980230170248657829
16043360529566504518764117077698726971988576287276452551061554736608053767374128
70387636993174149249170378468977823319310937284749639508286051850682216567908607
15589569911149192292366722013548209142550253646387418227528931725055042649390619
47369643497704171730794035219795594929075728895885718098493640657297418916010407
37491085929005694535614125452913408718110288737960708826857843862807452291452496
23051431504076779165406505099383792811717176947770458781170042244376308132178432
44167597318601886466200472281234616271752003390136369188776882033634493181205187
45705483359278525379549050123394940089135962976690641210977014151379704224477507
33833419484899844312081815668819695168672790070381837093885552769211286974955509
32341098482908257425652471111849738573815345777341088414381001813886288618906826
65805598405640396334740943600649321830384275819930267301148935778758973692623184
72346154394713297410850402556016118274814408451786956068416919679587820936692525
54851358069577197954957990773272086681558284680155611249689849996133908661790115
55931322287649567879087504099919618142307624940544480116122181086885809043178507
73424202931116489642693781174327822026848131100948178551440618078375627166915163
50145488343252842785787527583637594495970648556688450749580906575857720038643252
86594778725460165092652423556909157703662026659519231042018210881851955775319894
50037142683609814045173898726666023418439793429011897610931456004037140977565897
40788122241492592307548524440136373607873440657973752048660575402490952279017084
13474893570658031605343195755840887152396298354688
1
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
26.07.2016, 18:16  [ТС] 18
Цитата Сообщение от Mr.X Посмотреть сообщение
А мою программу что мешает запустить?
Не знаю может дело в компиляторах? Ваш код работает но когда задаю большие числа он просто не выводит ответ.

Добавлено через 17 минут
А нет работает! Просто приходится очень долго ждать если задам большие числа. Например с 25 25 мне приходится ждать ответа секунд 2, если ввести 30 30 через примерно 6 секунд появится ответ и т.д.. А если задам 100 100 так вообще минут 10 по-моему придётся ждать ответа
0
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
27.07.2016, 07:41 19
Цитата Сообщение от no swear Посмотреть сообщение
Не знаю может дело в компиляторах? Ваш код работает но когда задаю большие числа он просто не выводит ответ.
Добавлено через 17 минут
А нет работает! Просто приходится очень долго ждать если задам большие числа. Например с 25 25 мне приходится ждать ответа секунд 2, если ввести 30 30 через примерно 6 секунд появится ответ и т.д.. А если задам 100 100 так вообще минут 10 по-моему придётся ждать ответа
В релизе компилируйте.
1
0 / 0 / 0
Регистрация: 09.02.2019
Сообщений: 4
28.11.2019, 11:32 20
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
int main ()
{
 
    size_t k , n ;
    cin >> k >> n ;
 
    if (k == 1)
        cout << 1 << endl;
    else
        if (n <= k)
            cout << pow(2, n - 1) << endl;
    else
    {
        size_t * arr = new size_t[k] ;
        arr[0] = 1 ;
 
        for (size_t j = 1 ; j != k ; ++j)
            arr[j] = 2 * arr[j - 1];
 
        for (size_t j = 0 ; j != n - k ; ++j)
        {
            size_t next = accumulate(&arr[0], &arr[k], 0);
            rotate(&arr[0], &arr[1], &arr[k]);
            arr[k - 1] = next;
        }
 
        cout << arr[k - 1] << endl;
 
    }
 
 
    return 0;
}
Добавлено через 1 минуту
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
int main ()
{
 
    size_t k , n ;
    cin >> k >> n ;
 
    if (k == 1)
        cout << 1 << endl;
    else
        if (n <= k)
            cout << pow(2, n - 1) << endl;
    else
    {
        size_t * arr = new size_t[k] ;
        arr[0] = 1 ;
 
        for (size_t j = 1 ; j != k ; ++j)
            arr[j] = 2 * arr[j - 1];
 
        for (size_t j = 0 ; j != n - k ; ++j)
        {
            size_t next = accumulate(&arr[0], &arr[k], 0);
            rotate(&arr[0], &arr[1], &arr[k]);
            arr[k - 1] = next;
        }
 
        cout << arr[k - 1] << endl;
 
    }
 
 
    return 0;
}
9 тест ответ не правильный(
0
28.11.2019, 11:32
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.11.2019, 11:32
Помогаю со студенческими работами здесь

Сколько есть способов выплатить сумму
В Эстонии в обращении находятся 1,2,5,10,25,50,100 и 500 - кроновые купюры. Написать программу,...

сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N
Доброго времени суток, уважаемые форумчане! Есть задача: В нашем зоопарке появился заяц. Его...

Cколько различных способов есть у зайца добраться до вершины лестницы
1. В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор...

Сколько различных способов есть при выборе карт?
Из колоды 52 карт (13х4 масти) выбирается 7 карт. Сколько различных способов существует выбрать 7...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru