e-olymp 930. Номер мобильного телефона

26/12/2018 by Томас Пасенченко

Задача

Задан номер мобильного телефона. Определить, какие цифры отсутствуют в этом номере.

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

В единственной строке задан номер мобильного телефона.

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

В первой строке вывести количество отсутствующих в номере цифр. Во второй строке в порядке возрастания вывести отсутствующие цифры, разделенные пробелом.

Тесты

Входные данные	Выходные данные
0631562976	2 4 8
2139087	3 4 5 6
1111111111	9 0 2 3 4 5 6 7 8 9
7	9 0 1 2 3 4 5 6 8 9
4848	8 0 1 2 3 5 6 7 9
0921234567	1 8
6723545	4 0 1 8 9
9867453210	0
+38 (037) 123-4-765	1 9

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
	public static void main (String[] args) throws Exception{
		int code;
		int count = 0;
		int n[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while ((code = br.read()) != -1) {
			if (code >= 48 && code <= 57) n[code - 48]++;
		}
		for (int i = 0; i < 10; i++) {
        	if (n[i] == 0) count++;
		}
		System.out.println(count);
		for (int i = 0; i < 10; i++) {
			if (n[i] == 0) System.out.print(i + " ");
		}
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class Main {

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

int code;

int count = 0;

int n[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

while ((code = br.read()) != -1) {

if (code >= 48 && code <= 57) n[code - 48]++;

}

for (int i = 0; i < 10; i++) {

if (n[i] == 0) count++;

}

System.out.println(count);

for (int i = 0; i < 10; i++) {

if (n[i] == 0) System.out.print(i + " ");

}

Решение

Объявим массив на $10$ элементов, в котором будем хранить количество вхождений каждой цифры в номер телефона. Далее, посимвольно читаем входной поток и увеличиваем соответствующие каждой цифре элементы массива на $1$. После этого, находим количество нулевых элементов массива — это будет количество цифр, которые отсутствуют в номере. Наконец, выводим индексы нулевых элементов массива.

Ссылки

Условие задачи на e-olymp
Решение на ideone
Решение на e-olymp

e-olymp 1494. Санта Клаус

23/12/2018 by Томас Пасенченко

Задача

Санта Клаус готовится к Рождеству. В этот праздник он хочет вручить подарки $n$ детям. Его помощники Эльфы уже собрали два мешка, с которыми он отправится в новогоднее путешествие по всем странам мира. И чтобы Санта не запутался, Эльфы составили список детей, чьи подарки уже лежат в каждом из мешков. Санта хочет помочь Эльфам, и поэтому решил положить в третий мешок подарки для тех детей, которым они еще не подготовлены.

Помогите Санте, составьте список детей, чьи подарки надо положить в третий мешок.

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

Первая строка входного файла содержит три целых числа: $n$ — число детей, $m$ и $k$ — число подарков в первом и втором мешке соответственно $(1\leq n,\;m,\;k\leq 100;m+k\leq n)$. Вторая строка входного файла содержит $m$ целых чисел — номера детей, подарки для которых лежат в первом мешке. Третья строка входного файла содержит $k$ целых чисел — номера детей, подарки для которых лежат во втором мешке.

Гарантируется что Эльфы положили для каждого ребенка не более одного подарка. Номера всех детей являются целыми положительными числами не превосходящими $n$. Все дети должны получить подарок на Рождество, иначе Санта расстроится.

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

В первой строке выведите одно число $a$ — сколько подарков должно быть в третьем мешке. Во второй строке выведите в произвольном порядке $a$ чисел — номера детей, которым эти подарки должны быть доставлены.

Тесты

Входные данные	Выходные данные
2 1 1 2 1	0
3 1 2 1 2 3	0
7 2 1 7 3 1	4 2 4 5 6
100 14 4 2 93 30 56 17 19 75 22 23 5 49 11 8 33 91 40 81 54	82 1 3 4 6 7 9 10 12 13 14 15 16 18 20 21 24 25 26 27 28 29 31 32 34 35 36 37 38 39 41 42 43 44 45 46 47 48 50 51 52 53 55 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 76 77 78 79 80 82 83 84 85 86 87 88 89 90 92 94 95 96 97 98 99 100
10 3 5 2 5 8 3 7 1 4 9	2 6 10
61 40 5 61 20 5 3 4 9 8 49 31 20 33 35 34 61 1 32 53 51 7 21 44 46 47 2 60 50 19 25	36 5 6 10 11 12 13 14 15 16 17 18 22 23 24 26 27 28 29 30 36 37 38 39 40 41 42 43 45 48 52 54 55 56 57 58 59
12 3 3 1 2 3 11 10 8	6 4 5 6 7 9 12

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

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();
		int k = scanner.nextInt();
		int num;
		boolean children[] = new boolean[n];
		for (int i = 0; i < n; i++) {
			children[i] = false;
		}
		for (int i = 0; i < m + k; i++) {
			num = scanner.nextInt();
			num--;
			children[num] = true;
		}
		System.out.println(n - m - k);
		for (int i = 0; i < n; i++) {
			if (!children[i]) {
				System.out.print((i + 1) + " ");
			}
		}
	}
}

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();

int k = scanner.nextInt();

int num;

boolean children[] = new boolean[n];

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

children[i] = false;

}

for (int i = 0; i < m + k; i++) {

num = scanner.nextInt();

num--;

children[num] = true;

}

System.out.println(n - m - k);

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

if (!children[i]) {

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

}

Решение

Создадим массив типа boolean , в котором каждому $i$-ому ребёнку соответствует элемент с индексом $i-1$ , принимающий значение $0$, если для ребёнка ещё нет подарка, и $1$, если подарок уже имеется в одном из мешков. Далее, отмечаем детей, подарки для которых уже лежат в мешках. Наконец, выводим номера тех детей, подарки для которых не были найдены ни в одном из мешков.

Ссылки

Условие задачи на e-olymp
Решение на ideone
Решение на e-olymp

e-olymp 7492. Будильник

15/12/2018 by Георгий Мартынюк

Задача

Алиса любит свой цифровой будильник. Она устанавливает его каждый вечер. Прошлой ночью Алисе приснились ее часы. К сожалению, единственное, что она помнит — так это количество отображаемых сегментов на часах. Алиса хочет узнать, какое время показывали ее часы во сне.

Часы Алисы содержат четыре цифры: две для часов и две для минут. Например, часы ниже показывают [latex]9[/latex]:[latex]30[/latex] (ведущий ноль высвечивается).

Часы имеют следующее представление цифр:

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

Одно целое число [latex]n (0≤ n ≤30)[/latex] — количество подсвеченных сегментов на часах Алисы во сне.

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

Вывести пять символов в формате [latex]hh:mm[/latex] — время, показываемое часами Алисы во сне. Время должно быть корректным: [latex]0 ≤ hh < 24[/latex] and [latex]0 ≤ mm < 60[/latex]. Если существует несколько решений, то вывести любое. Если решения не существует, то вывести [latex]Impossible[/latex].

Тесты

Входные данные	Выходные данные
23	00:02
28	Impossible
0	Impossible
15	01:12

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n;
		while (in.hasNextInt()) {
			n = in.nextInt();
			int[] seg = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
			for (int i = 0; i < 24; i++)
				for (int j = 0; j < 60; j++) {
					int a = 0;
					a = a + seg[i / 10];
					a = a + seg[i % 10];
					a = a + seg[j / 10];
					a = a + seg[j % 10];
					if (a == n) {
						if (i < 10) System.out.printf("0%d", i);
						else System.out.print(i);
						System.out.print(":");
						if (j < 10) System.out.printf("0%d", j);
						else System.out.print(j);
						return;
					}
				}
				System.out.print("Impossible");
		}
		in.close();
		return;
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n;

while (in.hasNextInt()) {

n = in.nextInt();

int[] seg = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

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

for (int j = 0; j < 60; j++) {

int a = 0;

a = a + seg[i / 10];

a = a + seg[i % 10];

a = a + seg[j / 10];

a = a + seg[j % 10];

if (a == n) {

if (i < 10) System.out.printf("0%d", i);

else System.out.print(i);

System.out.print(":");

if (j < 10) System.out.printf("0%d", j);

else System.out.print(j);

return;

}

System.out.print("Impossible");

}

in.close();

return;

}

Решение

Перебираем [latex]i[/latex] и [latex]j[/latex] (от [latex]0[/latex] до [latex]24[/latex] и [latex]60[/latex] соответственно). [latex]a=seg[i/10][/latex] (для десятков) и [latex]a=seg[i[/latex]%[latex]10][/latex] (для остальных чисел) то же самое делаем для [latex]j[/latex]. Тем самым, мы перебираем все возможные варианты количества сегментов. Если [latex]a==n[/latex] (количество сегментов) при переборе и в входных данных совпадает, то выводим наше время и выходим из цикла. Если же при переборе не было такого же числа сегментов, как в входных данных, то решения нет и мы, соответственно, выводим Impossible

Ссылки

e-olymp
Ideone

A393a

28/11/2017 by Мазурин Эдвард

Задача:

Даны натуральное число [latex]n[/latex], целочисленная квадратная матрица порядка [latex]n[/latex]. Получить [latex]{b}_{1}[/latex],…,[latex]{b}_{n},[/latex] где [latex]{b}_{i}[/latex] — это наименьшее из значений, элементов находящихся в начале [latex]i[/latex]-й строки матрицы до элемента, принадлежащего главной диагонали, включительно.

Тесты:


Вводимые данные		Предполагаемый вывод	Комментарий
4	4 3 2 1	4 3 2 1	Тест пройден
	4 3 2 1
	4 3 2 1
	4 3 2 1
	1 2 3 4	1 1 1 1	Тест пройден
	1 2 3 4
	1 2 3 4
	1 2 3 4

Решение:

Считываем матрицу и проходим в цикле по каждой строке ведя поиск минимального элемента (но есть одно «Но», поиск ведется под главной диагональю матрицы).
У всех элементов находящихся под главной диагональю матрицы, включительно, индекс строк больше или равен индексу столбцов заданной матрицы. Учтем это при составлении программы.
Осталось только написать код с учетом вышеперечисленных особенностей задачи.

Код:

import java.util.*;

public class multi_arrays {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        System.out.print("Введите n: ");
        int n = in.nextInt();                //Объявление переменной, обозначающей размерность массива
            int[][] a = new int [n][n];      //Создание двумерного массива
        for (int i = 0; i < n; i++) {        
            for (int j = 0; j < n; j++) {
                System.out.print("Заполните массивы элементами: ");
                a[i][j] = in.nextInt();
            }
        }
        for (int i = 0; i < n; i++) {
            int min = a[i][0];
            for (int j = 0; i - j >= 0; j++)  // критерий отбора элементов под главной диагональю
            {
                if (a[i][j] < min) {
                    min = a[i][j];
                }
            }
            System.out.println(min);
        }
    }
}

import java.util.*;

public class multi_arrays {

public static void main(String[] args){

Scanner in = new Scanner(System.in);

System.out.print("Введите n: ");

int n = in.nextInt(); //Объявление переменной, обозначающей размерность массива

int[][] a = new int [n][n]; //Создание двумерного массива

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

for (int j = 0; j < n; j++) {

System.out.print("Заполните массивы элементами: ");

a[i][j] = in.nextInt();

}

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

int min = a[i][0];

for (int j = 0; i - j >= 0; j++) // критерий отбора элементов под главной диагональю

{

if (a[i][j] < min) {

min = a[i][j];

}

System.out.println(min);

}

Версия программы на Ideone.com

Ссылка на источник

Ю 4.24

28/11/2017 by Мазурин Эдвард

Задача:

В массиве каждый элемент, кроме первого, заменить суммой всех предыдущих элементов.


Вводимые данные	Предполагаемый вывод	Комментарий
1 1 1 1 1 1	1 1 2 3 4 5	Тест пройден
1 2 3 4 5 6 7 8 9	1 1 3 6 10 15 21 28 36	Тест пройден
3 5 2 9 0 4 65 156 1	3 3 8 10 19 19 23 88 244	Тест пройден
2 -7 3 8 -4 5 -2 4 2	2 2 -5 -2 6 2 7 5 9	Тест пройден

Код:

import java.util.*;


public class cu_total {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        System.out.print("Введите n: ");
        int n = in.nextInt(); //Объявление переменной, обозначающей размерность массива
        int[] a = new int[n]; //Создание массива
        for(int i=0;i<n;i++){ //Ввод значений элементов массива с помощью цикла
            System.out.print("Заполните массив элементами: ");
            a[i] = in.nextInt();
        }
        int b[] = new int[n]; //Создание дополнительного массива, в котором и будет храниться результат.
        int S=0;              //Создание вспомогательной переменной
        b[0]=a[0];            //Инициализация первого элемента второго массива
        for(int i=1;i<n;i++)  //Преобразование элементов первого массива в элементы второго массива и ввод результата во второй массив
        {
            S+=a[i-1];
            b[i]=S;
        }
        for(int i=0;i<n;i++){
            System.out.println(b[i]);
        }
        System.out.print("\n" + "Тест пройден");
    }
}

import java.util.*;

public class cu_total {

public static void main(String[] args){

Scanner in = new Scanner(System.in);

System.out.print("Введите n: ");

int n = in.nextInt(); //Объявление переменной, обозначающей размерность массива

int[] a = new int[n]; //Создание массива

for(int i=0;i<n;i++){ //Ввод значений элементов массива с помощью цикла

System.out.print("Заполните массив элементами: ");

a[i] = in.nextInt();

}

int b[] = new int[n]; //Создание дополнительного массива, в котором и будет храниться результат.

int S=0; //Создание вспомогательной переменной

b[0]=a[0]; //Инициализация первого элемента второго массива

for(int i=1;i<n;i++) //Преобразование элементов первого массива в элементы второго массива и ввод результата во второй массив

{

S+=a[i-1];

b[i]=S;

}

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

System.out.println(b[i]);

}

System.out.print("\n" + "Тест пройден");

}

Описание:

Простейшие операции с массивом. С помощью цикла записываем данные в массив, после чего, снова с помощью цикла, записываем новые данные во второй массив. Далее выводим результат.

Алгоритм:

Объявление переменной и ввод размерности массива.
Создание массива.
Создание цикла, для записи вводимых данных в массив.
Создание нового массива.
Создание цикла, для ввода обработанных данных в новый массив.
Создание цикла, для вывода результата.
Окончания работы программы.

Работающая версия программы на Ideone.com

Ссылка на источник

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.

Ю4.3

13/07/2017 by Гуменюк Марина

Задача

Центрирование массива. От каждого из заданных чисел [latex]{x}_{1}, {x}_{2}, \ldots, {x}_{m}[/latex] отнять их среднее арифметическое [latex]\overline{x}_{i} = {x}_{i}[/latex] — [latex]{x}_{cp}[/latex], [latex]i = 1, 2[/latex], … , [latex]m[/latex].

[latex]\overline{x}[/latex] = [latex]1/m[/latex];
[latex]E[/latex] от [latex]m[/latex] при [latex]i = 1 (x_1)[/latex];
[latex]{x}_{i}[/latex] = [latex]{x}_{i}[/latex] — [latex]\overline{x}[/latex]; [latex]i = 1, 2[/latex], … , [latex]m[/latex]

Результаты разместить на месте исходных данных.

Тесты

Количество элементов в массиве — m	Массив	Результат
2	2 5	-1,5 1,5
2	2 6	-2 2
7	2 6 -3 5 1 0 0	0.43 4.43 -4.57 3.43 -0.57 -1.57 -1.57

Код

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int m = in.nextInt();//количество элементов в массиве
		double sum = 0; // сумма чисел массива
		
		double[] arr = new double[m];
		for(int i = 0; i < m; i++)
		{
			arr[i] = in.nextDouble();
		}
		
		for (int i = 0; i < m; i++)
		{
			sum += arr[i];//вводим следующее число
		}

		for (int i = 0; i < m; i++)
		{
			arr[i] = arr[i] - (sum / m);//результат
			System.out.println(arr[i]);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int m = in.nextInt();//количество элементов в массиве

double sum = 0; // сумма чисел массива

double[] arr = new double[m];

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

{

arr[i] = in.nextDouble();

}

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

{

sum += arr[i];//вводим следующее число

}

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

{

arr[i] = arr[i] - (sum / m);//результат

System.out.println(arr[i]);

}

Протестированный код можно увидеть тут.

Решение

Объявляем массив типа double размерностью m. Считываем размерность из первой строки ввода, конвертируем из типа string в тип int; затем считываем элементы массива из второй строки ввода (их конвертируем в double — для точности вычислений). В циклах: находим сумму введенных чисел, затем их среднее арифметическое, затем высчитываем новые значения элементов массива, вычитая от каждого из них среднее арифметическое всего массива. Записываем новые значения поэлементно в исходный массив arr[ ]. Выводим arr[ ].

Ю 4.17

03/07/2017 by Присяжный Михаил

Постановка задачи

В массиве [latex]A(n)[/latex] найти и напечатать номера (индексы) локальных максимумов, то есть таких [latex]a_{i}[/latex], что [latex]a_{i-1}<x_{i}>a_{i+1}[/latex].

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

Количество значений и сами значения

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

Индексы локальных максимумов

Тесты

№	Количество значений	Значения	Результат
1	6	2 4 6 1 3 7 5	2
2	7	3 1 6 2 8 5 7	2, 4
3	10	2 5 8 3 5 6 9 7 1 4	2, 6

Решение

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

class Ideone
{
	public static void main (String[] args)
	{
		int n;
		Scanner s = new Scanner(System.in);
		n = s.nextInt();
		double[] x = new double[n];
		for(int i=0; i<n; i++){
			x[i]=s.nextInt();
		}
		for(int j=1; j<=(n-2); j++){
			if((x[j]>x[j+1])&&(x[j]>x[j-1])){
				System.out.println(j + " ");
			}	
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

int n;

Scanner s = new Scanner(System.in);

n = s.nextInt();

double[] x = new double[n];

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

x[i]=s.nextInt();

}

for(int j=1; j<=(n-2); j++){

if((x[j]>x[j+1])&&(x[j]>x[j-1])){

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

}

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Объявляем переменную n для хранения размера массива. Далее создаем массив типа double. Для нахождения локальных максимумов x[i] создаем цикл for, в котором при каждой итерации будем проверять, являются ли значения локальными максимумами. Если значение удовлетворяет условие, выводим на экран индекс этого значения. Например, в первом тесте мы вводим количество значений 6, сами значения 2 4 6 1 3 7 5 и нашим результатом оказывается число с индексом 2, т.е. число 6. Так как числа 4 и 1 меньше 6, наше значение будет удовлетворять условие.

Ю4.32

03/07/2017 by Хоба Юрий

Постановка задачи

Суммы по косой. Просуммировать элементы матрицы [latex]A(n,n)[/latex] по каждой из линий, параллельных главной диагонали. Напечатать полученные суммы.

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

[latex]n[/latex] — размерность матрицы [latex](n\geq 1)[/latex].
[latex]A[/latex] — квадратная матрица.

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

Суммы элементов матрицы [latex]A[/latex] по каждой из линий, параллельной главной диагонали.

Тесты

№	Входные данные		Выходные данные
№	Размерность матрицы [latex](n)[/latex]	Матрица [latex]A[/latex]	Суммы
1	2	[latex]\begin{pmatrix} 3 & 6\\ -7 & -5 \end{pmatrix} [/latex]	-7 -2 6
2	3	[latex]\begin{pmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{pmatrix} [/latex]	7 12 15 8 3
3	4	[latex]\begin{pmatrix} 4 & 1 & -6 & 3\\ 2 & 8 & 19 & 7\\ -8 & -11 & 3 & -13\\ 0 & 2 & 16 & -9 \end{pmatrix} [/latex]	0 -6 7 6 7 1 3

Посмотреть работу программы на примере третьего теста можно на сайте ideone.

Решение

import java.util.*;

class task5
{	
	public static void main (String[] args)
	{
		int n;
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		if (n<1)
		{
			System.out.println("Размерность матрицы не может быть меньше 1.");
			return;
		}

		double[][] matrix = new double[n][n];
		double[] sum = new double [2*n - 1];
		
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				matrix[i][j] = in.nextDouble();
		
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				 sum[(j-i + n-1] += matrix[i][j];
		
		for (int i=0; i<(2*n-1); i++)
			System.out.print(sum[i]+" ");
		
	}
}

import java.util.*;

class task5

{

public static void main (String[] args)

{

int n;

Scanner in = new Scanner(System.in);

n = in.nextInt();

if (n<1)

{

System.out.println("Размерность матрицы не может быть меньше 1.");

return;

}

double[][] matrix = new double[n][n];

double[] sum = new double [2*n - 1];

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

for (int j = 0; j < n; j++)

matrix[i][j] = in.nextDouble();

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

for (int j = 0; j < n; j++)

sum[(j-i + n-1] += matrix[i][j];

for (int i=0; i<(2*n-1); i++)

System.out.print(sum[i]+" ");

}

Описание решения

Сначала объявляем переменную n — размерность матрицы [latex]A[/latex] — и присваиваем ей значение, которое вводит пользователь. Если [latex](n\geq 1)[/latex] — продолжаем работу, иначе выводим сообщение об ошибке и завершаем работу программы.

Теперь, зная размерность матрицы, можем инициализировать 2 массива:

Двумерный массив double[][] matrix = new double[n][n]; размерностью [latex](n\times n)[/latex], который будет содержать в себе значения элементов матрицы [latex]A[/latex];
Массив double[] sum = new double [2*n - 1]; размерностью [latex](2*n-1)[/latex] для хранения сумм диагоналей. Такая размерность обусловлена следующей логикой: главная диагональ матрицы размерностью [latex](n\times n)[/latex] содержит [latex]n[/latex] элементов. Побочная диагональ, находящаяся выше, содержит в себе уже [latex](n-1)[/latex] элементов и т.д., пока элементов в диагонали больше нуля. Становится ясно, что выше главной диагонали находится [latex](n-1)[/latex] побочных диагоналей, еще столько же ниже. Прибавляем еще главную диагональ к этому числу и выводим формулу количества диагоналей у матрицы, параллельных главной: [latex]2(n-1)+1=2n-1[/latex].

Заполняем с помощью двух циклов for массив matrix из потока ввода, а затем в таких же циклах находим суммы элементов требуемых диагоналей ( sum[(j-i) + (n-1)] += matrix[i][j];).

Известно, что индексы [latex]i,j[/latex] элементов главной диагонали матрицы всегда одинаковы. Аналогично можно заметить, что на побочных диагоналях индекс [latex]j[/latex] отличается от индекса [latex]i[/latex] на число — «расстояние» между главной диагональю и рассматриваемой побочной. К примеру, если рассматривать побочную диагональ, находящуюся выше через одну от главной («расстояние» между ними равно 2), то в таком случае [latex]j-i=2[/latex].

И если на главной диагонали разность индексов будет равна 0, на диагоналях выше эта разность будет числом положительным, а на диагоналях ниже — отрицательным, то при попытке обращения к элементу массива sum[j-i] мы неизбежно столкнемся с ошибкой, так как индекс массива не может быть числом отрицательным. Значит, чтобы избежать этого, нам надо прибавить к этому индексу некую константу, чтобы самая нижняя диагональ [latex]n-1[/latex] обладала индексом 0 в массиве sum. Отсюда и формула [latex](j-i+n-1)[/latex].

А170

02/07/2017 by Хоба Юрий

Постановка задачи

Даны натуральные числа [latex]n, a_{1}, a_{2},\ldots, a_{n} (n\geq 4)[/latex]. Числа [latex]a_{1}, a_{2},\ldots , a_{n}[/latex] — это измеренные в сотых долях секунды результаты [latex]n[/latex] спортсменов в беге на [latex]100[/latex] м. Составить команду из четырех лучших бегунов для участия в эстафете [latex]4\times100[/latex], т.е. указать одну из четверок натуральных чисел [latex]i, j, k, l[/latex], для которой [latex]1\leq i\leq j\leq k\leq l\leq n[/latex] и [latex]a_{i}+a_{j}+a_{k}+a_{l}[/latex] имеет наименьшее значение.

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

[latex]n[/latex] — количество бегунов [latex](n\geq 4)[/latex].
[latex]a_{1}, a_{2},\ldots, a_{n}[/latex] — результаты спортсменов в беге на [latex]100[/latex] м.

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

[latex]i, j, k, l[/latex] — номера спортсменов, избранных для команды [latex](1\leq i\leq j\leq k\leq l\leq n)[/latex]

Тесты

№	Входные данные		Выходные данные
№	Количество спортсменов [latex](n)[/latex]	Результаты бега спортсменов	Номера спортсменов, избранных для команды
1	3	2.1 3.7 1.1	[latex]n[/latex] не должно быть меньше 4
2	4	1.4 2.1 0 0.2	Результаты должны быть больше 0
3	6	6.5 4.1 1.2 8 9.1 4.9	1 2 3 6
4	12	2.5 9 14 7.1 1.3 4.9 6.7 1.9 10.01 2.45 0.01 13	5 8 10 11

Посмотреть работу программы на примере четвертого теста можно на сайте ideone.

Решение

import java.util.*;

class task4
{	
	public static int FindMax(double[] resRun, int[] nRun)
	{
		double max = resRun[0];
		int maxN = 0;
		for (int i=1; i<resRun.length; i++)
		{
			if (resRun[i] > max)
			{
				max = resRun[i];
				maxN = i;
			}
		}
		return maxN;
	}
	
	public static void main (String[] args)
	{
		final int teamSize = 4;	//размер отбираемой команды
		int n;		//количество бегунов
		int[] nRun = new int[teamSize];	//номера бегунов
		double[] resRun = new double[teamSize];	//результаты этих бегунов
		
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		if (n < teamSize)
		{
			System.out.println("n не должно быть меньше 4");
			return;
		}
		
		double max = 0;	//результат худшего бегуна в отобранной команде для сравнения с очередным результатом
		int maxN = 0;	//номер (индекс) худшего бегуна в массиве
		for (int i = 0; i < n; i++)
		{
			double a = in.nextDouble();
			if (a <= 0)
			{
				System.out.printf("Результаты должны быть больше 0");
				return;
			}
			
			if (i<teamSize)	//заполяем команду первыми попавшимися бегунами
			{
				nRun[i] = i;
				resRun[i] = a;
				if (i==teamSize-1)
				{
					maxN = FindMax(resRun, nRun);
					max = resRun[maxN];
				}
			}
			
			else if (a < max)	//заменяем бегуна с наихудшим результатом бегуном, с лучшим результатом
			{
				resRun[maxN] = a;
				nRun[maxN] = i;
				maxN = FindMax(resRun, nRun);
				max = resRun[maxN];
			}
		}
		
		Arrays.sort(nRun);
		
		for (int i = 0; i<teamSize; i++)
		{
			System.out.println(nRun[i]+1);
		}
	}
}

import java.util.*;

class task4

{

public static int FindMax(double[] resRun, int[] nRun)

{

double max = resRun[0];

int maxN = 0;

for (int i=1; i<resRun.length; i++)

{

if (resRun[i] > max)

{

max = resRun[i];

maxN = i;

}

return maxN;

}

public static void main (String[] args)

{

final int teamSize = 4; //размер отбираемой команды

int n; //количество бегунов

int[] nRun = new int[teamSize]; //номера бегунов

double[] resRun = new double[teamSize]; //результаты этих бегунов

Scanner in = new Scanner(System.in);

n = in.nextInt();

if (n < teamSize)

{

System.out.println("n не должно быть меньше 4");

return;

}

double max = 0; //результат худшего бегуна в отобранной команде для сравнения с очередным результатом

int maxN = 0; //номер (индекс) худшего бегуна в массиве

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

{

double a = in.nextDouble();

if (a <= 0)

{

System.out.printf("Результаты должны быть больше 0");

return;

}

if (i<teamSize) //заполяем команду первыми попавшимися бегунами

{

nRun[i] = i;

resRun[i] = a;

if (i==teamSize-1)

{

maxN = FindMax(resRun, nRun);

max = resRun[maxN];

}

else if (a < max) //заменяем бегуна с наихудшим результатом бегуном, с лучшим результатом

{

resRun[maxN] = a;

nRun[maxN] = i;

maxN = FindMax(resRun, nRun);

max = resRun[maxN];

}

Arrays.sort(nRun);

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

{

System.out.println(nRun[i]+1);

}

Описание решения

Отличительной особенностью задач из категории «потоковая обработка» является то, что обработка большого объема данных происходит циклически, без их запоминания. То есть, когда пользователь вводит в программу массив значений, программа запоминает очередное значение, обрабатывает его соответствующим образом, а потом заменяет новым поступившим значением. Это дает преимущество в использовании памяти перед программами, которые запоминают весь массив целиком.

Так как по условию размер отбираемой команды — [latex]4[/latex] бегуна ( final int teamSize = 4;), введем ограничение на количество бегунов в целом — их должно быть [latex]4[/latex] или больше, иначе программа выдаст сообщение об ошибке и завершит работу.

Введя количество бегунов n, пользователь после этого будет вводить результат каждого. Программа запоминает этот результат ровно на один шаг цикла ( double a = in.nextDouble();), за который разберется, что с ним делать, а затем заменит следующим результатом.

Так как программа не запоминает весь массив целиком, найти [latex]4[/latex] наименьших значения перебором не получится. Поэтому инициализируем [latex]2[/latex] массива, один из которых ( double[] resRun = new double[teamSize];) будет хранить результаты бегунов, отобранных в команду, а другой ( int[] nRun = new int[teamSize];) — их номера.

Результаты бегунов, отобранных в команду изначально равны нулю; это говорит о том, что еще ни один бегун в команду отобран не был. Результаты и номера первых [latex]4[/latex] бегунов мы запомним в этих массивах, так как иначе мы просто потеряем эти данные и больше не сможем сравнить их со следующими. Теперь, когда 4 бегуна отобраны, следует найти номер бегуна с наихудшим результатом (с помощью функции public static int FindMax(double[] resRun, int[] nRun)). Этот бегун — первый в очереди на замену, если очередной полученный результат вдруг окажется лучшим (меньшим). Следует отметить, что программа будет искать номер наихудшего бегуна лишь в тех случаях, когда этот бегун будет заменен; в ином случае, когда результат очередного бегуна хуже, мы замены в команде не производим, соответственно, худший бегун в команде остается тем же.

Таким образом, с каждым шагом цикла результаты отобранных в команду бегунов становятся либо меньше, либо остаются прежними. После обработки последнего введенного результата, мы получим массив resRun лучших результатов и массив nRun номеров этих бегунов. Остается лишь отсортировать номера бегунов ( Arrays.sort(nRun);), как того требует условие, и вывести их значения.