---> 56 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Совсем недавно появилась в продаже новая компьютерная игра «Морской бой—3». Вася купил себе эту игру и теперь играет в нее в свободное от занятий время. Особенно ему нравится в одной из миссий управлять самолетом. Изначально самолет находится на палубе неподвижного авианосца и готов в любой момент к взлету. Задача игрока в этой миссии состоит в уничтожении $N$ кораблей противника. После уничтожения всех кораблей самолет должен вернуться обратно на авианосец.

Для простоты будем считать плоской поверхность моря, где располагается авианосец. Введем прямоугольную декартову систему координат и разместим авианосец в начале координат. Каждый из кораблей в начальный момент игры находится в некоторой точке ($x$, $y$), и сразу после начала игры движется равномерно и прямолинейно так, что его вектор скорости равен ($V_x$, $V_y$).

Конструктивные особенности самолета таковы, что он может двигаться с любой скоростью, не превосходящей $U$. Для того, чтобы сбросить бомбу, которая была специально придумана для этой игры, самолету необходимо находиться непосредственно над кораблем. Корабли считаются точками, т.е. размером кораблей можно пренебречь. Считается также, что самолет может мгновенно взлететь с палубы авианосца, и время падения бомбы на цель равно нулю.

Требуется написать программу, определяющую минимальное время, за которое игрок сможет уничтожить все корабли и возвратить самолет обратно на авианосец.

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

Первая строка входного файла содержит число $N$, определяющее количество кораблей (1 $\le$ $N$ $\le$ 9). Вторая строка входного файла содержит целое число $U$ (1 $\le$ $U$ $\le$ 10000), задающее скорость самолета в метрах в секунду. Последующие $N$ строк описывают все корабли. Каждая строка содержит четыре целых числа $x$, $y$, $V_x$, $V_y$, не превосходящих 10000 по модулю и определяющих начальные координаты и скорость корабля, соответственно. Координаты кораблей заданы в метрах, скорости — в метрах в секунду.

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

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

В первой строке выходного файла выведите минимальное время, требуемое на выполнение миссии. Требуемая точность — не менее $10^{−3}$.

Примеры
Входные данные
1
1000
10 10 0 0
Выходные данные
0.0282842712474619
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

На клетчатом поле $N\times N$, некоторые клетки которого закрашены, требуется найти размер максимального квадрата, состоящего из закрашенных клеток.

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

В первой строке входного файла содержится единственное целое число $N$ ($1\le N\le 3\,000$). В каждой из следующих $N$ строк содержится по $N$ символов «#» и «.» (соответствующих закрашенным и незакрашенным клеткам соответственно), описывающих таблицу.

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

Выведите единственное целое число — максимальный размер полностью закрашенного квадрата.

Система оценки

Каждая программа тестируется на четырёх тестах:

чтобы пройти первый тест, достаточно написать решение, работающее за $O(N^5)$, чтобы пройти второй, требуется решение уже за $O(N^4)$, третий — за $O(N^3)$, четвёртый — за $O(N^2\log N)$.

За каждый успешно пройденный тест начисляется 25 баллов.

Посылка, набирающая $x$ баллов по сумме баллов за тесты, считается принятой, если выполняются следующие два условия:

* во-первых, если $x>25$, должна существовать более ранняя принятая посылка, балл за которую по сумме баллов за тесты равен $x-25$,

* во-вторых, программа не должна содержать отсечений по $N$, искусственных замедлений работы и т. п.

Если посылка не принята, через некоторое время после её отправки результат её проверки станет «Дисквалифицирован». Балл за принятую попытку вычисляется как сумма баллов за каждый тест минус 5 баллов за каждую более раннюю дисквалифицированную посылку.

Задача считается решённой, если существует принятая посылка, получившая не менее 100 баллов.

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

ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось $n$ дипломов, причём, как оказалось, все они имели одинаковые размеры: $w$ — в ширину и $h$ — в высоту. Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером $w$ на $h$. Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек. Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

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

Входной файл содержит три целых числа: $w$, $h$, $n$ ($1\le w,h,n\le 10^9$).

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

В выходной файл необходимо вывести ответ на поставленную задачу.

Иллюстрация к примеру
Примеры
Входные данные
2 3 10
Выходные данные
9
Входные данные
1 1 1
Выходные данные
1
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. На то, чтобы довезти кружки от завода-изготовителя до ЛКШ, остаётся всего 24 часа.

Заказ на 10000000 экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения?

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

В первой строке находятся числа n (1≤n≤500) и m - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих m строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами. 

Узловые пункты нумеруются числами от 1 до n. При этом завод по производству кружек имеет номер 1, а ЛКШ - номер n. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик -  3 тонны.

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

Выведите одно число - максимальное количество кружек, которое можно привезти за первый рейс, потратив не более 24часов.

Примеры
Входные данные
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
Выходные данные
2
Бинпоиск по углу. Пересекаем бублики и ГМТ из которых какие-нибудь две овцы видны под зафиксированным углом.

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