ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1009. K-ичные числа

Why wrong answer ?
Послано svg 20 окт 2002 00:49
In forum I saw this (http://acm.timus.ru/messages.asp?id=3516):
== cut ==
Use DP:
M[1] = K;
M[2] = (K-1) * K;
M[K] = (K-1) * ( Mas[K-2] + Mas[K-1] ); k<N;
Answer is M[N] = (K-1)*Mas[N-1]
== cut ==
And author this message solve the problem

But for N = 3 and K = 10
M[1] = 10,
M[2] = 90
M[3] = 9 * 90 = 810

But that wrong, because for N = 3
we have Kxx numbers, where K=1..9, xx - can't be 00, so 99 variants
and answer is 9 * 99 = 891
The fomular is wrong.
Послано Pursue Success 25 апр 2003 20:35
The correct dp fomula should be:

M[1] = K-1;
M[2] = (K-1) * K;
M[K] = (K-1) * ( Mas[K-2] + Mas[K-1] ); k<=N;
Answer is M[N]

so for your case,m[1]=9;m[2]=90;m[3]=9*(9+90)=891.