3 / 3 / 4
Регистрация: 09.01.2013
Сообщений: 20
1

Задача про автомобиль

12.01.2013, 20:02. Показов 2153. Ответов 2
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Вообщем, задача одна не из лёгких, во всяком случае для меня. Для тех, кто любит поломать голову и посидеть подумать. Пробовал решить, увы, своих сил мало. И да, задача олимпиадная. Кому интересно: USACO 2004-2012\Bronze\10_MarB - "Need For Speed"

Итак, само условие:
Беси готовит свой автомобиль к предстоящему Гран-При, но она хочет
купить некоторые детали, чтобы повысить производительность. В
настоящее время ее автомобиль имеет массу M (1 <= M <= 1,000) и
способен двигать себя вперед с силой F (1 <= F <= 1,000,000). В
магазине есть N (1 <= N <= 20) частей последовательно
пронумерованных от 1 до N. Беси может купить любое количество частей
но не более чем по одному экземпляру каждого вида.

Часть P_i добавляет силу F_i (1 <= F_i <= 1,000,000) и имеет массу
M_i (1 <= M_i <= 1,000). Второй закон Ньютона гласит, что F = M * A,
Где F - сила, M - масса, A - ускорение.

Если Беси хочет максимизировать общее ускорение своего гоночного
автомобиля (и минимизировать массу другими словами), какие
дополнительные части она должна купить?

Рассмотрим авто с начальными значениями F=1500 и M=100.
Пусть имеется четыре вида частей для улучшения

i F_i M_i
1 250 25
2 150 9
3 120 5
4 200 8
Добавив только часть 2, мы получим ускорение
(1500+150)/(100+9) = 1650/109 = 15.13761.

Ниже приведена таблица показывающая результирующее ускорение для
всех возможных комбинаций добавления/не добавления четырех частей (в
первой колонке 1 часть добавляется, 0 - часть не добавляется).

Части Суммарная Суммарная
1234 F M F/M
0000 1500 100 15.0000
0001 1700 108 15.7407
0010 1620 105 15.4286
0011 1820 113 16.1062
0100 1650 109 15.1376
0101 1850 117 15.8120
0110 1770 114 15.5263
0111 1970 122 16.1475 <-- highest F/M
1000 1750 125 14.0000
1001 1950 133 14.6617
1010 1870 130 14.3846
1011 2070 138 15.0000
1100 1900 134 14.1791
1101 2100 142 14.7887
1110 2020 139 14.5324
1111 2220 147 15.1020
таким образом, наилучший вариант добавления - комбинация частей 2,3 и 4.

PROBLEM NAME: boost

INPUT FORMAT:

* Строка 1: Три разделенных пробелами целых числа: F, M, N

* Строки 2..N+1: Строка i+1 содержит два разделенных пробелами
целых числа: F_i M_i

SAMPLE INPUT (файл boost.in):

1500 100 4
250 25
150 9
120 5
200 8

OUTPUT FORMAT:

* Строки 1..P: Номера дополнительных частей, по одному в строке,
которые Бесси должна добавить. Если ничего добавить не
выгодно, выводите NONE. Вывод нужно выполнять в порядке
возрастания. То есть если выгодно купить части (2 4 6 7)
то можно выводить в порядке 2 4 6 7 и нельзя например
в порядке 4 2 7 6.

SAMPLE OUTPUT (файл boost.out):

2
3
4

OUTPUT DETAILS:

Бесси должна добавить части 2 3 4 чтобы максимизировать ускорение
своего авто.
Можете целое решение не писать, а просто дать мысль, как решать.

Также могу предоставить тесты для данной задачи.

Заранее спасибо.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.01.2013, 20:02
Ответы с готовыми решениями:

Создать иерархии наследования: автомобиль - легковой автомобиль, грузовой автомобиль – внедорожник
Создать иерархии наследования: автомобиль - легковой автомобиль, грузовой автомобиль – внедорожник.

задачка про автомобиль
Автомобиль движется со скоростью 60 км/ч. Внешний диаметр покрышек колес равен 60 см. Найти...

Найти информацию про самый дешевый автомобиль, выпущенный не ранее заданого года (файловый ввод/вывод)
Ребята, помогите написать программу! Задан файл с информацией про автомобили: Марка, стоимость,...

Задача про взлом кода из книги Эрика Фримена про основы javascript в конце 5 главы.
читаю книгу Эрика Фримена про основы javascript.В конце 5 главы есть задачка про взлом кода.Никак...

2
1 / 1 / 1
Регистрация: 18.03.2012
Сообщений: 29
12.01.2013, 20:06 2
Задача не такая сложная. Т.к n <= 20, можно перебрать битмаску. По этой битмаске считаем ускорение, которое получим и из них выбираем максимальное - ПРОФИТ!
0
63 / 63 / 77
Регистрация: 22.11.2012
Сообщений: 241
Записей в блоге: 1
12.01.2013, 23:05 3
Расчитываете коэффициент КПД детали к ёё массе, и в соответствии с коэффициентом детали находите самую подходящую.
0
12.01.2013, 23:05
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.01.2013, 23:05
Помогаю со студенческими работами здесь

Класс: Задача состоит в том, чтобы уметь сортировать по разным параметрам объекты класса автомобиль.
Сталкнулся с такой наверное обычной задачей. но нформации понятной мне в интеренте не нашел. Имею...

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он...

Задача про IP
Простите что не совсем в тему , но у меня ответ 97.15.81.53/15 , но говорят это неправильно ...

Задача про карты
Здравствуйте! Помогите пожалуйста проверить решение. Задание: дано 32 карты из них 4 туза....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru