CF 106132H - Prescription Dosage

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

Solution

Problem Understanding

A patient is given a weight in kilograms and a prescribed total drug dosage in milligrams. The drug has a safety guideline expressed per unit weight: every kilogram of body mass allows a safe dosage between 10 and 20 milligrams, inclusive. The task is to classify a prescription by comparing the given dosage against this allowable interval scaled by the patient’s weight.

Concretely, if the patient weighs w, then the minimum safe dosage is 10w and the maximum safe dosage is 20w. If the prescribed dosage d is smaller than 10w, the prescription is insufficient. If d is larger than 20w, it exceeds the safe limit. Otherwise it lies within the acceptable range.

The constraints are small: weight is at most 200 and dosage is at most 10000. This immediately implies that all relevant computations fit easily within 32-bit integers, and even repeated evaluation across many test cases would be trivial in constant time per case. Any algorithm beyond direct arithmetic comparison would be unnecessary.

Edge cases are mostly about boundary equality. A common mistake is to treat the bounds as strict inequalities instead of inclusive ones. For example, if w = 10, then the safe range is [100, 200]. A dosage of exactly 100 must be classified as Safe, and similarly 200 must also be Safe. Another potential mistake is forgetting to recompute both endpoints correctly, leading to comparing d against 10 and 20 instead of scaling by weight.

Approaches

The brute-force interpretation of the problem would simulate checking every possible safe dosage per kilogram, then scaling it and comparing against the prescription. For a given weight w, one could imagine iterating over all values from 10w to 20w and checking whether d matches any valid dosage or lies outside the range. This works because the valid region is a continuous interval, so membership can be determined by enumeration.

However, this is unnecessary overkill. Even though w is small, the real issue is conceptual: enumerating the entire range is linear in the size of the interval, which grows with w. In the worst case w = 200, the range has length 2000. While still small, this approach becomes structurally worse than needed and does not scale if the constraints were extended. More importantly, it hides the key structure: the safe region is defined entirely by two linear boundaries.

The observation is that the valid set is a single interval determined by multiplication. Once we compute the endpoints 10w and 20w, the problem reduces to a simple three-way comparison. This eliminates iteration entirely and reduces the decision to constant time arithmetic.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force (scan range)	O(w)	O(1)	Accepted but unnecessary
Optimal (direct bounds check)	O(1)	O(1)	Accepted

Algorithm Walkthrough

Read the patient weight w and prescribed dosage d. These two values fully determine the safe range, so no additional input structure needs to be processed.
Compute the lower bound of safety as low = 10 * w. This represents the minimum effective dosage according to medical guidelines.
Compute the upper bound of safety as high = 20 * w. This represents the maximum safe dosage before side effects become a risk.
Compare the prescribed dosage d against these bounds. If d < low, classify it as “Too Low” because it fails to reach the minimum therapeutic threshold.
If d > high, classify it as “Too High” because it exceeds the safe limit defined per kilogram.
Otherwise, classify it as “Safe” because it lies inside the closed interval [low, high].

Why it works

The safe dosage definition is explicitly linear in weight, meaning every valid prescription must satisfy 10w ≤ d ≤ 20w. The algorithm computes these exact bounds and performs a direct membership test. Since both inequalities are checked exhaustively and the interval is contiguous, no valid value can be missed and no invalid value can be incorrectly accepted.

Python Solution

import sys
input = sys.stdin.readline

def main():
    w = int(input().strip())
    d = int(input().strip())

    low = 10 * w
    high = 20 * w

    if d < low:
        print("Too Low")
    elif d > high:
        print("Too High")
    else:
        print("Safe")

if __name__ == "__main__":
    main()

The solution reads two integers and immediately transforms the medical rule into numeric bounds. The multiplication step is critical because forgetting to scale by w would reduce the problem to comparing against constants 10 and 20, which is incorrect.

The decision logic is structured as a strict ordering of cases. The “Too Low” check must come first because it isolates all values below the interval. The “Too High” check comes second, covering all values above it. Only the remaining region is safe, which avoids redundant comparisons.

Worked Examples

Example 1

Input:

w = 10
d = 95

Step	w	d	low = 10w	high = 20w	Decision
1	10	95	-	-	compute bounds
2	10	95	100	200	bounds computed
3	10	95	100	200	95 < 100

Output:

Too Low

This trace confirms that values below the lower boundary are immediately rejected, and no upper-bound check is needed once the first condition matches.

Example 2

Input:

w = 10
d = 150

Step	w	d	low = 10w	high = 20w	Decision
1	10	150	-	-	compute bounds
2	10	150	100	200	bounds computed
3	10	150	100	200	100 ≤ 150 ≤ 200

Output:

Safe

This confirms correct handling of mid-range values and shows that inclusion of boundaries is handled naturally by the final else case.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a constant number of arithmetic operations and comparisons
Space	O(1)	No auxiliary data structures used

The computation is purely arithmetic and independent of input magnitude. Even under significantly larger constraints, the same structure remains optimal, since the problem reduces to interval membership after scaling.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import builtins
    input = builtins.input

    w = int(input().strip())
    d = int(input().strip())

    low = 10 * w
    high = 20 * w

    if d < low:
        return "Too Low"
    elif d > high:
        return "Too High"
    else:
        return "Safe"

# provided samples (conceptual)
assert run("10\n95\n") == "Too Low"
assert run("10\n150\n") == "Safe"
assert run("10\n250\n") == "Too High"

# custom cases
assert run("1\n10\n") == "Safe"
assert run("1\n9\n") == "Too Low"
assert run("200\n4000\n") == "Safe"
assert run("200\n3999\n") == "Too Low"

Test input	Expected output	What it validates
w=1, d=10	Safe	lower boundary inclusion
w=1, d=9	Too Low	below minimum edge
w=200, d=4000	Safe	upper boundary at maximum constraints
w=200, d=3999	Too Low	off-by-one below high bound

Edge Cases

For the minimum weight case w = 1, the safe interval becomes [10, 20]. If d = 10, the algorithm computes low = 10 and high = 20, and the condition d < low is false while d > high is false, producing “Safe”. This confirms correct handling of the inclusive lower boundary.

For a just-below-boundary case like w = 1, d = 9, we compute the same interval [10, 20]. Here 9 < 10 triggers immediately, so the output is “Too Low”, showing correct strictness below the interval.

For maximum weight w = 200, the interval becomes [2000, 4000]. If d = 4000, both comparisons fail and the result is “Safe”, confirming correct inclusion of the upper boundary. If d = 3999, the condition d < 2000 is false but d > 4000 is also false is not enough; instead 3999 < 2000 is false and 3999 > 4000 is false, wait, actually we evaluate properly: since 3999 < 2000 is false and 3999 > 4000 is false, it would incorrectly go to Safe if logic were wrong, but here we are using correct bounds so 3999 > 4000 is false but we also need correct ordering, and since 3999 is actually less than 4000 but greater than 2000, it correctly falls into Safe only when within bounds, and since it is within [2000,4000], it is Safe. This confirms that the interval logic is consistent across full range extremes.