Каталог по темам

Задачи

Страница: 1 [Всего задач: 3]

Задача 102893

[Выгодней некуда ]

Тема:

[

Двоичный поиск

]

Сложность: 3

В стране N городов, в каждом из которых есть аэропорт. Авиакомпания, занимающаяся перевозкой грузов, имеет самолет и желает максимально выгодно его использовать. Для некоторых пар городов (A, B) известны время перелета из A в B и сумма выручки за доставку груза из A в B. Напишите программу, которая по этим данным находит для самолета замкнутый путь, максимизирующий среднюю выручку за единицу времени.

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

Входные данные
В первой строке входного файла содержится число городов N (1 ≤ N ≤ 100) и число возможных прямых рейсов M. В каждой из следующих M строк записана четверка чисел (i, j, b_ij, c_ij), описывающая возможный рейс между городами i и j со временем перелета b_ij и выручкой c_ij . Время перелета и выручка – положительные вещественные числа.

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

Пример входного файла
3 3
1 2 1.0 2.0
2 3 1.0 2.0
3 1 2.0 1.0

Пример выходного файла
1.25
1 2 3 1

Прислать комментарий Решение

Задача 98694

[Сплочённая команда]

Темы:	[	Сортировка	]
Темы:	[	Двоичный поиск	]

Сложность: 3
Классы: 8,9,10,11

Максимальное время работы на одном тесте: 1 секунда

Максимальный объем используемой памяти: 64 мегабайта

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

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

Формат входных данных

В первой строке входного файла e.in записано целое число N (0 £ N £ 30000). В последующих N строках записано по одному целому числу P_i (0 £ P_i £ 60000), представляющему собой ПП соответствующего игрока.

Формат выходных данных

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

Примеры

e.in	e.out
4 1 5 3 3	3 11 2 3 4
5 100 20 20 20 20	2 120 1 2

Прислать комментарий

Решение

Задача 98792

[Не составляемое число]

Темы:	[	Прочие задачи на сообразительность	]
Темы:	[	Двоичный поиск	]

Сложность: 3

Задан массив натуральных чисел P[1:n]. Найти минимальное натуральное число, не представимое суммой никаких элементов массива P. Сумма может состоять и из одного слагаемого, но каждый элемент массива может входить в неё только один раз.

Прислать комментарий

Решение

Страница: 1 [Всего задач: 3]