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

Задача

Даны действительные числа [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

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

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

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

Из входного потока считываем координаты всех точек, и отсеиваем из них те, у которых координата [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] — полукругов.

Ссылки

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

Задача

Даны целые числа [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
Решение

Воспользуемся рекурсивной реализацией алгоритма Евклида. Пусть  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в

Задача

Даны натуральное число [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

Решение

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

Пояснения

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

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

Задача

Вычислить [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

Решение

Проверить работу кода можно в облаке по ссылке — 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 . По выходу из цикла выводим финальную сумму в консоль.