непонятность в условии и верен ли алгоритм

@cotypan · Регистрация: 18.03.2015

Author24 — интернет-сервис помощи студентам

Последовательность из l целых чисел b1, b2, ..., bl (1 ≤ b1 ≤ b2 ≤ ... ≤ bl ≤ n) называется хорошей, если каждое число делит без остатка следующее число в последовательности. Более формально, bi делит bi+1 для всех i (1 ≤ i ≤ l - 1). Вам даны n и k, найдите количество хороших последовательностей длины k.
Формат входных данных: В первой строке записаны два целых числа через пробел n,k (1 ≤ n, k ≤50).
Формат выходных данных: Выведите единственное целое число — количество хороших последовательностей длины k
Примеры
вводим 3 2. Получаем 5.
вводим 6 4 Получаем 39
вводим 2 1 Получаем 2
Примечание В первом примере хорошие последовательности такие: [1,1],[2,2],[3,3],[1,2],[1,3].

То есть как я понимаю нужно сгененировать все подпоследовательности последовательность n длины k. Затем среди этих подпоследовательностей отобрать те что удовлетворяют условию хорошей последовательности.
Например вводим 3 2.Получаем подполедоваетльности последовательности от 1 до 3 длины 2 :
11
12
13
21
22
23
31
32
33
Среди них отбираем хорошие последовательности: [1,1],[2,2],[3,3],[1,2],[1,3]. Их 5 штук.

@John Prick · 17.04.2015, 15:01

Ну этот алгоритм называется "в лоб". Возможно (и наверняка) есть более быстрые алгоритмы.

@_Ivana · 17.04.2015, 16:39

Хорошая задачка, решение в 3 строки

Haskell

1
2
3

taskrec n k = sum $ map (go k) [1..n] where
    go 1 _ = 1
    go p i = sum $ map (go $ p-1) [i,2*i..n]

Надо конечно добавить мемоизацию для нормальных аргументов. (1 ≤ n, k ≤50) это конечно баловство, в исходной задаче ограничения (1 ≤ n, k ≤ 2000) - http://codeforces.ru/problemset/problem/414/B

@cotypan · 17.04.2015, 17:41 **[ТС]**

_Ivana, Спасибо))Жаль Haskell не знаю...

@_Ivana · 17.04.2015, 18:13

Важен не язык а алгоритм. Хотя на этом форуме мало кто разделяет эту имхо очевидную и бесспорную точку зрения

Добавлено через 24 минуты
UPD решил исходную задачку с кодефорсес, а сюда вылажу кота, который не работает на больших числах кодефорсеса по причине отсутствия оптимизации хвостовой рекурсии при настройках компилятора по-умолчанию. Но мне такие бесцикловые и малоифовые коты все равно больше нравятся

C++

typedef unsigned long long int ull; ull dp [2005][2005], go(int, int, int);
ull loop(int p, int i, int j, int n, ull a) {return j<=n ? loop(p, i, j+i, n, a+go(p-1, j, n)) : a;}
ull go(int p, int i, int n) {if (dp[p][i]==0) dp[p][i]=loop(p, i, i, n, 0); return (p==1) ? 1 : dp[p][i];}
ull res(int p, int i, int n, ull a) {return i<=n ? res(p, i+1, n, a+go(p, i, n)) : a;}
 
int _tmain(int argc, _TCHAR* argv[]) {
    int n, k; cout<<"Input n, k: "; cin >> n >> k;
    cout<<res(k, 1, n, 0)<<'\n';
    system("pause"); return 0;
}

@cotypan · 18.04.2015, 18:38 **[ТС]**

_Ivana, Спасибо)

@Anonim_ · 21.04.2019, 20:58

_Ivana, Не могли бы вы хотя бы в общих чертах объяснить идею решения? Я пытался понять ваш код на Haskell, запускать код на c++ в отладчике, но как-то тяжело дается... Очень интересно было бы узнать суть алгоритма!

@cotypan 0 / 0 / 0 Регистрация: 18.03.2015 Сообщений: 21
		1
	непонятность в условии и верен ли алгоритм 17.04.2015, 14:57. Показов 1836. Ответов 6 Метки нет (Все метки) Последовательность из l целых чисел b1, b2, ..., bl (1 ≤ b1 ≤ b2 ≤ ... ≤ bl ≤ n) называется хорошей, если каждое число делит без остатка следующее число в последовательности. Более формально, bi делит bi+1 для всех i (1 ≤ i ≤ l - 1). Вам даны n и k, найдите количество хороших последовательностей длины k. Формат входных данных: В первой строке записаны два целых числа через пробел n,k (1 ≤ n, k ≤50). Формат выходных данных: Выведите единственное целое число — количество хороших последовательностей длины k Примеры вводим 3 2. Получаем 5. вводим 6 4 Получаем 39 вводим 2 1 Получаем 2 Примечание В первом примере хорошие последовательности такие: [1,1],[2,2],[3,3],[1,2],[1,3]. То есть как я понимаю нужно сгененировать все подпоследовательности последовательность n длины k. Затем среди этих подпоследовательностей отобрать те что удовлетворяют условию хорошей последовательности. Например вводим 3 2.Получаем подполедоваетльности последовательности от 1 до 3 длины 2 : 11 12 13 21 22 23 31 32 33 Среди них отбираем хорошие последовательности: [1,1],[2,2],[3,3],[1,2],[1,3]. Их 5 штук. 0

@John Prick 2278 / 1769 / 741 Регистрация: 27.07.2012 Сообщений: 5,253
	17.04.2015, 15:01	2
	Ну этот алгоритм называется "в лоб". Возможно (и наверняка) есть более быстрые алгоритмы. 0

@cotypan 0 / 0 / 0 Регистрация: 18.03.2015 Сообщений: 21
	17.04.2015, 17:41 [ТС]	4
	_Ivana, Спасибо))Жаль Haskell не знаю... 0

@cotypan 0 / 0 / 0 Регистрация: 18.03.2015 Сообщений: 21
	18.04.2015, 18:38 [ТС]	6
	_Ivana, Спасибо) 0

@Anonim_ 0 / 0 / 1 Регистрация: 21.08.2016 Сообщений: 6
	21.04.2019, 20:58	7
	_Ivana, Не могли бы вы хотя бы в общих чертах объяснить идею решения? Я пытался понять ваш код на Haskell, запускать код на c++ в отладчике, но как-то тяжело дается... Очень интересно было бы узнать суть алгоритма! 0

непонятность в условии и верен ли алгоритм

Решение