Question

Un biciclist vrea să realizeze turul României. Pentru acest lucru îşi stabileşte traseul şi n oraşe unde poate să facă câte un popas ca să se odihnească. Ultimul oraş este punctul de sosire. Pentru fiecare oraş se cunoaşte distanţa în kilometri de la oraşul anterior la acesta, notate cu d1, d2, ..., dn.
d1 este distanţa de la punctul de plecare la primul oraş, d2 este distanţa de la primul oraş la al doilea, ..., dn este distanţa de la penultimul oraş la ultimul.
Efortul depus pentru deplasare este măsurat în picături de transpiraţie. Astfel după fiecare kilometru parcurs pe primii k kilometri de la ultimul popas pierde câte o picătură de transpiraţie, iar apoi numărul acestora devine la fiecare kilometru egal cu suma picăturilor de la ultimii doi kilometri parcurşi anterior.
Biciclistul opreşte de fiecare dată la primul popas posibil, dar numai după ce străbate cel puţin k kilometri (de la popasul anterior).

Cerinţă

Să se scrie un program care determină efortul depus de biciclist (numărul total de picături de transpiraţie) pentru realizarea turului României.

Date de intrare

Fişierul de intrare efort.in are pe prima linie numerele n şi k separate printr-un spaţiu, iar pe linia a doua n numere naturale reprezentand distanţele d1, d2, ..., dn separate între ele prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire efort.out va conţine o singură linie pe care se va afişa un număr natural reprezentând efortul depus de biciclist.

efort.in

4 10
5 9 7 5
efort.out
43

Answer 1

#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,j,p,k,kp,s;
int d[1005],v[1005];
int main()
{
    freopen("efort.in","r",stdin);
    freopen("efort.out","w",stdout);
    scanf("%d %d",&n,&k);
    for (i=1;i<=n;i++) scanf("%d",&d[i]);
    p=0; j=0; s=0;
    while (j<n)
    {
        kp=0;
        while ((kp<k)&&(j<n))
         {
             j++;
             kp=kp+d[j];
         }
        p=j;
        if (kp>k)
         {
             for (i=1;i<=k;i++) v[i]=1,s++;
             for (i=k+1;i<=kp;i++) v[i]=v[i-1]+v[i-2],s=s+v[i];
         }
        else s=s+kp;
    }
    printf("%d",s);
    return 0;
}