CF 1051952 - Лазерная пушка

CF 1051952 - \u041b\u0430\u0437\u0435\u0440\u043d\u0430\u044f \u043f\u0443\u0448\u043a\u0430

Rating: -
Tags: -
Solve time: 50s
Verified: yes

Solution

Problem Understanding

The problem describes a spaceship with two independent lasers. Each laser has a power value and a reload time. A laser starts charging immediately, and after each shot it needs its reload time before it can shoot again. If both lasers are ready at the same moment, they can be fired together and their powers are combined.

The enemy ship has a durability value and a shield value. A single laser shot deals its power minus the shield. A combined shot deals the sum of both powers minus the shield only once, so firing together is better than firing the two lasers separately by exactly one shield value.

The task is to find the earliest time when the enemy can be destroyed.

The input contains the power and reload time of the two lasers, followed by the enemy durability and shield. The output is the minimum time of the final shot that reduces the enemy durability to zero or below.

The durability is at most 5000, while reload times can reach $10^{12}$. This combination tells us that the answer may be very large, so simulating every second or every reload event is impossible. At the same time, the amount of damage needed is small enough that we can afford algorithms depending on the durability, but we need to avoid iterating over large time values.

A few edge cases require attention. If one laser is much weaker but much faster, using only that laser can beat waiting for combined shots. For example:

10 1
5000 100000
25 9

The first laser deals only $10-9=1$ damage per shot, but it can fire every second. The answer is 25, because waiting for the second laser would be slower.

Another case is when the lasers always synchronize. For example:

5 10
4 10
16 1

Both lasers are ready at times 10, 20, and so on. A combined shot deals $5+4-1=8$ damage, so two shots are enough and the answer is 20. A careless solution that only considers separate shots would underestimate the advantage of synchronization.

A third subtle case appears when reload times have no frequent common points:

100 7
100 11
50 1

The lasers rarely combine, so counting every possible pair of shots would be wasteful. The only relevant information about combined shots is how often the reload schedules meet.

Approaches

A direct approach would simulate the timeline. We could store the next moment each laser becomes available, repeatedly choose the best action, and continue until enough damage is dealt. This is correct because every shot event can only happen when a laser is charged. However, reload times can be extremely large, so even a small number of useful shots may happen after enormous gaps. A simulation based on time progression or event handling is not suitable.

The key observation is that we do not actually need to know the order of shots. Consider a fixed finishing time $T$. By this time, laser 1 has had exactly $\lfloor T/t_1 \rfloor$ opportunities to fire, and laser 2 has had exactly $\lfloor T/t_2 \rfloor$ opportunities. We should always use every available shot because all damage is positive.

If the two lasers are both available at the same moment, firing them together gives an additional $s$ damage compared with firing them separately. The common firing moments are exactly the positive multiples of the least common multiple of the two reload times. Therefore, for a given time $T$, the maximum damage is:

$$\left\lfloor\frac{T}{t_1}\right\rfloor(p_1-s) + \left\lfloor\frac{T}{t_2}\right\rfloor(p_2-s) + \left\lfloor\frac{T}{\operatorname{lcm}(t_1,t_2)}\right\rfloor s$$

Now the problem becomes checking whether a given time is enough. This predicate is monotonic: if time $T$ is enough, every larger time is also enough. That allows binary search on the answer.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(answer / minimum reload time)	O(1)	Too slow
Optimal	O(log(answer))	O(1)	Accepted

Algorithm Walkthrough

1. Compute the damage values of shooting laser 1 alone, laser 2 alone, and the extra damage gained from combining both lasers. A single laser contributes $p_i-s$, while a combined shot is equivalent to two separate shots plus an additional $s$.
2. Create a function that checks whether a given time $T$ is enough. The function counts how many times each laser can fire by time $T$, then adds the synchronization bonus from the moments when both reload schedules meet.
3. Find the least common multiple of the two reload times. Every positive multiple of this value is a moment when both lasers are ready together.
4. Binary search the answer. Start with a small right boundary and repeatedly double it until the checking function says the enemy can be destroyed within that time. Then search the interval to find the smallest valid time.
5. Return the first time that passes the check.

Why it works: for every chosen finishing time, the formula counts all damage that can be dealt by that moment. It includes every possible single shot and every possible synchronized shot. Since delaying a shot cannot create more damage before the same deadline, this is the maximum possible damage for that time. The check function is monotonic, so binary search finds the first time when the enemy becomes destroyable.

Python Solution

import sys
import math

input = sys.stdin.readline

p1, t1 = map(int, input().split())
p2, t2 = map(int, input().split())
h, s = map(int, input().split())

d1 = p1 - s
d2 = p2 - s

g = math.gcd(t1, t2)
lcm = t1 // g * t2

def can(time):
    damage = (time // t1) * d1
    damage += (time // t2) * d2
    damage += (time // lcm) * s
    return damage >= h

left = 0
right = 1

while not can(right):
    right *= 2

while left < right:
    mid = (left + right) // 2
    if can(mid):
        right = mid
    else:
        left = mid + 1

print(left)

The first part computes the effective damage of each laser. The shield is subtracted for every separate shot, so the damage values used in the formula are already the real damage values.

The can function is the entire mathematical model of the problem. The two floor divisions count individual firing opportunities. The least common multiple counts moments where both lasers can be merged into one stronger attack, and the extra $s$ accounts for the saved shield reduction.

The initial binary search upper bound is not guessed. It is expanded by doubling until it becomes valid, which guarantees that even very large answers caused by reload times up to $10^{12}$ are handled. Python integers avoid overflow during the least common multiple calculation and the damage computation.

Worked Examples

Sample 1

Input:

5 10
4 9
16 1

The values are:

Time	Laser 1 shots	Laser 2 shots	Combined moments	Damage
10	1	1	0	8 + 7 = 15
20	2	2	2	16 + 14 + 2 = 32

The first laser deals 4 damage per shot and the second deals 3 damage per shot. At time 20 there are two synchronized shots, adding the bonus from the shield twice. The damage is enough, while time 10 is not, so the answer is 20.

Sample 2

Input:

10 1
5000 100000
25 9

Time	Laser 1 shots	Laser 2 shots	Combined moments	Damage
10	10	0	0	10
25	25	0	0	25

The second laser has very high damage but takes too long to charge. The first laser alone destroys the enemy exactly at time 25.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log(answer))	Each binary search step performs only constant time arithmetic.
Space	O(1)	The algorithm stores only a few integer variables.

The number of binary search iterations is small because the answer is found by repeatedly halving an interval whose upper bound is obtained by doubling. The solution does not depend on the size of the reload times, so values around $10^{12}$ are handled easily.

Test Cases

import sys
import io
import math

def solve(data):
    it = iter(data.strip().split())
    p1 = int(next(it))
    t1 = int(next(it))
    p2 = int(next(it))
    t2 = int(next(it))
    h = int(next(it))
    s = int(next(it))

    d1 = p1 - s
    d2 = p2 - s
    lcm = t1 // math.gcd(t1, t2) * t2

    def can(t):
        return (t // t1) * d1 + (t // t2) * d2 + (t // lcm) * s >= h

    l, r = 0, 1
    while not can(r):
        r *= 2

    while l < r:
        m = (l + r) // 2
        if can(m):
            r = m
        else:
            l = m + 1
    return str(l)

assert solve("5 10 4 9 16 1") == "20", "sample 1"
assert solve("10 1 5000 100000 25 9") == "25", "sample 2"
assert solve("5 10 4 10 16 1") == "20", "equal reload times"
assert solve("100 7 100 11 50 1") == "2", "fast destruction"
assert solve("2 1000000000000 3 999999999999 10000 1") == "5000", "large reload values"

Test input	Expected output	What it validates
5 10 4 10 16 1	20	Frequent synchronization and combined shots
100 7 100 11 50 1	2	Large damage with no need for many shots
2 1000000000000 3 999999999999 10000 1	5000	Very large reload times and integer handling

Edge Cases

When one laser is much faster than the other, the algorithm does not force combined shots. For:

10 1
5000 100000
25 9

the check at time 25 counts 25 shots from the first laser, zero from the second, and zero synchronization bonuses. The damage is exactly 25, so the binary search accepts this time.

When both lasers always become ready together, the synchronization term becomes essential. For:

5 10
4 10
16 1

the least common multiple is 10. At time 20, each laser has two firing opportunities and there are two combined moments. The damage calculation gives:

$$2 \cdot 4 + 2 \cdot 3 + 2 \cdot 1 = 16$$

so the algorithm returns 20.

When the least common multiple is very large, the algorithm still works because it never enumerates synchronization moments. It only computes how many exist before a deadline using integer division. For:

100 7
100 11
50 1

the first few binary search checks simply evaluate the arithmetic formula, and the answer is found without simulating any shots.