1 Востаннє редагувалося Q-bart (29.05.2018 09:28:04)

Тема: Класика студіка

Сесія.

Ось така таска.

Нехай всього Зенику потрiбно пiднятися на N сходинок. За один крок вiн може подолати довiльну кiлькiсть сходинок вiд 1 до N. Назвемо довжиною кроку кiлькiсть сходинок, подоланих за цей крок. У Зеника є правило: рiзниця мiж найдовшим та найкоротшим кроком неможе перевищувати K. Потрiбно знайти скiлькома способами можна подолати N сходинок так,щоб правило Зеника виконувалося.

Допоможіть з алгоритмом? Динаміче програмування

Поки думав таке:

кількість можливих способів для N = a[n-1] + a[n-2] + ... a[n-n]
Це закодив.

Але далі -> треба якось перевіряти максимальну і мінімальну довжину кроку.

Подякували: FakiNyan, ostap34PHP2

2

Re: Класика студіка

Трохи незрозуміло - там в умові N сходинок і крок від 1 до N? Чи все ж різні числа?

Перша думка: так само, але перебираєте для всіх варіантів (кроки від 1 до K+1, від 2 до K+2, ..., від N-K до N). Але не виходить, ми ж двічі порахуємо купу варіантів.

3

Re: Класика студіка

Які обмеження на значення N, K, час та пам'ять?

4

Re: Класика студіка

Так, саме так. Крок може бути N

5

Re: Класика студіка

А ось обмеження жорстокі. Обмеження
2 сек., 256 МіБ

6

Re: Класика студіка

Довжина кроків у вас вкладається у формулу арифметичної прогресії, кінцева сума якої задана. Залишається перебрати усі можливі комбінації решти членів формули.

7

Re: Класика студіка

Хоча якщо різниця між кроками може бути різною... Цей момент треба уточнити.

8

Re: Класика студіка

Q-bart написав:

А ось обмеження жорстокі. Обмеження
2 сек., 256 МіБ

А на N та K? Бо якщо N=2^32, то 256МіБ і так не вистачить.

9

Re: Класика студіка

1≤ N, K ≤100

10

Re: Класика студіка

koala написав:

Трохи незрозуміло - там в умові N сходинок і крок від 1 до N? Чи все ж різні числа?

Перша думка: так само, але перебираєте для всіх варіантів (кроки від 1 до K+1, від 2 до K+2, ..., від N-K до N). Але не виходить, ми ж двічі порахуємо купу варіантів.

Кешування?

11 Востаннє редагувалося koala (29.05.2018 12:06:47)

Re: Класика студіка

Ні, я про те, що шлях, де всі кроки по 3, потрапляє і в область 1:3, і в 2:3, і в 3:5.
Наступна ідея. Оскільки N і K маленькі, робимо для кожної сходинки замість одного числа A[ i ] - таблицю по мінімальних-максимальних кроках:
Сходинка I
Кількість шляхів сюди із кроком:
Min\Max 1  2  3  4  5   6  ... N
1           1  3  ...
2           -   1  ...
3           -   -  ...

На кожному наступному кроці, відповідно, заповнюємо всю таблицю по всіх можливих шляхах.
Очевидно, що нижня половина таблиці (Max<Min) та верхній трикутник (Max-Min>K) нам не потрібні.
Також для сходинки i не потрібна частина з Max>i.
Витрати пам'яті O(k*n^2) < 100^3 = 10^6, в 256МіБ вкладаємося; час, відповідно - O(k*n^3) < 100^4 = 10^8, тут жорсткіше, але маємо в 2с вкластися, всі операції - додавання, а у нас тільки половину таблиць заповнювати.
Детальніше розжовувати?

12

Re: Класика студіка

Поясніть ще раз  дурному.

Ми перебираємо всі можливі варіанти. Як?

Два: результат цього треба занести в матрицю. так?

13

Re: Класика студіка

Ні.
Ще раз, як іде рішення, якщо у нас немає "правила Зеника": ми для кожної сходинки створюємо окрему змінну (тобто в результаті виходить одновимірний масив), який по одному кроку заповнюємо:
на першу сходинку можна потрапити 1 способом,
на другу - 2 (з землі і 1-ї сходинки), 
на третю - 4 (з землі, 1-ї сходинки і 2-ї сходинки з її 2-ма шляхами)
і т.д.
А тепер нам треба для кожної сходинки створити не одну змінну, а двовимірний масив, і заповнювати його аналогічно:
на i-у сходинку можна потрапити з землі кроком в i, це комірка A[ i ][ i ][ i ] (індекси: номер сходинки, мінімум, максимум); можна потрапити зі сходинки 1 кроком в i-1, це комірка A[ i ][1][i-1] і т.д.
Якщо ми розглядаємо, скільки існує способів переходу зі сходинки j на сходинку i, то нам доведеться для кожної комірки сходинки j (A[j][minj][maxj], де minj та maxj - змінні циклів, якими ми ітеруємо по таблиці сходинки j) подивитися, куди потрапляє нове значення i-j - якщо воно вписується в minj...maxj, то значення додається до A[ i ][minj][maxj]; якщо не вписується - то, наприклад, якщо більше за maxj, це буде додано до A[ i ][minj][i-j].

Подякували: Q-bart1

14

Re: Класика студіка

Треба починати з кінця.
З останньої сходинки можна зробити тільки один можливий крок.
Записуємо там 1
З перед останньої можна сходити на останню або в кінець. 1*1+1 = 2
З n-2 -> 1*2+1*1+1 = 4
Тільки треба буде прогнати це для різних мінімальних кроків, бо в нас є К.

Доречі питання, чи можуть кроки закінчуватись в N+m чи обо’язково останній крок має закінчуватись в N?

Подякували: Q-bart1

15

Re: Класика студіка

Vo_Vik написав:

Тільки треба буде прогнати це для різних мінімальних кроків, бо в нас є К.

Так це ж найцікавіше.

Vo_Vik написав:

чи можуть кроки закінчуватись в N+m чи обо’язково останній крок має закінчуватись в N?

В умові написано "скiлькома способами можна подолати N сходинок", а не "щонайменше N сходинок".

16 Востаннє редагувалося Vo_Vik (29.05.2018 15:01:19)

Re: Класика студіка

koala написав:
Vo_Vik написав:

Тільки треба буде прогнати це для різних мінімальних кроків, бо в нас є К.

Так це ж найцікавіше.

Vo_Vik написав:

чи можуть кроки закінчуватись в N+m чи обо’язково останній крок має закінчуватись в N?

В умові написано "скiлькома способами можна подолати N сходинок", а не "щонайменше N сходинок".

Ну так там просто ще один цикл. 0<=i<=N
min  = i, max = i+K
і в тих сумах не враховувати ті позиції які виходять за мінмакс.

Складність алгоритму десь O^3 виходить.
От чи можна за менший час, оце питання.

А про що найменше. Ну якщо подолано N+1 сходинка, то очевидно що N подолано.
От якби там було скількома способами можна попасти на сходинку N, це була би інша історія.

Подякували: Q-bart1

17

Re: Класика студіка

Ok, n=4, k=1. Без "правила Зеника" відповідь 8: (1,1,1,1), (1,1,2), (1,2,1), (2,2), (2,1,1), (1,3), (3,1), (4). Із ним - 6, бо (1,3) і (3,1) не проходять. Додаємо ваш цикл - треба врахувати всі шляхи з min,max = [1,2], [2,3] і [3,4]:
[1,2]: (1,1,1,1), (1,1,2), (1,2,1), (2,2), (2,1,1)
[2,3]: (2,2)
[3,4]: (4)
Разом - 7 шляхів. Чому? Бо шлях (2,2) входить у діапазони і [1,2], і [2,3].

Подякували: Q-bart1

18

Re: Класика студіка

Про "подоланість" сходинки - цікаве питання. Погоджуюся, що можна було б краще сформулювати; але в умові сказано, що треба піднятися на N сходинок. Якщо вам треба піднятися на 3-й поверх, а ви піднялися на 8-й - то вас результат не влаштує, хоча суто формально ви можете посперечатися, що ви піднялися не лише на 3-й, а й на 4-й, 5-й і т.д. поверхи; гадаю, тут так само - треба піднятися на рівно N, а не щонайменше N сходинок.

Подякували: Q-bart1

19

Re: Класика студіка

Тобто розв’язуємо примаючи умову, що треба опинитись на сходинці N.

20

Re: Класика студіка

Гм, якщо відкинути умову про К, то там взагалі проста формула виходить 2^(N-1)
Треба просто дізнатись як порахувати ті шляхи де різниця між кроками більша К і тоді їх відняти.