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

Вопросы программирования на Free Pascal, использования компилятора и утилит.

Модератор: Модераторы

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

Сообщение sign » 08.01.2019 09:27:44

Так я и предлагаю решать задачу с верхним порогом 10000. Как будто так и задано.
А на вопрос препода, почему не 10^10000, сделать круглыми глаза и вопрошать, но как? Разве такое возможно, да за 2 секунды? Типа, мне и в голову не пришло, что это не опечатка.
sign
энтузиаст
 
Сообщения: 1131
Зарегистрирован: 30.08.2009 09:20:53

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

Сообщение Дож » 08.01.2019 09:39:44

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).)
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 899
Зарегистрирован: 12.10.2008 16:14:47

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

Сообщение VirtUX » 08.01.2019 13:39:43

Вот еще мысль:
Число коробок [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;   


Это мы получим максимально возможное количество коробок. Но в чем реальный смысл задачи - не понимаю. Если принять, что в условии не допущено ошибок...
Аватара пользователя
VirtUX
энтузиаст
 
Сообщения: 880
Зарегистрирован: 05.02.2008 10:52:19
Откуда: Крым, Алушта

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

Сообщение Дож » 08.01.2019 23:48:09

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

Не, не получится соптимизировать мой алгоритм: т.к. ответ нужно хранить как длинное число, и инкремент его требует O(log(N)) времени, алгоритм неизбежно выполняется за O(log(N) * log(N)), а памяти требует O(log(N)). Но это всё равно укладывается в ограничения задачи.
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 899
Зарегистрирован: 12.10.2008 16:14:47

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

Сообщение Evgen » 09.01.2019 02:00:35

Уважаемые энтузиасты и долгожители условие задачи верное (выше подавал) и повторюсь (N от 1 до 10^10000 и задача должна выполнятся 2 сек., память - 256 МіБ).
Evgen
новенький
 
Сообщения: 19
Зарегистрирован: 03.01.2019 05:10:14

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

Сообщение Снег Север » 09.01.2019 08:08:13

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

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

Сообщение Evgen » 10.01.2019 00:26:56

Уважаемые энтузиасты и долгожители опечатки в задании нету. Я пробовал задание через указатели, возможно работать только с 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нег Север, как это "Сгенерировал, вывел и забыл." Обясни пожалуста точнее
Evgen
новенький
 
Сообщения: 19
Зарегистрирован: 03.01.2019 05:10:14

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

Сообщение Снег Север » 10.01.2019 08:59:30

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

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

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

Сообщение iskander » 10.01.2019 10:07:20

Evgen, вот вам решение с использованием MPArith(если я правильно путаю),
но с условием :wink:, вы расскажете откуда взялась эта странная задача.
Код: Выделить всё
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; 
......
iskander
энтузиаст
 
Сообщения: 590
Зарегистрирован: 08.01.2012 18:43:34

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

Сообщение Evgen » 11.01.2019 03:36:35

Уважаемый Снег Север, в задании необходимо ввести 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.
Evgen
новенький
 
Сообщения: 19
Зарегистрирован: 03.01.2019 05:10:14

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

Сообщение Vadim » 11.01.2019 04:10:13

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

Число 10^10000 имеет количество разрядов 10000. Следовательно, если один символ в строке соответствует одному разряду, то длина строки с числом будет 10000 символов.
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

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

Сообщение Evgen » 11.01.2019 04:19:10

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

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

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

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

Сообщение Лекс Айрин » 11.01.2019 06:25:19

Странный учитель программирования.
Аватара пользователя
Лекс Айрин
долгожитель
 
Сообщения: 5723
Зарегистрирован: 19.02.2013 16:54:51
Откуда: Волгоград

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

Сообщение Снег Север » 11.01.2019 06:39:08

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

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

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

Сообщение Vadim » 11.01.2019 07:31:17

Лекс Айрин писал(а):Странный учитель программирования.

Ну чего ж тут странного? У нас таких "учителей" пруд пруди. Хорошо, если они в пределах школьной программы преподают, а то некоторые ещё и на программу большой болт кладут. Это, скорее, к разряду печалей относится...
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Пред.След.

Вернуться в Free Pascal Compiler

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3

Рейтинг@Mail.ru