|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
11.12.2016, 18:45 | #1 |
Форумчанин
Регистрация: 21.05.2014
Сообщений: 121
|
Сколько существует T-значных чисел, в записи которых нет K подряд идущих нечетных цифр?
Всем привет!
Хочу обратиться за помощью по задаче. Конкретно интересует идея решения. Условие задачи: Заданы числа K и T. Вам необходимо выяснить, сколько существует T-значных чисел, в записи которых нет K подряд идущих нечетных цифр (это цифры 1,3,5,7,9). Формат ввода: K, T, M – три числа через пробел. Ограничения: 1 <= K, T <= 30; 10<=M<=1000000. Формат вывода: Количество T-значных чисел, в записи которых нет K подряд идущих нечетных цифр взятое по модулю M (подразумевается остаток от деления искомого числа на M). Пример ввода: 2 3 100 Пример вывода: 50 Ну ясно, что нужно решать с помощью ДП (динамическое программирование, рекурентные соотношения). Первое что можно было заметить в этой задаче это, то что мы можем заменить цифры на 2 - это чётная цифра и 1 - нечётная. У меня есть 2 идеи, но в каждой у меня проблема с переходами. 1 идея: ДП будет по 2 параметрам: i - на какой мы сейчас цифре и j - чётная или не чётная цифра (j = 1, либо j = 2), и храним мы в нём кол-во вариантов сделать такую последовательность. В начале f[1,2] = 1 и если K > 1, тогда f[1,1] = 1. Дальше мы бы перебирали i от 2 до T и у нас было бы 2 перехода: 1. f[i,2]:=(f[i,2]+f[i-1,1]+f[i-1,2]) mod M; 2. if i < K then f[i,1]:=(f[i,1]+f[i-1,1]+f[i-1,2]) mod M else ... А вот тут и у меня проблема, из каких состояни мы могли придти? Ну очивидно что, одно из них это f[i-1,2]. Но это же не все варианты, мы могли как-то придти и из нечётных (1). Я много чего пытался, но всёровно не получается нормальные переходы сделать. Ну и после цикла мы бы просто вывели (5^T mod M)*(f[T,1]+f[T,2]) mod M. 2 идея: ДП также будет по 2 параметрам: i - на какой мы сейчас цифре и j - сколько нечётных цифр (1) стоит в конце (0 <= j <= i), и мы также храним в нём кол-во вариантов. В начале f[1,0] = 1 и если K > 1, тогда f[1,1] = 1. Ну и с переходами тут у меня ничего, я не знаю какие они должны быть. Буду благодарен любой помощи, заранее спасибо! |
11.12.2016, 20:33 | #2 |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
Примерно так -
Код:
|
11.12.2016, 21:04 | #3 | |
Форумчанин
Регистрация: 21.05.2014
Сообщений: 121
|
Цитата:
|
|
11.12.2016, 21:11 | #4 |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
Все как ты и сказал. Квадратное ДП. dp[i][j]. I - количество цифирок, J сколько цифр в конце нечетны.
Переходы. dp[i][0] - это мы ко всем числам, чтобы были на предыдущем шаге дописываем четную цифру. Значит это сумма dp[i] по всем j, умноженная на 5. dp[i][j] можно получить если дописать к числу, с количеством цифр меньшим на 1, в котором было уже j-1 нечетная цифра, нечетную цифру. Таких 5. Значит dp[i][j] = dp[i-1][j-1]*5 Все. И отдельный случай, когда i = 1. Нужно помнить, что лидирующих нолей быть не может (а может и могут, я не в читывался в условие. да и не тестил сильно) |
11.12.2016, 21:12 | #5 |
Заблокирован
Регистрация: 29.11.2016
Сообщений: 215
|
|
11.12.2016, 21:21 | #6 |
Форумчанин
Регистрация: 21.05.2014
Сообщений: 121
|
Блин вообще лёгкие переходы) Огромное спасибо! Отпишусь, если сдам.
|
11.12.2016, 21:26 | #7 |
Заблокирован
Регистрация: 29.11.2016
Сообщений: 215
|
|
11.12.2016, 21:28 | #8 | |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
Цитата:
|
|
11.12.2016, 21:32 | #9 |
Заблокирован
Регистрация: 29.11.2016
Сообщений: 215
|
|
11.12.2016, 23:03 | #10 | |
Форумчанин
Регистрация: 21.05.2014
Сообщений: 121
|
Цитата:
Вот на такой тест: 7 9 123123 Должен быть такой ответ: 46259 UPD. Для j > k мы должны взять все варианты из f[i-j-1]. i-j-1 потому что будет j нечётных и затем 1 чётное. Это вроде бы правильно так? Ну вообщем, новерно, куда-то в эту сторону нужно переход делать. Или нужно ещё прибавить кол-во вариантов получить f[i-j,0]? Скорее всего, но ответ тоже неверный. Код:
Последний раз редактировалось VladKB1; 11.12.2016 в 23:51. |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
наибольшее количество идущих подряд цифр | Alexandr- | Помощь студентам | 1 | 11.03.2013 23:02 |
среди всех n-значных чисел указать те сумма цифр которых равна данному числу k. (C#) | Гузель23 | Помощь студентам | 2 | 03.03.2013 20:07 |
Трехзначные числа,в десятичной записи которых нет одинаковых цифр | X@OC | Общие вопросы по Java, Java SE, Kotlin | 6 | 10.04.2012 18:26 |
Сколько n-значных чисел можно образовать из двух цифр 5 и 9, в которых три одинаковые цифры не стоят рядом | Thunder Dragon | Паскаль, Turbo Pascal, PascalABC.NET | 7 | 26.03.2012 20:05 |
Пусть дан текст. Найдите наибольшее количество цифр, идущих подряд. | abakuz | Помощь студентам | 5 | 28.05.2011 17:08 |