Помогите!!! 4. Первоклассные числа Ограничения: время - 200мс, память - 256МБ Если взять...

0 голосов
76 просмотров

Помогите!!! 4. Первоклассные числа Ограничения: время - 200мс, память - 256МБ Если взять натуральное число и найти сумму квадратов его цифр, затем сумму квадратов цифр результата и так далее, то через несколько шагов для некоторых из чисел получится число 1. Такие числа будем называть первоклассными. Например, первоклассным будет число 19, так как 1^2+9^2=82, 8^2+2^2=68, 6^2+8^2=100, 1^2+0^2+0^2=1. числа 2 или 5 первоклассными не являются. Напишите программу, которая находит количество первоклассных чисел среди чисел в диапазоне от А до В включительно. Первая строка ввода содержит два целых чисел А, В. Вывести одно целое число - количество первоклассных чисел среди чисел в диапазоне от А до В. Пример ввода1. Пример вывода1 5. 4 4 5 6 3 7. Пример ввода 2. Пример вывода 2 3 9 5 6. 1


Информатика (42 баллов) | 76 просмотров
0

Что означают эти примеры? На вводе 2 числа, на выводе - одно. Как понимать эти примеры? Во втором примере на вводе вообще одно число.

0

Ага, задачка-то ехидная. Число 4, к примеру, вызывает зацикливание, давая ряд 4, 16, 37, 58, 89, 145, 42, 20, 4, ...

0

Ограничение на A - это неравенство, типа 1 < A < 10000, например.

0

Ограничение на A -

0

Вывод 5

0

Ввод 1 20

0

И какие ограничения на A и B ?

0

Примеры не те это косяк

0

Какое ограничение на A и B ? Можно задать и 10 в 9 степени, тогда по времени вылетит.

Дан 1 ответ
0 голосов
Правильный ответ

PascalABC.NET 3.4.2, сборка 1847 от 28.10.2018

Внимание! Если программа не работает, обновите версию!

function СуммаКвадратовЦифр(Число: integer): integer;

begin

 Result := 0;

 while Число > 0 do

 begin

   Result += Sqr(Число mod 10);

   Число := Число div 10

 end

end;


function ЧислоПервоклассное(Число: integer): boolean;

begin

 Число := Abs(Число); // защита от злобных буратинок

 var L:=new SortedSet;

 L.Add(Число);

 repeat

   case Число of

     0, 2, 3:

       begin

         Result := False;

         Exit

       end;

     1:

       begin

         Result := True;

         Exit

       end;

     else

     begin

       Число := СуммаКвадратовЦифр(Число);

       if L.Contains(Число) then

       begin

         Result:=False;

         Exit

       end

       else L.Add(Число)

     end

   end

 until False // бесконечный цикл

end;


begin

 var (НижняяГраница, ВерхняяГраница) := ReadInteger2;

 var Количество := 0;

 for var ОчередноеЧисло := НижняяГраница to ВерхняяГраница do

   if ЧислоПервоклассное(ОчередноеЧисло) then Inc(Количество);

 Количество.Println

end.

1 100

20

(654k баллов)
0

При A=1, B=100000 время 700 мс

0

Вы бы еще взяли B порядка триллиона. У Вас в задании не указаны ограничения на a и b, но это не значит, что в программу можно пихать любые значения, а время при этом будет оставаться долями секунды.

0

Ввод 1 20 вывод 5.

0

Так ограничения

0

Ну вот поскольку ответов вообще нет ни на какие вопросы, оно все так, как оно есть.

0

Мне просто было интересно, какие ограничения на A и B? Ответ я так и не получил.

0

А... так это еще и не Ваше задание...

0

Можно получить ускорение алгоритма в разы, если использовать малоизвестное свойство числа "145", переходящего само в себя. Но я предпочел не ссылаться на то, что не могу обосновать.

0

Понятно. Но это не ограничения. Это контрольный пример. Можете пробовать))