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

Задача

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

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

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

n, m, x_i, y_i, i = \overline{1, n}, r_j, j = \overline{1, m}

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

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

Тест

Входные данные Выходные данные
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

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

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

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

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

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

Ссылки

Ю4.3

Задача

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

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

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

Тесты

Количество элементов в массиве — 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

Код

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

Решение

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

 

 

Ю 4.17

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

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

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

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

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

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

Тесты

Количество значений Значения Результат
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

Решение

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

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

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

Ю4.32

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

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

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

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

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

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

Тесты

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

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

Решение

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

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

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

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

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

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

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

А170

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

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

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

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

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

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

Тесты

Входные данные Выходные данные
Количество спортсменов (n) Результаты бега спортсменов Номера спортсменов, избранных для команды
1 3 2.1  3.7  1.1 n не должно быть меньше 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.

Решение

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

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

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

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

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

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

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

Ю 4.9

Задача

В матрице A(n, m) все ненулевые элементы заменить обратными по величине и противоположными по знаку.

Тесты

      n        m  Входная матрица              Выходная матрица
     1                     3                         3           6   -2    -1                     0    0     4                    11   2    -3         -0.167     0.500      1.000                  0.000     0.000     -0.250                 -0.091    -0.500      0.333
     2                     3                         4       -3    -9    15   12        -31   -8     2     8           -1     2    -6    -8      0.333   0.111    -0.067   -0.083      0.032   0.125    -0.500   -0.125      1.000  -0.500     0.167    0.125
     3                    4                         3             1   1   1                       1   1   1                       1   1   1                       1   1   1            -1.000  -1.000   -1.000                    -1.000  -1.000   -1.000                    -1.000  -1.000   -1.000                    -1.000  -1.000   -1.000

Решение

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

Пояснения

Объявляем и инициализируем переменные n  и m , которые являются размерами нашей матрицы A. Объявляем нашу матрицу и создаем экземпляр с размерами n x m. Далее создаем цикл по i  от 0 до n-1 в котором создаем вложенный цикл по  j  от 0 до m-1, и в нем поэлементно вводим значения матрицы. В следующем цикле снова создаем вложенный, в котором мы проходим по каждому элементу матрицы и проверяем не равен ли он нулю  if(A[i][j] != 0) . Если условие выполняется, то мы заменяем элемент на обратный и меняем знак. В последнем цикле выводим полученную матрицу, элементы которой будут выводится с точностью до трех символов после запятой.

А694а. Многомерные массивы

Условие
Получить квадратную матрицу порядка \begin{pmatrix}1 &0 &\cdots & 0 \\ 0 & 1 &\cdots &0 \\ \cdots &\cdots &\cdots \cdots & \cdots \\ 0 & 0 & \cdots & 1\end{pmatrix}

Тесты

n Матрица
3 1 0 0
0 1 0
0 0 1
4 1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
6 1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
Решение

  1. С помощью цикла заполняем главную диагональ единицами.
  2. Приравниваем элементы не равные единице к нулю.
  3. Вывод массива.

Iseone.com

e-olymp 19. The degree of symmetry

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

Условие

Степенью симметрии натурального числа назовём количество пар его десятичных цифр, в которых цифры совпадают и расположены симметрично относительно середины десятичной записи этого числа. Если некоторая цифра стоит посередине десятичной записи, её тоже нужно учитывать в паре с ней самой. Найти степень симметрии числа n.

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

Одно натуральное число n < 2\cdot10^9.

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

Вывести степень симметрии числа n.

Тесты:

Ввод Вывод
123322 2
100 1
1010 0
1234321 4
1234567891 1

Код на Java:

Алгоритм:

Вначале считываем число. Затем раскладываем его по цифрам внутри массива (в обратном порядке, но для нашей задачи порядок цифр значения не имеет):

Затем подсчитываем собственно степень симметрии, двигаясь внутри массива от крайних цифр к центру, а после выводим результат:

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

Ю4.15

Заданы массивы A(n) и B(m). Получить массив C(m+n), расположив в начале его элементы массива A, а затем элементы массива B.

Тесты:

n m A[n] B[m] Результат:
3 4 0 1 2 5 7 8 4 A={0 1 2}
B={5 7 8 4}
C={0 1 2 5 7 8 4}
2 9 9 3.6 7.4 3.6 4.6666 7.99702 1 1 1 1 1 A={9 3.6}
B={7.4 3.6 4.6666 7.99702 1 1 1 1 1}
C={9 3.6 7.4 3.6 4.6666 7.99702 1 1 1 1 1}

Код

Решение
Задаем размерности массивов. Вводим их. Затем заполняем массив C элементами сначала из массива A (A элементов), а затем (с A-ого элемента ) — элементами из массива A. Выводим массив C.

Код на ideone.com