INFOMAN брой 20

/*
1000 500

XVII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА

Втори ден - Задача 3. Джип

Един джип се намира в пустинята и трябва да достигне точка, 
отстояща на N километра от него. Теренът е тежък, колата е 
старичка, а и май отнякъде изтича гориво, та затова на всеки 
изминат километър се изразходват по 1 л. гориво. Джипът 
обаче има резервоар и бидони с обща вместимост M<N литра.
От друга страна, в началото на пътя има неограничено 
количество гориво, а навсякъде по изминаваното разстояние 
има празни цистерни, в които джипът, минавайки край тях, 
може да оставя колкото е нужно големи количества гориво от 
запасите си.
Напишете програма JEEP.EXE, която пресмята минималното 
количество гориво в литри, което е нужно за да се достигне 
целта на пътуването.

Във входния файл JEEP.INP са записани числата N и  M, които 
са цели и се намират на един ред. Известно е, че 5*M >= N > 0 
(N < 32000). 

Резултатът от програмата е цяло число (минималното количество 
гориво, евентуално закръглено нагоре), записано във файла 
JEEP.OUT. 

РЕШЕНИЕ:

 Първо отбелязваме, че задачата се свежда до това да се пренесе M гориво
на разстояние N-M.

 Jeep-а пренася горивото на курсове (напред-назад, напред-назад и така 
докато пренесе необходимото му горивото). Забелязваме, че на колкото
по-малко разстояние пренасяме горивото, толкова повече можем да пренесем
на един курс; следователно, за да пренесем горивото с минимален брой
курсове, трябва курсовете ни да са с минимална дължина.
Т.е. можем да приемем, че в най-добрия вариант можем да пренасяме 
горивото на курсове с дължина клоняща към 0 и следователно количеството
гориво което пренасяме на един курс клони към M.

 Решаваме задачата отзад напред. В крайния момент ни трябват 2 курса,
за да закараме М гориво на разстояние N-M. Обаче съществува точка в 
която ще ни е необходимо 2*M гориво и до тази точка ще трябва да стигнем
с 3 курса. До точката в която вече ще ни е необходимо 3*М гориво ще стигнем
с 4 курса и т.н. ...

 В програмата сме направили следното:
 Бележим текущия брой курсове с s
 Бележим текущото разстояние на което трябва да носим гориво със l
 Бележим текущото необходимо гориво с k
 В крайния момент (за програмата това е началния момент) имаме:
 k=m;
 l=n-m;
 s=2;
 После намираме следващото място на което ще трябва да увеличим броя на 
курсовете. То отстои на разстояние r=m/(s*2-1) от текущото място (т.к. 
между двете места хабим по s*2-1 гориво на километър (на всеки курс по
2 литра с изключение на последния в който хабим само 1 литър гориво,
понеже отиваме само в едната посока), а разликата в необходимото ни
гориво на двете места е m, следователно разстоянието м/у двете места е
m/(s*2-1) ).
 После проверяваме дали това разстояние е по-голямо от l
 Ако е, то значи вече сме подминали началния момент и следователно ще можем
да пренесем горивото от него на s курса, следователно отговорът на задачата
ще бъде k + (s*2-1)*l
 Ако не е, то подменяме стойностите на k, l и s по следния начин:
 l=l-r;
 k=k+m;  (или k=s*m;)
 s=s+1;
 И после повтаряме същата операция докато r стане по-голямо от l, а при 
дадените в условието ограничени (5*M>=N) това ще стане достатъчно скоро, за
да се поберем във времевия лимит.

Заб.: в действителност могат да бъдат направени някои подобрения, които не съм
забелязал на състезанието:
 r=(s*m-k)/(s*2-1);  да се замени с  r=m/(s*2-1);
 k+=r*(s*2-1); да се замени с  k=s*m;  или с  k+=m;


Velin Tzanov
*/

#include <stdio.h>
#include <math.h>

FILE *fn;
double n, m;
double l;
double k, s, r;
double step;
int res;

void main(void) {
int i;

char sTemp[200]; fn=fopen("jeep.c", "r"); fgets(sTemp,200,fn); // fn=fopen("JEEP.INP", "r");
fscanf(fn, "%lf %lf", &n, &m);
fclose(fn);

k=m;
l=n-m;
s=2;
while (1) {
  r=(s*m-k)/(s*2-1);
  if (r>l) {
    k+=(s*2-1)*l;
    break;
  } else {
    l-=r;
    k+=r*(s*2-1);
    s+=1;
  }
}

res=ceil(k);
fn = stdout; // fn=fopen("JEEP.OUT", "w");
fprintf(fn, "%d", res);
fclose(fn);

}