А329. Квадрат суммы цифр числа

04/12/2018 by Костя Григорян

Задача

Задача из сборника задач по программированию Абрамова С.А. 2000 г.
Даны натуральные числа $n$, $m$. Получить все меньшие натуральные числа, квадрат суммы цифр которых равен $m$.

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

Два положительных числа $n$ и $m$.

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

Все целые числа из $\left ( 0, n \right )$, удовлетворяющие условию.

Тесты

Входные данные	Выходные данные
$1234 \ 9$	$3 \ 12 \ 21 \ 30 \ 102 \ 111 \ 120 \ 201 \ 210 \ 300 \ 1002 \ 1011 \ 1020 \ 1101 \ 1110 \ 1200$
$100 \ 4$	$2 \ 11 \ 20$
$49 \ 49$	$7 \ 16 \ 25 \ 34 \ 43$
$1000 \ 1$	$1 \ 10 \ 100$

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

import java.util.Scanner;
 
public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		for(int i=1; i<n; i++) {
			int a=i;
			int sum=0;
			while(a!=0) {
				sum+=a%10;
				a/=10;
			}
			if(sum*sum==m)
				System.out.print(i+" ");
		}
	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int m = scanner.nextInt();

for(int i=1; i<n; i++) {

int a=i;

int sum=0;

while(a!=0) {

sum+=a%10;

a/=10;

}

if(sum*sum==m)

System.out.print(i+" ");

}

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

Находим сумму цифр каждого числа от $1$ до $n$, проверяя равняется ли эта сумма, возведенная в квадрат, числу $m$. В случае положительного ответа, выводим число, сумму цифр которого мы проверяли.

Ссылки

Условие задачи (страница 135)
Код решения

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

02/12/2018 by Алиса Ворохта

Задача

Задано натуральное число [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
Код решения

e-olymp 141. Минимальная сумма цифр

01/07/2016 by Ирина Литвиненко

Задача взята с сайта www.e-olymp.com

Условие задачи:

Сколько натуральных чисел из промежутка [latex][M,N][/latex] имеют наименьшую сумму цифр ?

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

Во входном файле два числа [latex]M[/latex] и [latex]N[/latex], [latex]1\le M\le N\le 1000000[/latex].

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

В выходной файл нужно записать ответ – одно число.

Тесты

№	M	N	Вывод
1	1	100	3
2	2	17	1
3	32	1024	2
4	1	1000000	7
5	10	10	1

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

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


class Main {
	
	public static void main (String[] args) throws java.lang.Exception {
		
		int sumMin, counter = 1;
		
		Scanner scanner = new Scanner(System.in);
		int m = scanner.nextInt();
		int n = scanner.nextInt();
		
		sumMin = sumOfDigits(m);
		
		for(int i = m + 1; i <= n; i++) {
			if (sumOfDigits(i) < sumMin) {
				sumMin = sumOfDigits(i);
				counter = 1;
			} else if (sumOfDigits(i) == sumMin)   
		    counter++;
		}
		System.out.println(counter);
	}
	
	public static int sumOfDigits(int a){
		int sum = 0;
		while (a > 0) {
			sum += a%10;
			a /= 10;
		}
	return sum;
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

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

int sumMin, counter = 1;

Scanner scanner = new Scanner(System.in);

int m = scanner.nextInt();

int n = scanner.nextInt();

sumMin = sumOfDigits(m);

for(int i = m + 1; i <= n; i++) {

if (sumOfDigits(i) < sumMin) {

sumMin = sumOfDigits(i);

counter = 1;

} else if (sumOfDigits(i) == sumMin)

counter++;

}

System.out.println(counter);

}

public static int sumOfDigits(int a){

int sum = 0;

while (a > 0) {

sum += a%10;

a /= 10;

}

return sum;

}

www.ideone.com

Решение
Для решения данной задачи зададим функцию, которая возвращает сумму чисел вводимого нами числа. После ввода границ необходимого промежутка присваиваем минимальную сумму [latex](sumMin)[/latex] сумме цифр первого числа [latex]M[/latex], счетчик количества элементов с минимальной суммой цифр изначально равен 1. В цикле подсчитываем сумму цифр каждого последующего числа, если найдется число с меньшей суммой цифр, значит теперь эта сумма и является минимальной, присваиваем её значение переменной [latex]sumMin[/latex]. Если же встречаются элементы, сумма цифр которых равна [latex]sumMin[/latex], увеличиваем счетчик. Он и будет количеством натуральных чисел на промежутке, имеющих наименьшую сумму цифр.
Ссылка на полностью засчитанное решение на сайте e-olymp.

java@Cat

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

Tag Archives: сумма цифр

А329. Квадрат суммы цифр числа

Задача

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

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

Тесты

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

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

Ссылки

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

Задача

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

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

Тесты

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

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

Ссылки

e-olymp 141. Минимальная сумма цифр