По краю пропасти (НТО 21/22 :: ИЭС)

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

Каждая из тренировок несёт свой вклад в вероятную победу, представленный условной «полезностью». Но эта «полезность» растёт нелинейно: если повторять тренировку одного и того же типа, она будет приносить меньше пользы. А именно, общая «полезность» N тренировок конкретного типа в неделю будет равна ciN,  где сi — коэффициент полезности для этого типа. Очевидно, общая «полезность» тренировок по плану равна сумме полезностей по выбранным типам.

Но кроме «полезности», для каждого вида тренировки есть вероятность получить травму, из-за которой спортсмен пропустит соревнования (а все тренировки пройдут впустую).

Определите такой план тренировок (сколько раз в неделю проводится та или иная тренировка), чтобы максимизировать математическое ожидание суммарной «полезности» и, соответственно, шансы на победу. 

Входной формат: 10 строк, в каждой два вещественных числа через пробел. Первое число — вероятность (доля единицы) получить травму во время одной тренировки. Второе — коэффициент полезности сi.

Выходной формат: 10 строк, в каждой — сколько раз назначается соответствующий тип тренировки (целое число). 

Решение принимается, если ваш план тренировок обеспечит такое же или большее матожидание полезности, чем представленное авторским решением.

Time Limit: 5 секунд

Memory Limit: 256 MB

Напишите программу. Тестируется через stdin → stdout.

Подзадача 2. Теперь тренер составляет более подробный план для одной отдельной тренировки. Она длится 4 часа и состоит из упражнений, на каждое их которых отводится по 15 минут. Всего упражнений 10 видов (в т.ч. отдых), и они имеют те же характеристики, что и тренировки в первой подзадаче. Необходимо определить план полностью, то есть суммарное число упражнений соответствует числу 15-ти минутных слотов.

Определите оптимальный план упражнений. Форматы данных и принцип проверки остаются прежними.

Time Limit: 1 секунда

Memory Limit: 256 MB

Напишите программу. Тестируется через stdin → stdout.