Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 149 150 151 152 153 154 155 >> Отображать по:
#1575
Пиратские сокровища
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В руки одного искателя приключений попал старинный пиратский манускрипт. В рукописи сказано: "Придя на восходе солнца в точку \(A\), я начал свой путь по острову в поисках надежного места, чтобы спрятать сокровища. Я шел не спеша, все время с одинаковой скоростью в том направлении, куда показывала моя тень. Двигаясь таким образом, через \(N\) часов я вышел к руинам какого-то древнего храма, у северо-западного угла которых я и закопал свои сокровища. Вернувшись на корабль к заходу Солнца я с удивлением обнаружил, что в этот день от восхода Солнца до его захода прошло ровно 12 часов, причем Солнце взошло точно на востоке, а село точно на западе."

Искатель приключений, конечно же пожелал найти сокровища. Тем более, что число N ему было известно, а изображение точки A на карте прекрасно сохранилось. Единственная проблема – на острове оказалось слишком много разных руин, и исследовать их все займет очень много времени.

Напишите программу, которая по описанию острова определит список руин, наличие клада у которых наиболее вероятно. При решении задачи будем считать что угловая скорость Солнца над горизонтом постоянна (то есть за одно и то же время Солнце проходит один и тот же угол).

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

сначала вводится число \(N\) (натуральное, не превышает 11), затеем число \(k\) (натуральное, не превышает 100). Далее следует k строк по 3 числа в каждой – координаты и радиус соответствующих руин (целые, по модулю не превышают 1000). Гарантируется что никакие руины не перекрываются. Координатная плоскость организована таким образом: за начало координат принята точка \(A\), ось \(O_Y\) направлена с юга на север, ось \(O_X\) направлена с запада на восток.

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

выведите список руин, в которых следует искать клад, упорядоченный по удаленности от точки \(A\). В списке следует выводить только координаты руин, по одному объекту в строке. Гарантируется, что на острове существуют хотя бы одни искомые руины.

Примеры
Входные данные
6 3
-100 0 10
0 100 10
-50 50 20
Выходные данные
-50 50
#1576
Создание архива
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Системный администратор вспомнил, что давно не делал архива пользовательских файлов. Однако, объем диска, куда он может поместить архив, может быть меньше чем суммарный объем архивируемых файлов.

Известно, какой объем занимают файлы каждого пользователя.

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

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

сначала вводится число \(S\) – размер свободного места на диске (натуральное, не превышает 10000), затем следует число \(N\) – количество пользователей (натуральное, не превышает 100), после этого идет \(N\) чисел - объем данных каждого пользователя (натуральное, не превышает 1000).

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

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

Примеры
Входные данные
100 2
200
50
Выходные данные
1
Входные данные
100 3
50
30
50
Выходные данные
2
#1579
Простое обогащение
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Один из самых простых способов обогащения предложили писатели-фантасты. Он заключается в следующем: берем исправную машину времени и с ее помощью отправляемся в прошлое на несколько веков. Там помещаем небольшую (но лучше все-таки побольше) сумму денег в банк под сколько-то процентов годовых. Потом возвращаемся в настоящее, идем в филиал сохранившегося банка и предъявляем ценные бумаги к оплате.

Напишите программу, которая вычислит сумму на счете, скопившуюся за \(N\) (натуральное, не превышает 2000) лет при 10% годовых при начальном взносе равном \(X\) (натуральное, не превышает \(10^6\)). Проценты начисляются следующим образом: по прошествии каждого года к сумме, находящейся на счете, прибавляется 10% от нее, округленные до целого в меньшую сторону.

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

сначала вводится число \(X\), затем число \(N\).

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

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

Примеры
Входные данные
1 1000
Выходные данные
1
Входные данные
10 2
Выходные данные
12
#1613
Разрезать четырехугольник
  

Дан выпуклый четырехугольник ABCD с ненулевой площадью. Найти точку O, принадлежащую какой-либо стороне четырехугольника, что площади фигур, полученных в результате разреза исходного четырехугольника по линии AO, были бы равны.

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

вводятся координаты 4 точек (целые, по модулю не превышают 100). Гарантируется, что никакие три точки не лежат на одной прямой.

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

вывести координаты точки O с точностью до 4 знака после запятой.

Примеры
Входные данные
0 0 
1 1 
0 2
-1 1
Выходные данные
0 2
#1615
Замена робота
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан новый промышленный робот, максимальный срок службы которого не ограничен. Однако, все механизмы со временем теряют свою ценность, производительность и требуют больше затрат на ремонт. Известно, что затраты на обслуживание робота в \(i\)-м году от начала эксплуатации составляют \(C_i\), прибыль, которую приносит робот за \(i\)-й год своей работы составляет \(P_i\). Также в конце любого года можно продать старого робота и купить нового. Цена нового робота не зависит от времени и равна \(S\). Цена подержанного робота, прослужившего \(i\) лет равна \(R_i\). Определите оптимальный график замены роботов в течение \(N\) лет (то есть чтобы суммарная прибыль от использования была максимальна).

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

в первой строке вводятся числа \(N\) – расчетный период времени (натуральное, не превышает 100) и \(S\) (натуральное, не превышает \(10^5\)) – цена нового робота. В следующей строке указано \(N\) чисел (натуральные, не превышают 500) – затраты на обслуживание робота в течение соответствующего года. В следующей строке следует еще \(N\) чисел (натуральные, не превышают 500) - прибыль, которую приносит робот в соответствующие годы, затем еще \(N\) чисел (натуральные, не превышают 500) – цена подержанного робота, в зависимости от возраста.

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

Выведите максимальную прибыль, которую можно получить к концу \(N\)-го года, при оптимальной смене роботов.

Обратите внимание: рассматривается только операция замены робота. То есть если в конце \(N\)-го года вы решите продать робота, то это означает автоматическую покупку нового. То есть робот, проданный после расчетного периода чистой прибыли не приносит.

Комментарий

если робот работает 2 года без замены, то он приносит прибыли на 100+95=195 и требует 2+3=5 на обслуживание; если мы решим в конце 1-го года заменить робота на нового, то мы получим: 100+100=200 (новый робот будет приносить прибыль 100, так как работает 1-й года) + 90 (выручка от продажи старого робота) мы потеряем: 2+2=4 (новый робот также будет требовать затрат за свой первый год) -100 – уплатим за нового робота итого +200+90-100-4=186. Следовательно, первый вариант предпочтительнее

Примеры
Входные данные
2 100
2 3 
100 95
90 80
Выходные данные
190
Страница: << 149 150 151 152 153 154 155 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест