---> 101 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
В прямоугольном зале с круглыми колоннами (координаты и радиусы колонн заданы) необходимо разместить круглый фонтан максимального радиуса.

Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером $X$×$Y$ метров. Однако когда дизайнер стал выбирать место для фонтана, он столкнулся с серьезной проблемой: в холле института обнаружилось $N$ круглых колонн, снести которые не представляется возможным.

Таким образом, у него появилась проблема: где следует поместить фонтан, чтобы он имел максимально возможный радиус и не имел ненулевого по площади пересечения с колоннами. Вам предстоит помочь ему в решении этой нелегкой задачи.

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

В первой строке входных данных содержатся вещественные числа $X$ и $Y$, 1 <= $X$, $Y$ <= $10^4$ . Будем считать, что прямоугольник холла расположен на координатной сетке так, что его углы имеют координаты (0, 0), ($X$, 0), ($X$, $Y$) и (0, $Y$).

Во второй строке задается число $N$ (0 <= $N$ <= 10) - количество колонн. Следующие $N$ строк содержат параметры колонн - $i$-я строка содержит три вещественных числа $X_i$, $Y_i$ и $R_i$ - координаты центра и радиус $i$-й колонны ($R_i$ <= $X_i$ <= $X$-$R_i$, $R_i$ <= $Y_i$ <= $Y$-$R_i$, 0.1 <= $R_i$ <= min($X$ / 2, $Y$ / 2); для любых $i$ ≠ $j$ sqrt( ($X_i$ - $X_j$)2 + ($Y_i$ - $Y_j$)2 )>= $R_i$ + $R_j$). Все вводимые числа разделены пробелами.

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

Выведите три вещественных числа: $X_F$, $Y_F$ и $R_F$ - координаты центра и радиус фонтана. Фонтан должен быть полностью расположен внутри холла (допускается касание стен) и не иметь ненулевого пересечения ни с одной из колонн (допускается касание). Радиус фонтана должен быть максимален. Разделяйте числа пробелами и/или переводами строки. Если решений несколько, выведите любое из них.

Примеры
Входные данные
10 10
0
Выходные данные
5.000 5.000 5.000
Входные данные
1 1000
0
Выходные данные
0.500 0.500 0.500
Входные данные
10 10
4
1 1 1
9 9 1
1 9 1
9 1 1
Выходные данные
5.000 5.000 4.657
Для N человек известно 3 параметра: время надувания шарика, сколько шариков можно надуть до отдыха и время отдыха. Требуется определить, за какое минимальное время эти люди надуют N шариков.

Организаторы детского праздника планируют надуть для него $M$ воздушных шариков. С этой целью они пригласили $N$ добровольных помощников, $i$-й среди которых надувает шарик за $T_i$ минут, однако каждый раз после надувания $Z_i$ шариков устает и отдыхает $Y_i$ минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).

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

В первой строке входных данных задаются числа $M$ и $N$ (0 <= $M$ <= 15000, 1 <= $N$ <= 1000). Следующие $N$ строк содержат по три целых числа - $T_i$, $Z_i$ и $Y_i$ соответственно (1 <= $T_i$, $Y_i$ <= 100, 1 <= $Z_i$ <= 1000).

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

Выведите в первой строке число $T$ - время, за которое будут надуты все шарики. Во второй строке выведите $N$ чисел - количество шариков, надутых каждым из приглашенных помощников. Разделяйте числа пробелами. Если распределений шариков несколько, выведите любое из них.

Примеры
Входные данные
2 2
1 1 1
1 1 1
Выходные данные
1
1 1 
Входные данные
3 2
2 2 5
1 1 10
Выходные данные
4
2 1 
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано N отрезков провода длиной L1, L2, ..., LN сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.

Ограничения: 1 <= N <= 10 000, 1 <= K <= 10 000, 100 <= Li <= 10 000 000, все числа целые.

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

В первой строке находятся числа N и К. В следующих N строках - L1, L2, ..., LN, по одному числу в строке.

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

Вывести одно число - полученную длину отрезков.

Примеры
Входные данные
4 11
802
743
457
539
Выходные данные
200
Заданы начальные координаты и скорости кораблей на плоскости. Есть бомбы, уничтожающие корабли на расстоянии не превышающем R от центра взрыва. Взрывать бомбы можно только в целые моменты времени. Требуется уничтожить все корабли наименьшим количеством бомб.

N вражеских кораблей движутся прямолинейно с постоянными скоростями. Вакуумная бомба уничтожает все объекты в радиусе R от точки взрыва (то есть все объекты, расстояние от которых до точки взрыва не больше R). Взрывать бомбу можно только в целые моменты времени.

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

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

В первой строке входных данных задаются целые числа N (2 <= N <= 10) и R (0 < R ≤ 50. В следующих Nстроках  содержится по 4 числа, описывающих движение кораблей. Первые два числа строки – координаты корабля в момент времени 0, по модулю не превосходящие 105. Следующие два числа – значения координат вектора скорости, по модулю не превосходящие 1000. Все эти числа целые.

Гарантируется, что никакие 2 корабля не имеют одинаковые векторы скорости.Однако вполне возможно, что в какой-то момент времени два корабля пройдут через одну точку.

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

В первой строке выведите одно число – минимальное количество взрывов K. В следующих K строках для каждого взрыва выведите по три числа: целое время взрыва и вещественные координаты взрыва, указанные с точностью не менее трех значащих цифр после точки. Разрешается производить взрывы как в разные, так и в один и тот же момент времени. Разрешается взрывы производить как в различных точках, так и в одной точке в разные моменты времени.

Если решений несколько, выведите любое из них.

Комментарий. Решения, верно работающие при N ≤ 3, будут набирать не менее 50 баллов.

Примеры
Входные данные
3 3
-3 3 1 0
0 -6 0 2
-8 6 4 -1
Выходные данные
1
3 2.000 1.500
Входные данные
2 1
-4 -4 2 2
2 2 -2 -2
Выходные данные
2
0 -4.0000 -4.0000
0 2.0000 2.0000
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Дано два массива. Для каждого элемента второго массива определите, сколько раз он встречается в первом массиве.

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

Первая строка входных данных содержит одно число N (1 ≤ N ≤ 105) – количество элементов в первом массиве. Далее идет N целых чисел, не превосходящих по модулю 109 – элементы первого массива, Далее идет количество элементов M во втором массиве и M элементов второго массива с такими же ограничениями.

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

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

Примеры
Входные данные
3
1 2 1
4
0 1 2 3

Выходные данные
0 2 1 0 

Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест