Описание
Отправленные решения

183. Документы на выдачe

Не решаласьСредняя

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

Формат ввода

Вам дан текстовый файл input.txt со следующими данными:

serpset — список размеченных поисковых выдач.
new_documents — размеченные документы.

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

Суммарная выручка по всем запросам.

Ответ округлите до сотых.

Примечание

Качество мерим метрикой $RelDCG=\sum_i\frac{relevance_i}{i}$.

Деньги метрим метрикой $Revenue=\sum_i\frac{cost_i}{\sqrt{i}}$.

Ограничения

Ограничение времени: 1 с
Ограничение памяти: 64 МБ

Пример 1

Ввод

{
	"serpset": [
		{
			"query": "okna",
		 	"results": [
				{"position": 0, "url": "okna-msk.ru", "relevance": 0.95, "cost": 77}, 
				{"position": 1, "url": "okna-pvh.ru", "relevance": 0.95, "cost": 70}, 
				{"position": 2, "url": "ne-okna.ru", "relevance": 0.3, "cost": 100}, 
				{"position": 3, "url": "best-okna.ru", "relevance": 0.1, "cost": 0}
		]}, 
		{
			"query": "lego",
			"results": [
				{"position": 0, "url": "lego.ru", "relevance": 0.95, "cost": 15}, 
				{"position": 1, "url": "lego-mir.ru", "relevance": 0.7, "cost": 30}, 
				{"position": 2, "url": "disney.ru", "relevance": 0.3, "cost": 100}]
		}], 
	"new_documents": [
		{"query": "weather", "url": "yandex.ru/pogoda", "relevance": 1, "cost": 0}, 
		{"query": "okna", "url": "yandex.ru/okna", "relevance": 1, "cost": 100}, 
		{"query": "lego", "url": "yandex.ru/lego", "relevance": 0.4, "cost": 10}
	]}

Вывод

338.81