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

Ссылки

e-olymp 107. Компакт-диски

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

Чистые компакт-диски продают в трёх видах упаковок. Упаковка из 100 дисков стоит 100 грн., из 20 дисков — 30 грн., а один диск стоит 2 грн. Какую минимальную сумму нужно истратить для покупки N таких дисков?

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

Единственное число N — количество дисков. Значение N натуральное, не больше 1000.

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

Искомая минимальная сумма в гривнах.

Тесты

Входные данные Выходные данные
1 0 0
2 163 196
3 238 260
4 298 300

Решение

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

Задача может быть решена по алгоритму «купить максимальное количество упаковок из 100, потом из 20 дисков, а потом докупать по одному диску, чтобы получить требуемые для покупки N дисков». Такой алгоритм можно записать формулой: (N / 100) * 100 + (N \% 100 / 20) * 30 + 2 * (N \% 20).

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

К примеру, если необходимо купить 96 дисков, куда дешевле купить за 100 гривен упаковку, содержащую 100 дисков, чем 4 упаковки по 20 дисков и отдельно еще 16 дисков, что в общей стоимости даст 152 гривны.

Поэтому сперва следует проверить, не будет ли покупка большего количества дисков дешевле. Для этого используются условия if (N % 100 >= 65) и if (N % 20 > 15), где 65 и 15 — лимит количества дисков, при превышении которого покупка упаковок из 100 и 20 дисков соответственно — дешевле.

Посмотреть решение задания можно на сайте e-olymp.

Посмотреть, как работает программа со входными данными 238 можно на сайте ideone.

e-olymp 904. Увеличить на 2

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

Задан одномерный массив A целых чисел. Увеличить на 2 каждый неотрицательный элемент массива.

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

В первой строке задано натуральное число n — количество элементов массива n <= 100. Во второй строке через пробел заданы сами элементы массива, значение каждого из которых по модулю не превышает 100.

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

В единственной строке вывести через пробел n чисел: новые значения элементов массива, в том же порядке, в котором они были заданы.

Код

Тесты

Входные данные Выходные данные
4
1 2 3 4
3 4 5 6
4
1 2 3 -4
3 4 5 -4
4
-1 2 3 4
-1 4 5 6
4
0 2 3 4
2 4 5 6
4
1 2 2 4
4
1 2 2 4

Решение

Вводим число n. Используем цикл for и вводим число a. Выводим неотрицательное число a, либо без изменений, либо увеличенное на два.
e-olymp.com
ideone.com

e-olimp 7365 — Молоко и пирожок

Задача на e-olimp.

Условие

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее 30 кг. В первых классах школы учится n учеников. Стакан молока имеет емкость 200 мл, а упаковки молока – 0,9 л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

Решение

Возьмем количество пирожков за счетчик. Используя for найдем количество пирожков для детей, вес которых не превышает 30кг. По количеству пирожков мы можем найти количество упаковок молока. При этом мы можем получить не целое число. Чтобы избежать этого, используем метод ceil из класса Math для округления до целого.

Код

Ссылка на Ideone.

Тест

Входящие данные Выходящие данные
n w(вес) pack pie
4 30 29 40 25 1 2
7 21 20 22 29 26 27 26 2 7

Проверка решения на e-olimp.

e-olymp 388. Превращение

Задача на e-olimp.

Условие

Возьмем какое-нибудь натуральное число N. Будем изменять его следующим образом: если число четное, то разделим его на 2, если нечетное, прибавим 1. После нескольких таких изменений мы всегда получаем число 1. Например, из числа 11 получается число 12, затем 6, 3, 4, 2 и, наконец, 1. Таким образом, для получения 1 из 11 нужно проделать 6 изменений.

Напишите программу, которая считывает натуральное число и выводит количество изменений данного числа до получения 1.

Число N (1  ≤ N  ≤  109).

Решение

Пусть N – это число, которое мы будем изменять, а counter – количество превращений. Цикл должен выполняться до того момента, пока N \neq 1. Чтобы проверить число на чётность/нечётность, делим его по модулю и сравниваем остаток с нулём. Если число – чётное, то делим его на 2, в противном случае – добавляем единицу, и при выполнении каждого действия, увеличиваем количество превращений на 1.

Код на Ideone.

 Тест

Входные данные Выходные данные
-5 Wrong number
1 0
6 4

Ссылка на решение на e-olimp.

А58а

Задача. Дано действительное число a. Для функции f\left(x \right), график которой изображен, вычислить f\left(a \right).

58a

Для решения данной задачи требуется лишь проверка знака числа a. Если a> 0, то f\left(a \right) вычисляется как -a^{2}, а если a< 0, то f\left(a \right) равна  -a. При a=0f\left(a \right)=0.

Код на Ideone.

Тест

 Входные данные  Выходные данные
 -7 7
 7  -49
 0  0