Задача

Задано натуральное число [latex]N[/latex]. От данного числа вычтем сумму цифр этого числа, от полученного числа опять вычтем сумму цифр и т.д. Данную операцию будем продолжать до тех пор, пока полученное число положительно. Сколько раз будем выполнять данную операцию?

Входные данные

Во входной строке находится число [latex]N[/latex], которое не превышает [latex]2147483647[/latex].

Выходные данные

Количество выполненных операций.

Тесты

Входные данные	Выходные данные
[latex]23[/latex]	[latex]3[/latex]
[latex]55555[/latex]	[latex]3000[/latex]
[latex]1234567[/latex]	[latex]49877[/latex]
[latex]999999999[/latex]	[latex]25632473[/latex]
[latex]2147483647[/latex]	[latex]54682584[/latex]

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long N, sum, subsidiary = 0, quantity = 0;
    	Scanner in = new Scanner(System.in);
    	N = in.nextLong();
    	while (N > 999999999) {
        	sum = 0;
        	subsidiary = N;
        	while (subsidiary!=0) {
            	sum += subsidiary%10;
            	subsidiary /= 10;
        	}
        	N -= sum;
        	quantity++;
    	}
    	if (N == 999999999) {
        	N = 0;
        	quantity += 25632473;
    	}
    	while (N > 0) {
        	sum = 0;
        	subsidiary = N;
        	while (subsidiary != 0) {
            	sum += subsidiary%10;
            	subsidiary /= 10;
        	}
        	N -= sum;
        	quantity++;
    	}
    	System.out.println(quantity);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

long N, sum, subsidiary = 0, quantity = 0;

Scanner in = new Scanner(System.in);

N = in.nextLong();

while (N > 999999999) {

sum = 0;

subsidiary = N;

while (subsidiary!=0) {

sum += subsidiary%10;

subsidiary /= 10;

}

N -= sum;

quantity++;

}

if (N == 999999999) {

N = 0;

quantity += 25632473;

}

while (N > 0) {

sum = 0;

subsidiary = N;

while (subsidiary != 0) {

sum += subsidiary%10;

subsidiary /= 10;

}

N -= sum;

quantity++;

}

System.out.println(quantity);

}

Решение задачи

Данную задачу можно решить, вычитая от данного числа [latex]N[/latex] суммы цифр, пока само число не станет равным [latex]0[/latex], с помощью циклов. Но этого нам не позволяет ограничение по времени.
Поэтому мы найдем максимально возможное число, которое мы можем получить при вычитании из больших чисел сумм цифр и которое проходит по времени. Это число — [latex]999999999[/latex] (найдено экспериментальным путем). Из него необходимо вычесть суммы цифр [latex]25632473[/latex] раз, чтобы получился [latex]0[/latex].
Тогда из чисел, которые больше данного, достаточно вычитать суммы цифр, пока они не станут равными [latex]999999999[/latex] и прибавить к количеству вычитаний [latex]25632473[/latex].
Если [latex]N[/latex] меньше найденного нами числа, то можно из него просто вычитать суммы цифр, пока оно не станет равным [latex]0[/latex].

Ссылки

Условие задачи на e-olymp
Код решения

Facebook
X
Shares

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

e-olymp 481. И опять: сколько можно?