Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 11.12.2016, 18:45   #1
VladKB1
Форумчанин
 
Регистрация: 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.

Ну и с переходами тут у меня ничего, я не знаю какие они должны быть.


Буду благодарен любой помощи, заранее спасибо!
VladKB1 вне форума Ответить с цитированием
Старый 11.12.2016, 20:33   #2
Dekay
Пользователь
 
Регистрация: 21.06.2016
Сообщений: 65
По умолчанию

Примерно так -
Код:
int k, n, m;
    cin >> k >> n >> m;
    k--;
    vector<vector<int> > v(n+1, vector<int>(k+1, 0));
    v[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            v[i][j] = (v[i-1][j-1]*5)%m;
        }
        if (i == 1) {
            v[i][0] = ((accumulate(all(v[i-1]), 0)%m)*4)%m;
        }
        else v[i][0] = ((accumulate(all(v[i-1]), 0)%m)*5)%m;
    }
    cout << accumulate(all(v[n]), 0)%m << endl;
Вроде все понятно в коде. Если что - могу пояснить
Dekay вне форума Ответить с цитированием
Старый 11.12.2016, 21:04   #3
VladKB1
Форумчанин
 
Регистрация: 21.05.2014
Сообщений: 121
По умолчанию

Цитата:
Сообщение от Dekay Посмотреть сообщение
Примерно так -
Код:
int k, n, m;
    cin >> k >> n >> m;
    k--;
    vector<vector<int> > v(n+1, vector<int>(k+1, 0));
    v[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            v[i][j] = (v[i-1][j-1]*5)%m;
        }
        if (i == 1) {
            v[i][0] = ((accumulate(all(v[i-1]), 0)%m)*4)%m;
        }
        else v[i][0] = ((accumulate(all(v[i-1]), 0)%m)*5)%m;
    }
    cout << accumulate(all(v[n]), 0)%m << endl;
Вроде все понятно в коде. Если что - могу пояснить
Спасибо! Но я пишу на паскале. Если можно, то объясните словами саму дп и переходы.
VladKB1 вне форума Ответить с цитированием
Старый 11.12.2016, 21:11   #4
Dekay
Пользователь
 
Регистрация: 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. Нужно помнить, что лидирующих нолей быть не может (а может и могут, я не в читывался в условие. да и не тестил сильно)
Dekay вне форума Ответить с цитированием
Старый 11.12.2016, 21:12   #5
olej.tsil
Заблокирован
 
Регистрация: 29.11.2016
Сообщений: 215
По умолчанию

Цитата:
Сообщение от VladKB1 Посмотреть сообщение
Ну ясно, что нужно решать с помощью ДП (динамическое программирование, рекурентные соотношения).
Совершенно не обязательно.
Что и показывает предложенное вам решение - нет там на дух никакого ДП (рекурсивного обхода).
olej.tsil вне форума Ответить с цитированием
Старый 11.12.2016, 21:21   #6
VladKB1
Форумчанин
 
Регистрация: 21.05.2014
Сообщений: 121
По умолчанию

Блин вообще лёгкие переходы) Огромное спасибо! Отпишусь, если сдам.
VladKB1 вне форума Ответить с цитированием
Старый 11.12.2016, 21:26   #7
olej.tsil
Заблокирован
 
Регистрация: 29.11.2016
Сообщений: 215
По умолчанию

Цитата:
Сообщение от VladKB1 Посмотреть сообщение
Отпишусь, если сдам.
Лучше выставиться.
olej.tsil вне форума Ответить с цитированием
Старый 11.12.2016, 21:28   #8
Dekay
Пользователь
 
Регистрация: 21.06.2016
Сообщений: 65
По умолчанию

Цитата:
Блин вообще лёгкие переходы) Огромное спасибо! Отпишусь, если сдам.
Если не сдашь, тоже отпишись. Если есть еще задачи. Любые - кидай. Скучно же...
Dekay вне форума Ответить с цитированием
Старый 11.12.2016, 21:32   #9
olej.tsil
Заблокирован
 
Регистрация: 29.11.2016
Сообщений: 215
По умолчанию

Цитата:
Сообщение от Dekay Посмотреть сообщение
Если не сдашь, тоже отпишись. Если есть еще задачи. Любые - кидай. Скучно же...
А если не сдаст, то задачи будут не скоро :
Цитата:
Через две, через две зимы,
Через две, через две весны
Отслужу, отслужу, как надо, и вернусь.
olej.tsil вне форума Ответить с цитированием
Старый 11.12.2016, 23:03   #10
VladKB1
Форумчанин
 
Регистрация: 21.05.2014
Сообщений: 121
По умолчанию

Цитата:
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= k; j++) {
Моя проблема была, в том что можно составлять последовательность из j > k нечётных чисел. Главное что бы не было, что где-то в последовательности есть ровно k подряд идущих нечётных чисел. Получается нужно идти j от 1 до i но если i > k то нужны другие переходы, так как f[i-1,j-1] составляет из себя уже цепоку j-1 нечётных чисел. Может как-то посчитать кол-во таких "плохих" вариантов и отнять? Вообщем нужно, как-то сделать и для таких вариантов.

Вот на такой тест:
7 9 123123

Должен быть такой ответ:
46259

UPD. Для j > k мы должны взять все варианты из f[i-j-1]. i-j-1 потому что будет j нечётных и затем 1 чётное. Это вроде бы правильно так? Ну вообщем, новерно, куда-то в эту сторону нужно переход делать. Или нужно ещё прибавить кол-во вариантов получить f[i-j,0]? Скорее всего, но ответ тоже неверный.

Код:
 if j > k then
  begin
   sum:=0;
   for o:=0 to n do sum:=sum+f[i-j-1,o];

   f[i,j]:=(f[i,j]+sum+f[i-j,0])*5 mod m;
  end;

Последний раз редактировалось VladKB1; 11.12.2016 в 23:51.
VladKB1 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
наибольшее количество идущих подряд цифр 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