/* NAME: Ivan Anev PROG: invest LANG: C ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН'02 - 16 ноември 2002 ТЕМА ЗА 11–12 КЛАС (ГРУПА A) Задача 2. ИНВЕСТИЦИЯ Един инвеститор внася начален капитал x0 лева в строителна компания. От получения дивидент в края на всяка година той консумира ut лева, а остатъка добавя към своя капитал. Капиталът е инвестиран при лихвен процент p така, че капиталът през (t + 1)-вата година ще бъде равен на x(t+1) = xt + (p/100)xt – ut. Напишете програма INVEST.EXE, която да определи как инвеститорът може да максимизира общото потребление u0 + u1 + u2 + ... + uT–1 за T години чрез подходящо заделяне на пари за консумация ut през всяка от годините t = 0, 1, 2, ..., T – 1, като се спазва условието, че потреблението ut не може да е по-голямо от получения дивидент (p/100)xt, т.е. 0 <= ut <= (p/100)xt. Входните данни за задачата са записани на текстов файл и програмата ви трябва да ги прочете от стандартния си вход. Текстовият файл съдържа на един ред три стойности, отделени с по един интервал: стойността на T (цяло число в интервала от 1 до 5000), p (дробно число в интервала от 0.001 до 20.000, зададено с най-много 3 знака след десетичната точка) и началния капитал x0, зададен като цяло число между 1000 и 1000000. Изходните данни (възможното най-голямо общо потребление) програмата трябва да изведе на стандартния изход като число с десетична точка с точност до 6 цифри в дробната си част, закръглено чрез отсичане на евентуалните следващи десетични цифри. Пример. Вход: 2 10.0 1000 Изход: 200.000000 РЕШЕНИЕ: Нека означим с x началния капитал, с p (0<=p<=1) процента който получава като дивидент инвеститорът всяка година, с t броят на годините в разглеждания период и с k1, k2, . . ., kt процентите които сме взимали от дивидента през всяка година (0<=ki<=1). Нека разгледаме един период от j години, в който не сме взимали дивидент освен в една година - i. Тогава след този период ще имаме капитал x*((1+p)^(j-1))*(1+p*(1-ki)) и взети пари x*((1+p)^(i-1))*p*ki. Следователно независимо кога взимаме парите капитала в края на периода е един и същ само взетите пари се увеличават колко сме по към края. Следователно имаме изгода да взимаме пари само в края на периода. Да разгледаме сумите който взимаме през различните години. През първата година сме взели k1*x*p, през втората x*(1+p*(1-k1))*p*k2, през третата x*(1+p*(1-k1))*(1+p*(1-k2))*p*k3 и т.н. Искаме тяхната сума да бъде максимална. Вижда се че функцията е линейна спрямо k1, k2, . . ., kt. Да разгледаме функцията като функция на k1, като фиксираме всички други k-та. Функцията ще има максимална стойност когато k1 е или 0 или 1. Аналогично за всички k. Следователно сумата е максимална когато k-тата са 0 или 1. С тези две твърдения доказахме, че в началото трябва да се инвестира всичко, а в края да се взима всичко. Сега въпросът е кога да започнем да взимаме. Ясно е, че последната година ще вземем всичко. Нека до края на периода да остават m години. Ако (m-1)*p>1 следва, че ако инвестираме пари сега до последната година когато ще вземем всичко те ще са повече от колкото инвестираните следователно трябва да ги инвестираме. Горното неравенство е вярно до един момент и след това до края не е вярно. Стига да го открием (а то не е много трудно) и сме решили задачата. */ #include <stdio.h> #include <math.h> int t; double p, x, ans; int main(void) { int m; scanf("%d%lf%lf", &t, &p, &x); p /= 100.0; m = (int)floor(1.0 / p); if (m > t-1) m = t-1; x *= pow(1.0+p, t-1-m); ans = x * p * (m+1); printf("%.6f\n", ans); return 0; }