CF 102697090 - Computer World

The task is a direct classification of a computer's hard-drive capacity. The input is a string such as 300GB, where the numeric part is the capacity in gigabytes and the final GB is a fixed suffix.

codeforcescompetitive-programming

CF 102697090 - Computer World

Rating: -
Tags: -
Solve time: 9m 55s
Verified: yes

Solution

Problem Understanding

The task is a direct classification of a computer's hard-drive capacity. The input is a string such as 300GB, where the numeric part is the capacity in gigabytes and the final GB is a fixed suffix. We must remove that suffix, interpret the remaining part as an integer, and classify the capacity into one of three categories.

A capacity of at most 200 GB is SMALL. A capacity greater than 200 GB but at most 500 GB is MEDIUM. Anything above 500 GB is LARGE. The official problem uses a 1 second time limit and 256 MB of memory. Since there is only one short input string and the computation consists of parsing it and performing at most two comparisons, the algorithm is comfortably within those limits. The running time is proportional only to the number of characters in the input string.

The main boundary cases are the two thresholds themselves. For 200GB, the answer is SMALL, not MEDIUM, because the first interval is inclusive. For 500GB, the answer is MEDIUM, not LARGE, because the second interval is also inclusive. For example, the input 200GB produces SMALL, while 500GB produces MEDIUM. A careless implementation using < 200 or < 500 would misclassify these exact boundary values.

Another easy mistake is comparing the complete string with strings such as "200GB" without first interpreting its numeric part. Lexicographic string comparison does not represent numerical comparison in general. For example, "1000GB" and "500GB" do not have the same ordering under the logic we need. Extracting the integer avoids that entire class of errors.

Approaches

A brute-force interpretation would be to simulate every possible capacity from the smallest possible value up to the given capacity and determine which interval contains it. This would be correct in the sense that eventually the simulated value reaches the actual capacity, but it performs one iteration per gigabyte. If the capacity is C, that approach performs C iterations, so its worst-case operation count is proportional to the largest possible capacity, rather than to the length of the input. There is no reason to enumerate values because the classification is determined entirely by two fixed boundaries.

The key observation is that the three categories form consecutive intervals. Once the numeric capacity is known, there are only two questions to answer: is it at most 200, and if not, is it at most 500? The first true condition completely determines the answer. If both conditions are false, the capacity must be larger than 500 and is consequently LARGE.

The brute-force works because it eventually discovers the same interval containing the capacity, but fails because it does unnecessary work over values that have no influence on the result. The observation that only the two thresholds matter reduces the problem to parsing one integer and making two constant-time comparisons.

Approach Time Complexity Space Complexity Verdict
Brute Force O(C) O(1) Too slow in principle
Optimal O(L) O(1) Accepted

Here, C is the numeric capacity and L is the length of the input string. The optimal solution is effectively constant time for the small fixed-size input used by the problem.

Algorithm Walkthrough

  1. Read the capacity string, for example 450GB. The GB suffix is not part of the numerical value, so it must be removed before converting the capacity to an integer.
  2. Convert everything before the final two characters to an integer. For 450GB, this gives 450.
  3. If the capacity is at most 200, print SMALL. The comparison must be inclusive because exactly 200 GB belongs to this category.
  4. Otherwise, if the capacity is at most 500, print MEDIUM. Reaching this branch already tells us the capacity is greater than 200, so the resulting interval is exactly 201 through 500.
  5. If neither comparison succeeded, print LARGE. At this point the capacity is necessarily greater than 500.

Why it works: after removing GB, every valid capacity is represented by exactly one integer. The three possible outputs partition all capacities into x <= 200, 200 < x <= 500, and x > 500. The algorithm checks those intervals in order, so exactly one branch matches the numeric capacity and the corresponding classification is printed.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    s = input().strip()
    capacity = int(s[:-2])

    if capacity <= 200:
        print("SMALL")
    elif capacity <= 500:
        print("MEDIUM")
    else:
        print("LARGE")

if __name__ == "__main__":
    solve()

The first line inside solve reads the complete input and removes the trailing newline with strip(). The expression s[:-2] removes exactly the two characters GB, leaving only the decimal representation of the capacity.

Python's int performs the required numerical conversion, so comparisons such as capacity <= 200 are numerical rather than lexicographic.

The first condition uses <= 200, matching the inclusive lower category boundary. The second condition only needs to check <= 500 because the earlier if has already ruled out every value at most 200. The final else consequently represents every value greater than 500.

There is no integer-overflow issue in Python, and the algorithm stores only the input string and one integer.

Worked Examples

Sample 1

For the input 800GB, removing the suffix gives the integer 800.

Capacity First check <= 200 Second check <= 500 Output
800 false false LARGE

Both threshold checks fail, so the remaining category is LARGE. This demonstrates the upper interval.

Sample 2

For the input 200GB, removing the suffix gives 200.

Capacity First check <= 200 Second check <= 500 Output
200 true not reached SMALL

The first comparison is inclusive, so exactly 200 belongs to SMALL. This is the boundary case that catches an implementation using < 200.

Sample 3

For the input 450GB, the parsed capacity is 450.

Capacity First check <= 200 Second check <= 500 Output
450 false true MEDIUM

The value is above 200 but does not exceed 500, so it belongs to MEDIUM.

Complexity Analysis

Measure Complexity Explanation
Time O(L) The input string is read and its suffix is removed in proportion to its length, followed by two comparisons.
Space O(L) The input string and its parsed integer require storage proportional to the input size.

With only one short string to process, the solution is far below the 1 second and 256 MB limits specified by the problem.

Test Cases

# helper: run solution on input string, return output string
import sys
import io

def solve():
    s = input().strip()
    capacity = int(s[:-2])

    if capacity <= 200:
        print("SMALL")
    elif capacity <= 500:
        print("MEDIUM")
    else:
        print("LARGE")

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    try:
        solve()
        return sys.stdout.getvalue()
    finally:
        sys.stdin = old_stdin
        sys.stdout = old_stdout

# provided samples
assert run("800GB\n") == "LARGE\n", "sample 1"
assert run("200GB\n") == "SMALL\n", "sample 2"
assert run("450GB\n") == "MEDIUM\n", "sample 3"

# minimum-size style case
assert run("0GB\n") == "SMALL\n", "zero capacity"

# exact upper boundary of SMALL
assert run("200GB\n") == "SMALL\n", "200 must be SMALL"

# exact upper boundary of MEDIUM
assert run("500GB\n") == "MEDIUM\n", "500 must be MEDIUM"

# just above the MEDIUM boundary
assert run("501GB\n") == "LARGE\n", "501 must be LARGE"

# large capacity
assert run("1000000000GB\n") == "LARGE\n", "large capacity"
Test input Expected output What it validates
0GB SMALL Minimum-style value and lower interval
200GB SMALL Inclusive SMALL boundary
500GB MEDIUM Inclusive MEDIUM boundary
501GB LARGE First value above the MEDIUM boundary
1000000000GB LARGE Large numeric value and parsing

Edge Cases

The first boundary case is exactly 200GB. The algorithm parses 200, checks 200 <= 200, and immediately prints SMALL. An implementation using < 200 would incorrectly continue to the next category.

The second boundary case is exactly 500GB. The first comparison fails because 500 is greater than 200, while the second comparison succeeds because 500 <= 500. The output is MEDIUM. Using < 500 here would incorrectly classify it as LARGE.

The value immediately above the second boundary, 501GB, follows the opposite path. 501 <= 200 is false and 501 <= 500 is also false, so the final branch prints LARGE. This confirms that there is no gap between the MEDIUM and LARGE ranges.

Finally, the suffix must be removed before conversion. For 450GB, s[:-2] produces 450, which int converts to the number 450. The algorithm then compares that number against the numerical thresholds rather than attempting to reason about the original text.