Codeforces Round #614 (Div.2 ) D. Aroma's Search

data는 각 노드 위에 존재하고, 노드의 위치는 (a_x * x_i-1 + bx, a_y * y_i-1 + b_y)로 주어진다.

노드의 위치가 최소 ax, ay 만큼의 배수로 커지는데, ax와 ay가 2 이상이므로

Aroma가 i번째 노드에서 i+1번째 노드로 이동하는 시간으로 i번째 노드에서 0번째 노드를 모두 가는 것이 가능하다.

따라서 시간이 불충분하고, i + 1번째 노드가 가깝게 있지 않는한 위쪽 노드는 방문하는 것은 힘든 일이다.

1) i + 1 노드가 가깝지 않을 때

가장 가까운 노드를 방문하여 아래로 쭉 내려가서 위로다시 올라오며 데이터를 모은다.

2) i + 1 노드가 가까운 경우

i + 1 노드를 먼저 방문하고 0번째 노드 방향으로 진행하여 데이터를 모은다.

#include <iostream>

using namespace std;

long long calDistance (long long x1, long long y1, long long x2, long long y2){
    long long diffX = x2 - x1;
    long long diffY = y2 - y1;
    if(diffX < 0) diffX = - diffX;
    if(diffY < 0) diffY = - diffY;

    return diffX + diffY;
}

long long x0, y0, ax, ay, bx, by;
long long xs, ys, t;
int num = 0;
long long numSec = 0;
long long xArr[60];
long long yArr[60];

int findNum(int i);

int main(){
    
    cin >> x0 >> y0 >> ax >> ay >> bx >> by;
    cin >> xs >> ys >> t;

    xArr[0] = x0;
    yArr[0] = y0;
    long long dCur;
    long long dPrev = calDistance(xArr[0], yArr[0], xs, ys);
    long long result = 0;
    // 2^60 이 10^16 보다 크므로 적당히 설정함
    for (int i = 1; i < 60; i ++){
        xArr[i] = ax * xArr[i-1] + bx;
        yArr[i] = ay * yArr[i-1] + by;
    }
    for (int i = 1; i < 60; i ++){
        dCur = calDistance(xArr[i], yArr[i], xs, ys);
        if(dPrev < dCur){
            result = findNum (i);
            break;
        }
        dPrev = dCur;
    }
    
    cout << result  << endl;

    return 0;
}

int findNum (int i){
    long long curX, curY;
    curX = xs;
    curY = ys;
    long long curDis;
    long long tSec = t;
    
    //작아지는 방향으로 서치
    for (int a = i-1; a >=0; a --){
        curDis = calDistance(xArr[a], yArr[a], curX, curY);
        t = t - curDis;
        if(t >= 0){
            num ++;
            curX = xArr[a];
            curY = yArr[a];
        } else{
            break;
        }
    }
    //아직 시간이 남은 경우 위로 올라가면서 더한다.
    if(t > 0){
        for (int a = i; a < 60; a++){
            curDis = calDistance(xArr[a], yArr[a], curX, curY);
            t = t - curDis;
            if( t >= 0 ){
                num ++;
                curX = xArr[a];
                curY = yArr[a];
            } else{
                break;
            }
        }
    }
    
    //위로 한칸만 갈 수 있는 경우를 구한다.
    tSec -= calDistance(xArr[i], yArr[i], xs, ys);
    if(tSec >0){
        numSec ++;
        curX = xArr[i];
        curY = yArr[i];
        //작아지는 방향으로 서치
        for (int a = i-1; a >=0; a --){
            curDis = calDistance(xArr[a], yArr[a], curX, curY);
            tSec = tSec - curDis;
            if(tSec >= 0){
                numSec ++;
                curX = xArr[a];
                curY = yArr[a];
            } else{
                break;
            }
        }
    }
    if (num < numSec){
        num = numSec;
    }
    return num;
}