There is a certain number N from it we take away the sum of its numbers. The question is how many times can you take? plain code

while n>0 do begin inc(k); x:=n; while x<>0 do begin n := n - (x mod 10); x := x div 10; end;

does not work as it goes beyond 1 sec. How else can you?

  • and if you run on a more powerful computer? - kandi 2:41 pm


2 answers 2

on my laptop 100 million counts a little less than a second. But you need to know the upper limit, what maximum numbers will be entered. Let's assume that this is 2 to 32 (or 2 to 31 - which is logical and fits into the standard type integer).

The same code, being launched from 2 to 32, I worked in 42 seconds.

And now we start to accelerate. But since this is very similar to the Olympiad task, then you can apply various dirty optimizations, which are never laid out in the industrial code.

The first thing to remember is that if for any number you perform the operation of subtracting its digits from it, then the resulting number will be a multiple of 9. This is very easily proved if you know the rule for checking for divisibility by 9. (any number is divisible by 9, if the sum of its digits is divisible by 9. If it is not divisible, then the remainder of dividing the number by 9 and the sum of the digits divided by 9 is the same. Therefore, the difference of the number and sum of its digits will be a multiple of 9).

Modify a bit of code and run. We see that n go through the same sequence. (... 45 36 27 18 9 0). Based on this, you can make a prediction for certain values ​​of n and simply substitute the correct answer. Since my calculation for the maximum takes 42 seconds, then we simply select 50 intermediate values, so that in each range it would be considered not longer than 1 second (50 - with a margin).

The next stage will be reduced by another 40%. We will summarize two digits at a time. Here is my code:

 program subb; // таблица сумм для двузначных чисел. const h:array[0..99] of integer = (0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18); var n, k, x:int64; l:int64; begin // это такой трюк, что бы можно было передавать как параметр и с консоли вводить if paramcount < 1 then readln(n) else val(paramstr(1), n, k); k := 0; while n > 0 do begin if (n = 9999999) then begin // это первая проверка для ускорения n := 0; k := k+333582; continue; end; inc(k); x := n; //writeln('curr n = ', n); while x > 0 do begin l := x mod 100; n := n - h[l]; x := x div 100; end; end; writeln(k); end.

This code is already 2 times faster than the original one. And if you add a few reference points, you can adjust the total time.

But I think there is a simpler formula. If you look at the conclusion, you can see that within the first 400 numbers there is a dependency - the number of deductions is equal to the integer part of dividing by 10 (plus 1). Then you need to subtract some other correction factor.

  • compared this code with his. My quicker doubled. Although with 9ki option is interesting, yes. - Yura Ivanov
  • Yes, this is a good optimization thing if you know how to use it, thanks to the code, it really turned out to be quick if you add a dozen checks 0.031ms - inceon

This option.
If we take an integer, then whatever the number to subtract is not more than 100 each time. Therefore, we do not need to calculate the sum of all digits for large numbers each time, at each iteration we can count the sum of only the last three digits, and the sum of the higher digits is calculated at least a few iterations. Thus, the number of calculations can be reduced by several times.
I sketched here on my knee, I didn’t really check it out. I’ve got such results ...

  N Вычитаний Время 2^31-1 54682584 3.744 2^32 106102644 7.441

4 seconds for Int32 is already quite good =)

For int64, there will be no more than 180 at each iteration, i.e. the same ears.

Threat I forgot to write, the original code works more than 14 seconds for 2 ^ 31-1