↓Skip to main content
  1. Posts/

CodeForces-1292B Aroma's Search

·2 mins·
Table of Contents

CodeForces-1292B Aroma’s Search #

Solution 1 #

根据条件, 所有的点都在第一象限, 从左下向右上分布, 越向右上越稀疏. 从初始点到某个点, 不难证明先向左下出发, 到达 $(x_0, y_0)$ 后再返回右上的性价比是最高的. 两层遍历计算答案.

代码如下:

from math import inf

x = [inf for _ in range(100)]
y = [inf for _ in range(100)]
d = [[inf for _ in range(100)] for _ in range(100)]

def dist(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)

x[0], y[0], ax, ay, bx, by = list(map(int, input().split()))
xs, ys, t = list(map(int, input().split()))

for i in range(1, 100):
    x[i] = ax * x[i - 1] + bx
    y[i] = ay * y[i - 1] + by
    if x[i] > xs and y[i] > ys and dist(x[i], y[i], xs, ys) > t:
        break
        
ans = 0

for i in range(99):
    res, k = 0, t
    if dist(xs, ys, x[i], y[i]) <= k:
        k -= dist(xs, ys, x[i], y[i])
        res += 1
    else:
        continue
    for j in range(i - 1, -1, -1):
        if dist(x[j + 1], y[j + 1], x[j], y[j]) <= k:
            k -= dist(x[j + 1], y[j + 1], x[j], y[j])
            res += 1
        else:
            break
    for j in range(1, 100):
        if dist(x[j - 1], y[j - 1], x[j], y[j]) <= k:
            k -= dist(x[j - 1], y[j - 1], x[j], y[j])
            res += 1 if j > i else 0
        else:
            break
    ans = max(ans, res)
    
print(ans)
↑