R
On my laptop, 100 million counts a little less than a second. But we need to know the upper limit which maximum numbers will be imposed. Let's say it's 2 in 32 (or 2 in 31), which is logical and fits into the standard type integer).The same code, being launched from 2 in 32, I worked in 42 seconds.Now we're going to accelerate. But since it's very much like an olimpiad task, it's possible to use a variety of dirty optimizations that never fit into the industrial code.The first thing to remember is that if, for any number of people, the operation to deduct its numerals, the number will be repeated 9. This is very easy to prove if you know the rule of the denomination of 9. (any number is divided by 9 if the amount of its figures is divided by 9. If not divided, the balance of the 9-digit split and the 9-digit difference. The difference in the number and amount of the number will therefore be reversed.Modify a little code and start. We see that n the same sequence. (... 45 36 27 18 9 0). It is therefore possible to pre-empt certain n values and simply to provide the correct answer. Since I have a calculation for a maximum of 42 seconds, we just pick 50 intermediate values, which would be considered within 1 second in each range (50 with a reserve).The next stage will be reduced by 40%. We'll make two numbers a once. Here's my code slot: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 two times faster than the original. And if you add a backbone, you can adjust the time.But I think there's a formula. If we look at the conclusion, it can be seen that within the first 400 numbers there is a dependence - the number of deductions equals the whole of the division by 10 (plus minus 1). There's another correction factor to be recalculated.
