PAST2M

https://gyazo.com/b74deda81b8400cfd3e8c683aff07100

PAST2M

Thoughts.

0 when the favorite dish is 0.

Otherwise, the pattern will be Period D, starting with the timing of your favorite dish.

Divide L by D.

But if I calculate the pattern of period D for each of the N employees, 10^10 will not make it, what should I do?

Official Explanation

https://gyazo.com/c60e3ee7a911c22c643bb530acf812c6

A new thought.

L is constant regardless of employees

If I know the next day the same favorite menu item is served, I know how many times I'll eat a menu item I don't like in between.

Tj varies from person to person, 10^9

Requires processing on the order of less than linear

Doubling to logarithmic order

The problem of finding x when f(x) = y by doubling the sum f(x) of the number of times you ate your favorite dish x times.

mounting

The specification is complex, so for the sake of clarity, I implemented it naively first

sample AC:

code:python

def solve(D, L, N, CS, KFTS):

for K, F, T in KFTS:

F -= 1 # 1-origin to 0-origin

ret = 0

ret = 1

countdown = T - 1

cur = F

prev = cur

while countdown:

cur += 1

ret += 1

prev = cur

countdown -= 1

elif cur - prev == L:

prev = cur

countdown -= 1

print(ret)

I didn't take the extra and forgot that RE and F are 1-origin and did WA and so on.

The problem is that this while countdown is 10^9.

The commentary dubbed it one step to the next favorite dish, but if you're going to dub it anyway, why not just one step per day?

No, because if you don't use your favorite dish as a starting point, you won't be able to determine how many dishes you don't like to eat.

A version that records the location of the "next same dish" in advance and skips ahead once a favorite dish is found.

code:python

def solve(D, L, N, CS, KFTS):

MAX_C = 10 ** 5

for i, d in enumerate(CS):

d -= 1 # to 0-origin

else:

for d in range(MAX_C):

for K, F, T in KFTS:

F -= 1 # 1-origin to 0-origin

ret = 0

ret = 1

countdown = T - 1

cur = F

prev = cur

while countdown:

cur += 1

ret += 1

countdown -= 1

while True:

d = n - cur

if d < 0:

d += D

up = (d - 1) // L + 1

if countdown >= up:

countdown -= up

cur = n

ret += 1

continue

else:

countdown = 0

break

elif cur - prev == L:

prev = cur

countdown -= 1

print(ret)

Next, we'll dub this "moving on" section.

Scope.

Worst case scenario, if the next plate is next to it, the number of dishes is only +1, so it takes 10^9 times to get to 10^9.

This is one step

doubling

I didn't realize I needed the value of next for doubling ups, and I implemented it wrong once.

code:python

# doubling

for _i in range(1, 30):

new_next = []

new_ups = []

for i in range(D):

new_next.append(n2)

new_ups.append(u1 + u2)

db_next.append(new_next)

db_ups.append(new_ups)

code:python

for i in range(30 - 1, -1, -1):

if countdown >= up:

countdown -= up

ret += 2 ** i

You're still going to TLE on this one, right? (19 TLE to 10 TLE)

Oh, right, people who don't have a favorite dish will run 10^9.

code:python

print(0)

continue

Still, 4TLE.

It's not good that you're asking for a loop of "the first day your preferred dish appears after F."

Let's bifurcate this one, too.

---