А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)
Код решения

A301. Количество точек в полукругах

13/11/2017 by Вадим Гордийчук

Задача

Даны действительные числа [latex]x_1, y_1[/latex], [latex]x_2, y_2[/latex], [latex]\ldots[/latex], [latex]x_{20}, y_{20}[/latex], [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex], [latex]\left( 0 < r_1 < r_2 < \ldots < r_{11} \right)[/latex]. Пары [latex]\left( x_1, y_1 \right)[/latex], [latex]\left( x_2, y_2 \right)[/latex], [latex]\ldots[/latex] [latex]\left( x_{20}, y_{20} \right)[/latex] рассматриваются как координаты точек плоскости. Числа [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex] рассматриваются как радиусы одиннадцати полукругов в полуплоскости [latex]y > 0[/latex] с центром в начале координат. Найти количество точек, попадающих внутрь каждого полукруга (границы-полуокружности не принадлежат полукругам).

Примечание: будем рассматривать задачу с произвольным количеством точек [latex]n[/latex] и полуокружностей [latex]m[/latex].

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

[latex]n[/latex], [latex]m[/latex], [latex]x_i, y_i[/latex], [latex]i = \overline{1, n}[/latex], [latex]r_j[/latex], [latex]j = \overline{1, m}[/latex]

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

[latex]a_j[/latex] — количество точек в [latex]j[/latex]-том полукруге, [latex]j = \overline{1, m}[/latex].

Тест

Входные данные	Выходные данные
20 11 14 4 5 -4 4 90 2 4.91 8 9.0 8.3 4.111 20 49.0 0 301.419 8.01 34.5 2.1 -49.1 0.01 0.03 56 1.91 4.04918 34.49294 -1.85892 5.01674 51 214 14.94 44.09 41.4 -154 -581.49 495 14.39 -81.682 77 194.4 0.3 20.82 50.9 51 65.845 90.37 109.58 170.83 217 301.58901 314	1 6 9 9 11 12 12 12 13 15 15

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

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

20 11

14 4
5 -4
4 90
2 4.91
8 9.0
8.3 4.111
20 49.0
0 301.419
8.01 34.5
2.1 -49.1
0.01 0.03
56 1.91
4.04918 34.49294
-1.85892 5.01674
51 214
14.94 44.09
41.4 -154
-581.49 495
14.39 -81.682
77 194.4
0.3
20.82
50.9
51
65.845
90.37
109.58
170.83
217
301.58901
314

1
6
9
9
11
12
12
12
13
15
15

Иллюстрация к тесту:

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

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

class Dot
{
	public double x, y;

	public Dot() {}

	public Dot(double x, double y)
	{
		this.x = x;
		this.y = y;
	}
}

public class Main
{
	public static double euclidianDistanceToZero(Dot a)
	{
		return Math.sqrt(a.x*a.x+a.y*a.y);
	}

	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n_dot = in.nextInt();
		int n_circ = in.nextInt();

		Vector <Dot> dots = new Vector<Dot>();

		for(int i = 0; i < n_dot; ++i)
		{
			Dot a = new Dot(in.nextDouble(), in.nextDouble());
			if (a.y > 0)
				dots.addElement(a);
		}

		double rads[] = new double[n_circ];
		int amounts[] = new int[n_circ];

		for(int i = 0; i < n_circ; ++i)
		{
			rads[i] = in.nextDouble();
			amounts[i] = 0;
		}

		if (n_circ == 1)
		{
			for(int i = 0; i < dots.size(); ++i)
				if (euclidianDistanceToZero(dots.elementAt(i)) < rads[0])
					++amounts[0];
		}
		else
			for(int i = 0; i < dots.size(); ++i)
			{
				int j = n_circ;
				double r = euclidianDistanceToZero(dots.elementAt(i));
	
				if (r < rads[n_circ-1]) // if dot belongs to one of the semicircles
				{
					if (r < rads[0]) // if dot belongs to the first semicircle
						j = 0;
					else if (rads[n_circ-2] <= r) // if dot belongs to the last semicircle
						j = n_circ-1;
					else // binary search of the smallest semicircle, which includes dot
					{
						int prev_l = 0, prev_r = n_circ, k;

						while(j == n_circ)
						{
							k = (prev_l+prev_r)/2;

							if (rads[k-1] <= r && r < rads[k])
								j = k;
							else if (r >= rads[k])
								prev_l = (prev_l+k)/2;
							else //if (r < rads[k-1])
								prev_r = (prev_r+k)/2;
						}
					}

					++amounts[j]; //increasing amount of dots, which belong to [j, n_circ-1] circles.
				}
			}

		for(int accumulated_amount = 0, i = 0; i < n_circ; ++i)
		{
			accumulated_amount += amounts[i];
			amounts[i] = accumulated_amount;
		}

		for(int i = 0; i < n_circ; ++i)
			out.println(String.valueOf(amounts[i]));
		out.flush();
	}
}

100

import java.util.*;

import java.lang.*;

import java.io.*;

class Dot

{

public double x, y;

public Dot() {}

public Dot(double x, double y)

{

this.x = x;

this.y = y;

}

public class Main

{

public static double euclidianDistanceToZero(Dot a)

{

return Math.sqrt(a.x*a.x+a.y*a.y);

}

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

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

int n_dot = in.nextInt();

int n_circ = in.nextInt();

Vector <Dot> dots = new Vector<Dot>();

for(int i = 0; i < n_dot; ++i)

{

Dot a = new Dot(in.nextDouble(), in.nextDouble());

if (a.y > 0)

dots.addElement(a);

}

double rads[] = new double[n_circ];

int amounts[] = new int[n_circ];

for(int i = 0; i < n_circ; ++i)

{

rads[i] = in.nextDouble();

amounts[i] = 0;

}

if (n_circ == 1)

{

for(int i = 0; i < dots.size(); ++i)

if (euclidianDistanceToZero(dots.elementAt(i)) < rads[0])

++amounts[0];

}

else

for(int i = 0; i < dots.size(); ++i)

{

int j = n_circ;

double r = euclidianDistanceToZero(dots.elementAt(i));

if (r < rads[n_circ-1]) // if dot belongs to one of the semicircles

{

if (r < rads[0]) // if dot belongs to the first semicircle

j = 0;

else if (rads[n_circ-2] <= r) // if dot belongs to the last semicircle

j = n_circ-1;

else // binary search of the smallest semicircle, which includes dot

{

int prev_l = 0, prev_r = n_circ, k;

while(j == n_circ)

{

k = (prev_l+prev_r)/2;

if (rads[k-1] <= r && r < rads[k])

j = k;

else if (r >= rads[k])

prev_l = (prev_l+k)/2;

else //if (r < rads[k-1])

prev_r = (prev_r+k)/2;

}

++amounts[j]; //increasing amount of dots, which belong to [j, n_circ-1] circles.

}

for(int accumulated_amount = 0, i = 0; i < n_circ; ++i)

{

accumulated_amount += amounts[i];

amounts[i] = accumulated_amount;

}

for(int i = 0; i < n_circ; ++i)

out.println(String.valueOf(amounts[i]));

out.flush();

}

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

Из входного потока считываем координаты всех точек, и отсеиваем из них те, у которых координата [latex]y \le 0[/latex], так как они по условию не могут принадлежать данным полуокружностям, остальные же добавляем в вектор точек dots. После этого, создаём два массива: первый rads — массив радиусов — считываем из входного потока, второй amounts — обнуляем. В i-ой ячейке массива amounts будем хранить количество точек, которые принадлежат [latex]i[/latex]-тому, и большим чем он полукругам. После этого, используя алгоритм бинарного поиска, находим наименьший полукруг, который содержит точку, и запоминаем его номер. Затем количество точек, содержащихся в данном и больших, чем данный полукругах, увеличиваем на единицу.

После обработки вектора точек, массив amounts преобразуем в массив количеств точек, содержащихся в конкретных полукругах, так как до этой обработки он содержит количество точек, которые «аккумулированы» i-тым, и большими чем i-тый полукруги.

Таким образом, общая асимптотика программы составит [latex]O \left(m+n \cdot \log_{2}{m}\right)[/latex], где [latex]n[/latex] — количество точек, а [latex]m[/latex] — полукругов.

Ссылки

Код на ideone.com;
Условие задачи, страница 126.

A324. Делители одного числа, взаимно простые с другим

07/07/2017 by Халафов Нурал

Задача

Даны целые числа [latex]p[/latex] и [latex]q[/latex]. Получить все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex].

Тесты

q	p	Все делители числа q, взаимно простые с числом p
40	15	1 2 4 8
87	3	1 29

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static long gcd(long x, long y){
		return (y != 0) ? gcd(y, x%y) : x;
	}
	public static void main (String[] args) 
	{
		int q = 0, p;
		Scanner in = new Scanner(System.in);
		q = in.nextInt();
		p = in.nextInt();
		for (int i = 1; i <= q; i++)
		{ 
        	if((q % i) == 0) {
            	if (gcd(i,p) == 1)
                	System.out.println(i + " ");
        	}
    	}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static long gcd(long x, long y){

return (y != 0) ? gcd(y, x%y) : x;

}

public static void main (String[] args)

{

int q = 0, p;

Scanner in = new Scanner(System.in);

q = in.nextInt();

p = in.nextInt();

for (int i = 1; i <= q; i++)

{

if((q % i) == 0) {

if (gcd(i,p) == 1)

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

}

Решение

Воспользуемся рекурсивной реализацией алгоритма Евклида. Пусть m и n — не равные нулю целые неотрицательные числа, и пусть [latex]m\geq n[/latex]. Тогда, если [latex]n=0[/latex], [latex]GCD(n,m)=m[/latex], а если [latex]n\neq 0[/latex], то для чисел [latex]m,n[/latex] и [latex]k[/latex], где [latex]k[/latex], где [latex]k[/latex] — остаток от деления [latex]m[/latex] и [latex]n[/latex], выполняется равенство [latex]GCD(m,n)=GCD(n,k)[/latex].

Для нахождения делителей числа [latex]q[/latex] взаимно простых с [latex]p[/latex], программа проверяет остатки от деления [latex]q[/latex] на все числа [latex]i[/latex] от [latex]1[/latex] до [latex]q[/latex]. Если остаток равен нулю, то число [latex]i[/latex] является делителем [latex]q[/latex]. Для каждого такого числа выполняется поиск наибольшего общего делителя (НОД — Greatest common divisor, GCD) [latex]i[/latex] и [latex]p[/latex] по алгоритму Евклида. [latex]1[/latex], то числа [latex]i[/latex] и [latex]p[/latex] взаимно простые.

А136в

01/07/2017 by Шостак Дмитрий

Задача

Даны натуральное число [latex]n[/latex], действительные числа [latex]a_1,\ldots, a_n[/latex]. Вычислить: [latex]|a_1|+\ldots+|a_n|[/latex].

Тесты

№	n	[latex]a_1,\ldots, a_n[/latex]	Результат
1	3	3.31 -2.11 8.21	13.63
2	6	-12.1 -2.56 9 5 -2 4	34.66
3	2	-3.65 -3.11	6.76

Решение

class StreamLab
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner input = new Scanner(System.in);
		int n;
		double a, sum = 0;
		n = input.nextInt();
		for(int i = 1; i <= n; i++)
		{
			a = input.nextDouble();
			sum += Math.abs(a);
		}
		System.out.println(sum);
	}
}

class StreamLab

{

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

{

Scanner input = new Scanner(System.in);

int n;

double a, sum = 0;

n = input.nextInt();

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

{

a = input.nextDouble();

sum += Math.abs(a);

}

System.out.println(sum);

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

С начала вводим количество элементов [latex]n[/latex], после чего, в цикле по i от 1 до [latex]n[/latex] вводим элементы и суммируем их значение по модулю в переменную sum , по выходу из цикла выводим сумму в консоль.

А320. Вложенный цикл

29/06/2017 by Шостак Дмитрий

Задача

Вычислить [latex] \sum\limits_{k = 1}^n (k^3 \sum\limits_{l = 1}^m (k-l)^2) [/latex] при произвольных целых [latex]n[/latex] и [latex]m[/latex].

Тесты

Тесты были подготовлены и проверены с помощью ресурса WolframAlpha.

№	n	m	Результат
1	3	2	144
2	2	9	1332
3	4	4	1120

Решение

class ThirdAndHalfLab
{
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		int n, m, k, l;
		n = input.nextInt();
		m = input.nextInt();
		long m_sum = 0, n_sum = 0;
		
		for(k = 1; k <= n; k++)
		{
			for(l = 1; l <= m; l++)
			{
				m_sum += (k-l)*(k-l);
			}
			n_sum += k*k*k * m_sum;
			m_sum -= m_sum;		
		}
		System.out.println(n_sum);
	}
}

class ThirdAndHalfLab

{

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n, m, k, l;

n = input.nextInt();

m = input.nextInt();

long m_sum = 0, n_sum = 0;

for(k = 1; k <= n; k++)

{

for(l = 1; l <= m; l++)

{

m_sum += (k-l)*(k-l);

}

n_sum += k*k*k * m_sum;

m_sum -= m_sum;

}

System.out.println(n_sum);

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Объявляем и инициализируем переменные n и m из потока ввода. Объявляем переменные для сумм: m_sum для вложенного цикла по [latex]l[/latex] и n_sum для цикла по [latex]k[/latex]. Далее создаем цикл по [latex]k[/latex] от 1 до [latex]n[/latex], в котором мы создаем вложенный цикл по [latex]l[/latex] от 1 до [latex]m[/latex], в котором вычисляем [latex]\sum\limits_{l=1}^m (k-l)^2[/latex] в переменную m_sum , по выходу из данного цикла добавляем произведение [latex] k^3 * \sum\limits_{l = 1}^m (k-l)^2 [/latex] в переменную n_sum , после чего обнуляем переменную m_sum . По выходу из цикла выводим финальную сумму в консоль.

java@Cat

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

Tag Archives: Абрамов

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

Задача

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

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

Тесты

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

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

Ссылки

A301. Количество точек в полукругах

Задача

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

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

Тест

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

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

Ссылки

A324. Делители одного числа, взаимно простые с другим

А136в

Задача

Тесты

Решение

Пояснения

А320. Вложенный цикл

Задача

Тесты

Решение