Задача

Сложность

0
Голосов еще нет

Автор

12.03.2014, 15:53 (Юрий Габуев)
12.03.2014, 15:54
В Весеннем королевстве есть $N$ городов и очень плохие дороги. Каждый город представляет собой целочисленную точку на отрезке $[0;N]$, и в каждом $i$-м городе живет $2i$ человек.
Bezymyannyy.jpg
Король Нетипун ненавидит деньги, но обожает котиков и поэтому собирает налоги в виде пушистых животных (по ставке $t$ от доходов жителей). Но вот незадача: по пути от города до столицы из-за некачественных дорог высыпается и гибнет часть налоговых котиков, пропорциональная расстоянию между городом и столицей и имеющая максимально возможное значение $L$. Помогите Нетипуну разместить столицу так, чтобы спасти как можно больше котиков.

Комментарии

Пусть $y$ - доход одного жителя, $k$ - коэффициент пропорциональности такой, что $L=k*t2Ny$, $X$ - координата столицы.
$U=\sum_{i=0}^{N}(2iyt - k|X-i|)=\sum_{i=0}^{N}2iyt - \frac{L}{2Nty}\sum_{i=0}^{N}|X-i| {\rightarrow}\underset{X}{max} $ $\Leftrightarrow \sum_{i=0}^{N}|X-i| \rightarrow \underset{X}{min}$ - ломаная с наклоном $-N-1+2X$ на каждом из интервалов $(X-1;X)$. Точкой минимума будет точка, удовлетворяющая условию $\frac{N-1}{2} \leqslant X \leqslant \frac{N+1}{2}$. Таким образом, $X^*=[\frac{N+1}{2}]$ (целая часть числа), если N - чётное, и $X^*$ - любое число из отрезка $[\frac{N-1}{2};\frac{N+1}{2}]$, если N - нечётное.
Так и не поняла, зачем нужны другие параметры. Я неверно понимаю условие?

____________________
UPD. Я действительно сделала не то, но оставлю тот кусок - вдруг кому-то пригодится.

Пусть $y$ - доход одного жителя, $k$ - коэффициент пропорциональности такой, что $L=kN$, $X$ - координата столицы.
$U=\sum_{i=0}^{N}(2iyt - k|X-i|*2iyt)=\sum_{i=0}^{N}2iyt - \frac{2Lty}{N}\sum_{i=0}^{N}i|X-i| {\rightarrow}\underset{X}{max} $ $\Leftrightarrow \sum_{i=0}^{N}i|X-i| \rightarrow \underset{X}{min}$ - ломаная, в любой точке $X=\left \{ 0,1,2,...,N \right \}$ меняющая наклон с $\left [ \frac{X(X-1)}{2}-\frac{(X+N)(N-X+1)}{2}\right ]$ на $\left [ \frac{(1+X)X}{2}-\frac{(X+1+N)(N-X)}{2}\right ]$. Остаётся найти точку смены знака c "-" на "+" или промежуток, на котором функция постоянна: этим условиям будут удовлетворять пары $X,N$ такие, что $X(X-1) < \frac{N(N+1)}{2} < X(X+1)$.

Моё решение было обвинено в отсутствии ответа, поэтому выпишу ответ явно:
$$ X=\begin{cases}[\frac{\sqrt{2N^2+2N+1}+1}{2}], \text { если } \frac{\sqrt{2N^2+2N+1}+1}{2}\notin \mathbb{Z}, (\text {[k] - целая часть числа}) \\ [\frac{\sqrt{2N^2+2N+1}-1}{2};\frac{\sqrt{2N^2+2N+1}+1}{2}], \text { если } \frac{\sqrt{2N^2+2N+1}+1}{2}\in \mathbb{Z}, (\text {[a;b] - отрезок})\end{cases}$$
zadacha_pro_kotikov.jpg