Большие числа

[sign]

Так я и предлагаю решать задачу с верхним порогом 10000. Как будто так и задано.
А на вопрос препода, почему не 10^10000, сделать круглыми глаза и вопрошать, но как? Разве такое возможно, да за 2 секунды? Типа, мне и в голову не пришло, что это не опечатка.

[Дож]

Evgen, вам не нужно пробегать все такие числа, достаточно посчитать их количество.

1. N считываем не в численную переменную, а в строковую (например, типа AnsiString). Пусть мы прочли и получили строку N = N_1 N_2 .. N_k
(N_i -- это десятичный знак от 0 до 9, k по условию от 1 до 10000).

2. Обозначим за M_i множество, состоящее из чисел длины k такого вида:

Код: Выделить всё

N_1 N_2 ... N_{i-1} {0 .. N_i - 1} {0..9} .. {0..9} {0..9}


Т.е. первые i-1 цифр совпадают с N, i-ая цифра от 0 до N_i - 1, остальные k-i цифр любые.
(Размер этого множества N_i * 10^(k-i)).

3. Обозначим через C(M_i) количество чисел во множестве M_i, в записи которых встречается 4. Для вычисления C(M_i) не требуется перебирать числа множества M_i, достаточно знать k, i, встречается ли 4 среди первых i-1 цифр и встречается ли 4 в диапазоне 0 .. N_i - 1.

C(M_i) вычисляется за O(k).

4. Ответ задачи -- сумма C(M_1) + C(M_2) + C(M_3) + ... + C(M_k), и прибавить 1, если в изначальном N встречается 4.

Памяти требуется 10KB, время работы O(k*k)=O(100 * 10^6) < 2 сек. (Скорее всего можно соптимизировать до O(k).)

[VirtUX]

Вот еще мысль:

Число коробок [1..10] - 4 встречается только в одной коробке
Число коробок [1..10^2] - 19 коробок
Число коробок [1..10^3] - 271 коробка
...
Число коробок [1..10^10000] - X раз

Следовательно код должен был быть примерно таким:

Код: Выделить всё

var
  i: integer;
  cou: VeryLargeNumber;
begin
  cou:= 0;
  for i:= 1 to 10000 do begin
    cou:= (cou*9) + trunc(exp((i-1)*ln(10)));
  end;
end;   

Это мы получим максимально возможное количество коробок. Но в чем реальный смысл задачи - не понимаю. Если принять, что в условии не допущено ошибок...

[Дож]

Памяти требуется 10KB, время работы O(k*k)=O(100 * 10^6) < 2 сек. (Скорее всего можно соптимизировать до O(k).)

Не, не получится соптимизировать мой алгоритм: т.к. ответ нужно хранить как длинное число, и инкремент его требует O(log(N)) времени, алгоритм неизбежно выполняется за O(log(N) * log(N)), а памяти требует O(log(N)). Но это всё равно укладывается в ограничения задачи.

[Evgen]

Уважаемые энтузиасты и долгожители условие задачи верное (выше подавал) и повторюсь (N от 1 до 10^10000 и задача должна выполнятся 2 сек., память - 256 МіБ).

[Снег Север]

Святой Никлас (Вирт), ну что за проблемы...
Рассуждаем. Числа в диапазоне 1 до 10^10000 это набор строк из цифр длиной от 1 до 10000 символов. В однозначных числах есть только один результат - "4". В двузначных все числа вида Х4 и 4Х, где Х - любая цифра. Надо только исключить дубликат "44". В трехзначных - ХХ4, Х4Х и 4ХХ. И так далее. Простой набор циклов.
Естественно, запоминать каждое число (строку) не надо. Сгенерировал, вывел и забыл. 10000 цифровых символов - это 10000 байт.

[Evgen]

Уважаемые энтузиасты и долгожители опечатки в задании нету. Я пробовал задание через указатели, возможно работать только с N =10000000. Вот мой код. может что то не правильно в программе:

program korob;
var k1,ch,d:^longint; k,cod:byte; i,j:longint; s,n:^ansistring;
begin
readln(k); new(n); new(k1); new(s); new(ch); new(d);
readln(n^);
k1^:=0; val(n^,d^,cod);
for i:=4 to d^ do begin s^:=n^;
for j:=1 to length(s^) do
if (s^[j]='4') then k1^:=k1^+1;
val(n^,ch^,cod);ch^:=ch^-1;str(ch^,n^);
end;
writeln(k1^);
Dispose (n);
Dispose (k1);
Dispose (s);
Dispose (ch);
Dispose (d);
end.

Добавлено спустя 10 минут 17 секунд:
Cнег Север, как это "Сгенерировал, вывел и забыл." Обясни пожалуста точнее

[Снег Север]

Cнег Север, как это "Сгенерировал, вывел и забыл." Обясни пожалуста точнее

Я вам в третий раз объясняю, что вы не поняли смысла задачи. Забудьте о "числах", вам надо работать не с числами, а с массивами символов от 0 до 9, длина массива от 1 до 10000. Или строками, что в данном случае удобнее.
Устанавливаете длину строки, заполняете по алгоритму, который я написал выше, выводите на экран, строку очищаете.

[iskander]

Evgen, вот вам решение с использованием MPArith(если я правильно путаю),
но с условием , вы расскажете откуда взялась эта странная задача.

Код: Выделить всё

program boxes;

{$mode objfpc}{$H+}

uses
  SysUtils, mp_types, mp_base;

procedure Solve;
var
  X, Y: mp_int;
  I: Integer;
  Count: string;
begin
  mp_init2(X, Y);
  try
    mp_set1(X);
    mp_set1(Y);
    for I := 2 to 10000 do
      begin
        mp_mul_w(Y, 10, Y);
        mp_mul_w(X, 9, X);
        mp_add(X, Y, X);
      end;
    Count := mp_adecimal(X);
  finally
    mp_clear2(X, Y);
  end;
  WriteLn('Count = ', Count);
end;

begin
  Solve;
  ReadLn;
end.


и да, можно и пошустрее

Код: Выделить всё

.....
procedure Solve;
var
  X, Y: mp_int;
  Count: string;
begin
  mp_init2(X, Y);
  try
    mp_set_pow(X, 10, 10000);
    mp_set_pow(Y, 9, 10000);
    mp_sub(X, Y, X);
    Count := mp_adecimal(X);
  finally
    mp_clear2(X, Y);
  end;
  WriteLn('Count = ', Count);
end; 
......


[Evgen]

Уважаемый Снег Север, в задании необходимо ввести N (N может меняться от 1 до 10^10000). Мне не понятно, что вы говорите "Длина строки от 1 до 10000, а не до 10^1000). С длиной строки 10000000 у меня задача проходит, а вот дальше штопорит.

Ответ для Iskander
Сначала хочу спросить включена ли библиотека MPArith автоматически у FRC, ели нет, то как ее подключить? И постараюсь разобраться в том, что вы написали.
Дело в том, что задача на самом деле немного другая (сложнее), я изложил основную мысль, а остальное хотел сделать сам, но пока не получается.
И теперь говорю откуда взялась эта странная задача.
Я готовлюсь к олимпиаде по программированию и задача с алготестера (оригинал условия на украинском языке, но думаю будет понятно)
https://algotester.com/uk
надо за регистрироваться и найти задачу 0162 - Щасливi днi пiнгвiнiв
(Извините, скопировать условие не смог для вставки в ответ).
Спасибо всем.

Добавлено спустя 24 минуты 2 секунды:
Iskander, если попробуете решить эту задачу, то пропустите ее на алготестере (если пройдут все тести, то результат ЗАРАХОВАНО. У меня проходит только два теста, на третьем или лимит времени, или неправильный ответ, или лимит памяти.
Например этот код (уже моей задачи з алготестера Лимит памяти 3
program Pingvin;
var n,kil,i,j:longint; k:byte; k1:longint; s:ansistring; x:array of ansistring;
begin
readln(k); readln(n); setlength(x,n+1); k1:=0;
for i:=1 to n do begin str(i,x[i]); s:=x[i]; for j:=1 to length(s) do if (s[j]='4') or (s[j]='7') then k1:=k1+1; end;
kil:=k1 div (k+1); writeln(kil); x:=nil;
end.


Этот код дает ответ Неверный ответ3:
program Pingvin;
var kil,k1,ch,d:^int64; k,cod:byte;i,j:int64; s,n:^ansistring;
begin
readln(k); new(n); new(kil); new(k1); new(s); new(ch); new(d); readln(n^); k1^:=0; val(n^,d^,cod);
for i:=4 to d^ do begin s^:=n^; for j:=1 to length(s^) do if (s^[j]='4') or (s^[j]='7') then k1^:=k1^+1; val(n^,ch^,cod);ch^:=ch^-1;str(ch^,n^) ; end;
kil^:=k1^ div (k+1); writeln(kil^);
Dispose (n); Dispose (kil); Dispose (k1); Dispose (s); Dispose (ch); Dispose (d);
end.

[Vadim]

Мне не понятно, что вы говорите "Длина строки от 1 до 10000, а не до 10^1000).

Число 10^10000 имеет количество разрядов 10000. Следовательно, если один символ в строке соответствует одному разряду, то длина строки с числом будет 10000 символов.

[Evgen]

Теперь дошло, спасибо Vadim

Добавлено спустя 10 минут 58 секунд:
Уважаемый Iskander, если Вы захатите попробовать решить ориинал задачи на алготестере, то :
В столбце ЗАДАЧА выберите задачу
Кнопка ВЫБРАТЬ файл, кнопка НАДІСЛАТИ
После появления зельоного поля УСПЕХ ждем результата, если не появляется обновляем (над зеленым полем).

На уровне моих знаний я пока больше сделать не могу (я ученик 10 класса, моему учителю это не интересно - не школьная программа). Буду пробовать MPArith, если удастся.
Все, иду спать. Завтра буду думать.
Хто на форуме, всем спокойной ночи.

[Лекс Айрин]

Странный учитель программирования.

[Снег Север]

Уважаемый Снег Север, в задании необходимо ввести N (N может меняться от 1 до 10^10000). Мне не понятно, что вы говорите "Длина строки от 1 до 10000, а не до 10^1000). С длиной строки 10000000 у меня задача проходит, а вот дальше штопорит.

Вы удивитесь , но 10^M - это, в десятичной записи, единица и M нулей после неё. Поэтому, наибольшее целое число, меньшее 10^10000 - это ровно 10000 девяток. Проверка проста и наглядна:
10^1 = 10
10^2 = 100
10^3 = 1000
10^4 = 10000 и т.д.

[Vadim]

Странный учитель программирования.

Ну чего ж тут странного? У нас таких "учителей" пруд пруди. Хорошо, если они в пределах школьной программы преподают, а то некоторые ещё и на программу большой болт кладут. Это, скорее, к разряду печалей относится...