CF 1062741 - Освещение комнаты

CF 1062741 - \u041e\u0441\u0432\u0435\u0449\u0435\u043d\u0438\u0435 \u043a\u043e\u043c\u043d\u0430\u0442\u044b

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

Solution

Problem Understanding

The problem compares two light bulbs. The ordinary bulb is cheaper to buy but consumes more electricity. The energy saving bulb costs more at the beginning, but every hour it uses fewer watts. We need to find the first whole number of hours after which the total money spent on the energy saving bulb is no more than the total money spent on the ordinary bulb.

The input gives five values on separate lines: the purchase price of the ordinary bulb, its hourly power consumption, the purchase price of the energy saving bulb, its hourly power consumption, and the electricity price per watt-hour in kopecks. The output is the smallest integer number of hours when the energy saving bulb has paid for its higher initial cost.

The values can reach $10^9$, so the answer can be much larger than a 32 bit integer. A direct simulation of hours is impossible because the number of hours needed may be around $10^{11}$ or more. We need a constant time calculation using arithmetic instead of checking every hour.

The edge cases are mostly connected to zero electricity price and exact division. If electricity is free, the more expensive bulb never catches up. For example:

The correct output is -1, because both bulbs keep their original purchase prices forever. A solution that divides by the saved energy cost without checking zero would fail.

Another case is when the saving becomes enough exactly at an integer hour:

The difference in purchase price is 10000 kopecks. Each hour saves 350 kopecks, so the first valid hour is 29. A solution using integer division without rounding upward would incorrectly produce 28.

A third case is when the first hour is already enough:

The output is 1. The energy saving bulb starts one kopeck more expensive, but saves 100 kopecks per hour, so it becomes better after the first hour. Implementations that accidentally allow zero hours would be wrong because the bulbs have not been used yet.

Approaches

A straightforward approach is to simulate the passing hours. For every hour, we calculate the total cost of both bulbs and stop when the energy saving bulb becomes no more expensive. This approach is easy to prove correct because it checks exactly the condition from the statement. However, it can require an enormous number of iterations. With prices near $10^9$, the required time can be around $10^{11}$ hours, making simulation impossible.

The key observation is that both costs grow linearly with time. The purchase prices are fixed, and every hour only adds the electricity cost. Instead of repeatedly comparing two growing values, we can compare their difference.

The energy saving bulb starts behind by $b-a$ rubles. Every hour it gains an advantage of $(x-y)p$ kopecks because it consumes fewer watts. Converting the initial difference into kopecks gives a simple inequality:

$$100(b-a) \leq h(x-y)p$$

The answer is the smallest integer $h$ satisfying it. This is just a ceiling division.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(answer)	O(1)	Too slow
Optimal	O(1)	O(1)	Accepted

Algorithm Walkthrough

Read the five input values and work entirely in kopecks. The electricity calculation already uses kopecks, so converting the bulb prices prevents floating point errors.
Compute the initial disadvantage of the energy saving bulb as 100 * (b - a). This is the amount of money it must save before becoming profitable.
Compute the saving gained every hour as (x - y) * p. The ordinary bulb consumes more energy, so this value is nonnegative.
If the hourly saving is zero, the energy saving bulb can never recover its higher price. Output -1.
Otherwise, compute the smallest integer hour count using ceiling division:

$$\left\lceil \frac{\text{initial disadvantage}}{\text{hourly saving}} \right\rceil$$

The integer form is (need + save - 1) // save.

Why it works: the difference between the two bulbs' costs decreases by exactly the same amount every hour. Initially the energy saving bulb is behind by a fixed amount. Each hour removes a fixed portion of that difference. The first moment when the accumulated saving reaches the initial disadvantage is exactly the moment when the energy saving bulb becomes no more expensive. Ceiling division finds the first integer hour where this happens.

Python Solution

import sys

input = sys.stdin.readline

def solve():
    a = int(input())
    x = int(input())
    b = int(input())
    y = int(input())
    p = int(input())

    need = 100 * (b - a)
    save = (x - y) * p

    if save == 0:
        print(-1)
    else:
        print((need + save - 1) // save)

if __name__ == "__main__":
    solve()

The program first converts the purchase price difference from rubles to kopecks. This avoids losing precision and keeps all calculations as integers.

The variable save stores how much cheaper the energy saving bulb becomes after one hour. Since the ordinary bulb consumes more electricity, this value is the progress made toward recovering the initial price difference.

The zero check is necessary because ceiling division by zero would be invalid, and logically the cheaper electricity cost never creates any advantage when electricity itself has no price.

The final expression uses the standard integer ceiling division formula. Adding save - 1 before dividing moves any non-exact result upward while leaving exact divisions unchanged.

Worked Examples

Sample 1

Input:

Step	Initial difference (kopecks)	Hourly saving (kopecks)	Calculation	Answer
Start	10000	350	ceil(10000 / 350)	29

The energy saving bulb needs to recover 10000 kopecks. Each hour it saves 350 kopecks, so after 28 hours it has saved 9800 kopecks, which is not enough. After 29 hours it saves 10150 kopecks, so it has become cheaper.

Sample 2

Input:

Step	Initial difference (kopecks)	Hourly saving (kopecks)	Calculation	Answer
Start	100	100	ceil(100 / 100)	1

The initial price difference is exactly covered after one hour. This confirms that exact division must not add an extra hour.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	The solution performs only a fixed number of arithmetic operations.
Space	O(1)	Only a few integer variables are stored.

The input values are large, but the algorithm never loops over the answer size. Python integers handle the required range safely, so the solution fits easily within the limits.

Test Cases

import sys
import io

def solve_data(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout
    sys.stdin = io.StringIO(inp)
    out = io.StringIO()
    sys.stdout = out

    a = int(sys.stdin.readline())
    x = int(sys.stdin.readline())
    b = int(sys.stdin.readline())
    y = int(sys.stdin.readline())
    p = int(sys.stdin.readline())

    need = 100 * (b - a)
    save = (x - y) * p

    if save == 0:
        print(-1)
    else:
        print((need + save - 1) // save)

    sys.stdin = old_stdin
    sys.stdout = old_stdout
    return out.getvalue()

assert solve_data("20\n90\n120\n20\n5\n") == "29\n", "sample 1"
assert solve_data("0\n100\n1\n0\n1\n") == "1\n", "sample 2"

assert solve_data("10\n100\n20\n50\n0\n") == "-1\n", "free electricity"
assert solve_data("5\n1000000000\n1000000000\n1\n1000000000\n") == "1\n", "large values"
assert solve_data("100\n200\n101\n199\n1\n") == "1\n", "small boundary difference"

Test input	Expected output	What it validates
`20 90 120 20 5`	`29`	Original sample and ceiling division
`0 100 1 0 1`	`1`	Exact division and first hour boundary
`10 100 20 50 0`	`-1`	Zero electricity price
Large values	`1`	Integer size handling
Small difference	`1`	Minimal positive answer

Edge Cases

For the zero electricity case:

The algorithm computes need = 1000 and save = 0. Since every hour gives no financial advantage, it immediately returns -1. There is no division by zero and no incorrect infinite loop.

For exact recovery:

The algorithm computes a required saving of 10000 kopecks and an hourly saving of 350 kopecks. The formula gives (10000 + 350 - 1) // 350 = 29, which matches the first hour where the accumulated saving is enough.

For a very small answer:

The required saving is 100 kopecks and the hourly saving is also 100 kopecks. The formula gives one hour instead of zero because the bulb must actually be used before electricity savings can appear.