14679 - 영우와 ‘갓4’

step 1

전투를 1000번만 치루면 모든 스탯이 몬스터보다 높고 공격도 먼저 합니다. 즉, 이 이후로는 항상 이긴다고 생각할 수 있습니다.

step 2

현재 몬스터의 스탯을 알고 있을 때 다음 몬스터의 스탯은 $\log n$(https://codestudycafe.tistory.com/2)에 알 수 있습니다.

step 3

몬스터는 50,000,000마리가 있고 모든 몬스터의 상태를 계산해 주긴 해야합니다. dp를 만들어서 해결할 수 있습니다.

 

dp[i][j][k]: 현재 몬스터의 공격력이 i, 방어력이 j, 체력이 k일 때 다음 몬스터의 공격력, 방어력, 체력

 

이 dp를 만들면 시간을 줄일 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
pair<pair<long long int,long long int>,long long int> mapp[110][10][1100];
long long int ch[110][10][1100];
long long int win(long long int x, long long int y, long long int z, long long int xx, long long int yy, long long int zz) {
    long long int at = max((x - yy), 1ll);
    long long int at2 = max((xx - y), 1ll);
    long long int c1 = (zz % at == 0 ? zz / at : zz / at + 1);
    long long int c2 = (z % at2 == 0 ? z / at2 : z / at2 + 1);
    if (c1 <= c2) return 1; else return 0;
}
long long int poww(long long int x, long long int y, long long int z) {
    if (y == 1) return x;
    long long int v = poww(x, y / 2, z);
    v = v * v % z;
    if (y % 2 == 0) return v;
    return v * x % z;
}
int main() {
    long long int n, i, x, y, z, ex, ey, ez, sx1, sy1, sz1, sx2, sy2, sz2;
    scanf("%lld", &n);
    scanf("%lld%lld%lld", &x, &y, &z);
    scanf("%lld%lld%lld", &ex, &ey, &ez);
    scanf("%lld%lld%lld%lld%lld%lld", &sx1, &sx2, &sy1, &sy2, &sz1, &sz2);
    for (i = 1;i <= n;i++) {
        if (i<=2000 && !win(x, y, z, ex, ey, ez)) {
            printf("-1"); return 0;
        }
        x += ex; y += ey; z += ez;
        x %= 1000000007;
        y %= 1000000007;
        z %= 1000000007;
        if (ch[ex][ey][ez] !=0) {
            auto tmp = mapp[ex][ey][ez];
            ex = tmp.first.first;
            ey = tmp.first.second;
            ez = tmp.second;
            continue;
        }
        long long int tx = ex, ty = ey, tz = ez;
        ex = (poww(ex, sx1, 100) + sx2) % 100 + 1;
        ey = (poww(ey, sy1, 3) + sy2) % 3 + 1;
        ez = (poww(ez, sz1, 1000) + sz2) % 1000 + 1;
        ch[tx][ty][tz] = 1;
        mapp[tx][ty][tz] = { {ex,ey},ez };
    }
    printf("%lld %lld %lld", x, y, z);
    return 0;
}