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

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

new kind of algo
Послано Ciprian 5 дек 2007 23:57
I found a new kind of algo for this problem.I wish if someone could tell me if it's good or bad. I got wa on test 2 .Bad algo or bad implementation?
!!11.First we find  numbers made from n-1 numbers that can begin with 0, but don't have 2 zeros one after the other.
We find them like this.for(i=0;i<=n-2;i++) we put the two zeros on i position and now we have 2 numbers one in the left of 2 zeros and one in the right.the number of numbers in right is k^((n-1)-2-i).In left we do !!11. for i-1.(if n<=4)else the number is (k-1)*k^(n-1-2-i)*(k-1)^(i-1)
Re: new kind of algo
Послано Bobur 6 дек 2007 18:57
I've too new algo, but I've CRASh(over flowler steck-check)
here is my code,

  function f(n, k : integer) : integer;
    begin
    f := 0;
    if n = 2 then f := 0
    else
      begin  if n = 3 then f := k-1
             else if n > 3 then f := TRUNC(f(n-1, k)+ (n-2)*exp((n-2)*ln(k-1)));
      end;

    end;

begin
   read(n, k);
   s := TRUNC((k-1)*exp((n-1)*ln(k)) - f(n, k));
   write(s);
end.
Re: new kind of algo
Послано Bobur 17 дек 2007 19:15
first I find how many numbers have 00;
for example:
k = 6;
n = 3 ----  0  1  2  3  4  5
            0  1  2  3  4  5
            0  1  2  3  4  5   5
n = 4 ----  0  1  2  3  4  5   5*6+5*5
n = 5 ----  0  1  2  3  4  5   5+25+25+125+125+125
n = 6 ----  0  1  2  3  4  5   5+25+25+125+125+125+625+625+625+625
n = 7 ----  0  1  2  3  4  5   5+25+25+125+125+125+625+625+625+625+3125+3125+3125+3125+3125
f = f(n-1)+(n-2)*exp((n-2)*ln(k-1));
4 = 5 + 2*5*5
5 = 55 + 3*5*5*5
6 = 330+4*5*5*5*5
...

then k^n all numbers
     k^(n-1) all numbers till n digits
  then we've  f=k^n-k^(n-1)-(n-2)*(k-1)^(n-2);
i can't find what's wrong in this