Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#864
Медиана объединений
  
Дано N последовательностей. Требуется для каждой пары последовательностей найти медиану объединения этих последовательностей.

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

Напишите программу, которая для каждой пары последовательностей выведет левую медиану их объединения.

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

Сначала вводятся числа N и L (2≤N≤100, 1≤L≤300). В следующих N строках задаются последовательности. Каждая последовательность состоит из L чисел, по модулю не превышающих 30000.

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

В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N‑1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Пример 

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

3 6

1 4 7 10 13 16

0 2 5 9 14 20

1 7 16 16 21 22
	

	

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

7

10

9
#1113
Интересные числа
  
Источники: [ Командные олимпиады, ВКОШП, 2008, Задача F ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Роман коллекционирует числа, кажущиеся ему интересными. Например, сейчас он считает интересным положительные числа, запись которых в системе счисления с основанием k заканчивается нечетным числом нулей. Например, при k = 2 такими числами являются 210 = 102, 2410 = 110002.

Для того, чтобы пополнить свою коллекцию, Роман хочет найти n-ое в порядке возрастания такое число. Поскольку n он взял достаточно большим, то вручную у него это сделать не получается. Помогите Роману — напишите программу, которая найдет число, которое нужно ему для пополнения коллекции.

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

Первая строка входного файла содержит два целых числа (1 ≤ n ≤ 1015, 2 ≤ k ≤ 10).

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

В выходной файл выведите n-ое в порядке возрастания число, запись которого в системе счисления с основанием k заканчивается на нечетное число нулей. Это число необходимо вывести в десятичной системе счисления.

Примеры
Входные данные
1 2
Выходные данные
2
Входные данные
10 10
Выходные данные
110
#1116
Архимедова спираль
  
Источники: [ Командные олимпиады, ВКОШП, 2008, Задача I ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Дима недавно поступил на работу в НИИ Плоских Кривых. Как следует из названия этого научно- исследовательского института, он занимается различными исследованиями в области плоских кривых. Недавно Димин начальник Георгий столкнулся с весьма интересной кривой, которая, как выяснилось после некоторого исследования, известна под названием Архимедовой спирали. Архимедова спираль плоская кривая, изображающая траекторию точки M, которая равномерно движется вдоль луча OK с началом в O, в то время как сам луч OK равномерно вращается вокруг точки O (см. рисунок). Другими словами, расстояние до начала координат ρ = OM линейно зависит от угла поворота φ луча OK. При этом повороту луча OK на один и тот же угол соответствует одно и то же приращение расстояния ρ.

Движение точки M можно задать с помощью ряда параметров:

• начального угла поворота α луча OK (измеряется в градусах против часовой стрелки относительно положительного направления оси OX);

• угловой скорости вращения ω луча OK (измеряется в градусах за единицу времени);

• начального расстояния R от точки M до начала координат (точки O);

• скорости движения V точки M по лучу OK.

Если, задав эти параметры, не ограничить время движения точки M, то получится бесконечная кривая, исследовать которую достаточно трудно. Поэтому Дима решил ограничиться исследованием некоторой части этой кривой той, которая получается при движении точки M от нулевого момента времени до момента времени T. Задача, которую решает Дима состоит в поиске прямоугольника минимальной площади со сторонами, параллельными осям координат, в который ее можно вписать.

Требуется написать программу, которая найдет искомый прямоугольник

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

Входной файл содержит четыре целых числа: ω (1 ≤ ω ≤ 100), V (1 ≤ V ≤ 100), R (0 ≤ R ≤ 100) и T (1 ≤ T ≤ 1000). В этой задаче считается, что начальный угол поворота α равен нулю.

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

В первой строке выходного файла выведите два вещественных числа — координаты левого нижнего угла искомого прямоугольника, а во второй строке — координаты правого верхнего угла искомого прямоугольника.

Ответ будет считаться правильным, если значение каждой из координат будет отличаться от истинного значения не более чем на 10-5.

Примеры
Входные данные
60 10 0 18
Выходные данные
-150.3028434716 -165.2754877824
180.0000000000 135.3362037333
#1125
Минимальный прямоугольник
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Даны координаты N клеток. Необходимо определить координаты минимального прямоугольника, со сторонами, параллельными осям, покрывающего все клетки.

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

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

Во входном файле, на первой строке, находится число K(1 ≤ K ≤ 100). На следующих K строках находятся пары чисел Xi и Yi – координаты закрашенных клеток (|Xi|, |Yi| ≤ 109).

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

Выведите в выходной файл координаты левого нижнего и правого верхнего углов прямоугольника.

Примеры
Входные данные
3
1 1
1 10
5 5
Выходные данные
1 1 5 10
#1126
Трамвайная остановка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
На прямой расположены остановки с заданными координатами. Заданы скорость трамвая и мальчика. Требуется найти минимальное расстояние L до первой остановки, на которое мальчик должен видеть приближение трамвая так, чтобы трамвай не обогнал его между остановками.

Трамвайная линия имеет вид прямой. Петя живет в N трамвайных остановках от метро. Метро находится у нулевой остановки, в точке с координатой 0.


Выходя из метро, Петя хочет попасть домой как можно быстрее, но он очень не любит ждать трамвай на остановке. Поэтому, если, подходя к очередной трамвайной остановке, он не видит трамвая, то идет пешком вдоль трамвайной линии. Если в какой-то момент Петя видит трамвай, то он может принять решение вернуться на остановку, или продолжить свое движение к следующей остановке. Петя идет со скоростью U, трамвай едет со скоростью V. Нужно найти минимальное расстояние L, которое должно просматриваться перед нулевой остановкой, чтобы он мог идти со своей скоростью в сторону дома, не опасаясь, что трамвай его обгонит между остановками.

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

Во входном файле находятся три числа N, U и V (N ≤ 1000, U и V – положительные вещественные), за которым будет следовать N вещественных чисел – X1, X2,... Xn (0 < X1 < X2 < … < Xn < 106), разделенных пробелами.

 

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

В выходной файл ваша программа должна вывести число L с точностью до 10-4.

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