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 — полукругов.

Ссылки

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

Задача

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

Тесты

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

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

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

А136в

Задача

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

Тесты

     n a_1,\ldots, a_n Результат
 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

Решение

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

Пояснения

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

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

Задача

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

Тесты

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

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

Решение

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

Пояснения

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