2014年9月20日 星期六

2014/9/20 TopCoder SRM 633 Div1 250 PeriodicJumping

// http://community.topcoder.com/stat?c=problem_statement&pm=13234&rd=16076
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

struct PeriodicJumping
{
    int minimalTime(int x, vector <int> v)
    {
        x = abs(x);
        if( x == 0 ) return 0;

        ll l = 0, r = 0;

        int cnt = 0;

        for(int i = 0; i < 2; i++)
            for(int vi = 0, vn = v.size(); vi < vn; vi++)
            {
                ll _l, _r;

                if( v[vi] > r ) _l = v[vi]-r;
                else if( v[vi] < l ) _l = l-v[vi];
                else _l = 0;
                _r = r+v[vi];

                l = _l; r = _r;

                cnt++;
                if( l <= x && x <= r ) return cnt;
             }

        ll sum = 0;

        for(int vi = 0, vn = v.size(); vi < vn; vi++)
            sum += v[vi];

        cnt = v.size()*(x/sum);
        x %= sum;

        if( x == 0 ) return cnt;
        sum = 0;

        for(int vi = 0; ; vi++)
        {
            sum += v[vi];
            cnt++;
            if( sum >= x ) return cnt;
        }
    }
};

沒有留言:

張貼留言