Форум: "Основная";
Текущий архив: 2002.12.23;
Скачать: [xml.tar.bz2];
Вниз
К- ричные числа. Найти похожие ветки
← →
Armageddon (2002-12-10 22:22) [0]Дорогие господа программисты. Предлагаю вашему вниманию еще одну задачу.
Требуется вычислить количество N значных чисел в системе счисления с основанием K таких, что их запись не содержит двух подряд идущих нулей. Ограничения 2<=K<=10; N>=2; 4<=N+K<=180(!!!).
Когда-то я очень долго бился над задачей, недавно попалась на глаза. Помогите пожайлуста. Только не предлагайте, пожалуйста, способов типа "заносим в массив и просто проверяем нет ли в нем двух подряд идущих нулей". Необходим действительно рациональный и быстрый алгоритм. Буду очень презнателен.
← →
Uncle Archi (2002-12-10 22:34) [1]Это нечестно! Решать задачи с Timus"a при помощи других!
(Задача № 1009 ссылка:
http://acm.timus.ru/problem.asp?id=1009&rus )
← →
Armageddon (2002-12-10 23:00) [2]Между прочем эта задача была придложена в прошлом году на областной олимпиаде. А что точно такую задачу предложил кто-то еще я не виноват.
← →
Uncle Archi (2002-12-12 12:27) [3]Зайди на
acm.timus.ru
← →
DarkGreen (2002-12-12 16:11) [4]Страно, у меня получилась следующаая формула (если я правильно понял условия задачи) Result := K^n-K^(n-1)-(n-2)*(K-1), написал программульку бытренько, отправли ее на acm.timus.ru, а мне говорят, что решение неверное. Вот мое решение:
program K_N;
function Ex(K1, N1: Integer): Longint;
var
I: Integer;
Res: Longint;
begin
Res := K1;
for I := 1 to N1 - 1 do
begin
Res := Res * K1;
end;
Ex := Res;
end;
var
K, N: Integer;
Result: Longint;
begin
ReadLn(N, K);
Result := Ex(K, N)-Ex(K, N-1)-(N-2)*(K-1);
WriteLn(Result);
end.
← →
DarkGreen (2002-12-12 16:13) [5]Дополнение:
После компиляции размер exe"шника составил ~9Кб, а в статиске мне сказали, что количество используемой памяти = 390 Кб, что-то у них там не так работает. Иль я в чем не прав?
← →
Uncle Archi (2002-12-12 21:25) [6]>После компиляции размер exe"шника составил ~9Кб, а в статиске >мне сказали, что количество используемой памяти = 390 Кб,
>что-то у них там не так работает. Иль я в чем не прав?
Память даётся та, которую занимают переменные, а не exe"шник
>отправли ее на acm.timus.ru, а мне говорят, что решение
>неверное
Значит не решил
← →
DarkGreen (2002-12-13 05:43) [7]2 Uncle Archi ©: И где ты там увидел 390Кб переменных??? Программа в 100000 на паскале имеет сегмент данных ~64Кб. А у данной программы Data Size = 756 Code Size = 2829 Stack Size = 16384 (Borland Pascal 7.0)
> Значит не решил
Веский аргумент. Ты хотя бы решение глянул?
← →
Separator (2002-12-13 06:16) [8]
> DarkGreen © (13.12.02 05:43)
Ты наверное писал на Borland Pascal а они компилируют на дельфях, отсюда и больше памяти. Я тоже несколькими способами решал эту задачу, но то ответ не верен, то времени слишком много затрачивается на решение :-)
← →
DarkGreen (2002-12-13 06:35) [9]2 Separator ©:
Ну в этом случае, они конкретные уроды, указывают Паскаль, а компилят делфями, при чем даже компилируя делфями размер программы не может быть 390Кб. :(. Да, на счет этой задачи, как я понял, необходимо исключить из общего количества N-значных чисел, те, которые внутри себя содержат два подряд идущих нуля, а вот что делать, если число подряд идущих нулей > 2, в условии про это ни чего не говорится, и я такие числа не удалял, правильно ли это?
← →
Separator (2002-12-13 06:48) [10]нет, если больше, то они тоже долны удалятся. Вот рабочий пример, но в acm.timus он не проходит по времени:
function ExStr(N, K: integer): integer; //Для проверки значений
function Proverka(S: string): boolean;
var
i: integer;
begin
Result:= true;
for i:= 2 to Length(S) - 1 do
if (S[i] = "0") and (S[i + 1] = "0") then
begin
Result:= false;
Break
end
end;
var
J: integer;
procedure Work(Level: integer; S: string);
var
i: integer;
begin
if Level = 1 then
for i:= 1 to K - 1 do
Work(Level + 1, IntToStr(i))
else
if Level <> N then
for i:= 0 to K - 1 do
Work(Level + 1, S + IntToStr(i))
else
for i:= 0 to K - 1 do
if Proverka(S + IntToStr(i)) then
Inc(J)
end;
Самый примитивный метод решения задачи, кстати я тоже делал примерно также как и ты, только там формула попроще:
function Ex(N, K: integer): integer;
begin
Result:= trunc(exp(N * ln(K)) - exp((N - 1) * Ln(K)) - (N - 2) * (K - 1))
end;
Но результат не верен, если брать допусти N = 5 и K = 10
← →
DarkGreen (2002-12-13 07:10) [11]2 Separator © (13.12.02 06:48)
Спасибо большое за пояснения.
Этим парням из университета, надо посоветовать научиться ставить условия задачи. Чтобы люди, учавствующие в конкурсе не ломали себе голову над интерпретацией задания.
← →
Uncle Archi (2002-12-13 21:45) [12]>Ты наверное писал на Borland Pascal а они компилируют на
>дельфях, отсюда и больше памяти. Я тоже несколькими способами >решал эту задачу, но то ответ не верен, то времени слишком
>много затрачивается на решение :-)
Они компилят на хорошем паскале, который позволяет делать большие массивы и использует много памяти.
// если написать Int64-ошибка компиляции
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2002.12.23;
Скачать: [xml.tar.bz2];
Память: 0.47 MB
Время: 0.008 c
