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

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

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

Формат ввода

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

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

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

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

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

Примечание

Качество мерим метрикой R e l D C G = ∑ i r e l e v a n c e i i RelDCG=\sum_i\frac{relevance_i}{i} .

Деньги метрим метрикой R e v e n u e = ∑ i c o s t 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

Теги

7.3.19
Нужно войти, чтобы отправить решение.Войти