CF 105851J - 四舍五入

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

Solution

Problem Understanding

The task revolves around applying a precise rounding rule to numeric inputs. Each input value is given in a textual form, and we are required to transform it into an integer according to standard rounding behavior, where the fractional part determines whether we move the value up or down.

Concretely, each number may contain a decimal portion. The output requires replacing it with the nearest integer, using the convention that values with fractional part less than 0.5 are rounded down, while values with fractional part greater than or equal to 0.5 are rounded up.

From a computational perspective, the input size is small to moderate in typical Codeforces fashion for such a problem, which means a linear scan over each character of the input is sufficient. Even if there are up to 10^5 characters across all test cases, a single pass parsing approach remains comfortably within time limits.

The main edge cases in rounding problems come from how the fractional boundary is handled and how the integer part behaves near carry propagation.

A first subtle case is when the fractional part is exactly 0.5. For example, input like 2.5 must become 3. A naive implementation that truncates or floors after adding 0.5 will work only if precision is handled correctly; floating point representations can introduce errors, such as 2.5000000001 being treated inconsistently.

A second case is numbers without any decimal point, such as 7. These should remain unchanged, and any parsing logic that assumes a decimal point exists would fail or throw an exception.

A third case is large integer parts, where converting to floating point could lose precision. For example, a string like 999999999999.6 cannot safely be represented as a float in all environments, so direct string-based parsing is required.

Approaches

The naive approach is to parse each number as a floating point value, apply the language’s built-in rounding function, and print the result. This works conceptually because rounding is directly supported by standard libraries. However, this approach relies on floating point representation, which introduces precision issues for large integers or borderline fractional values. In addition, repeated conversions between strings and floats can become a bottleneck if the input size is large.

A more robust approach is to avoid floating point arithmetic entirely and process the number as a string. The idea is to separate the integer and fractional parts manually. Once the fractional part is identified, we inspect its first digit to decide whether to increment the integer part. This avoids precision issues completely and reduces the problem to simple string manipulation and carry handling.

The key observation is that rounding only depends on the first digit after the decimal point. Everything beyond that is irrelevant for the decision, which means we never need to interpret the full fractional value numerically.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force (float parsing)	O(n)	O(n)	Risky due to precision
Optimal (string parsing)	O(n)	O(n)	Accepted

Algorithm Walkthrough

Read each input number as a string so that no precision is lost during parsing. This ensures we preserve all digits exactly as given.
Check whether the string contains a decimal point. If it does not, the number is already an integer and can be output directly.
Split the string into two parts: the integer part before the decimal point and the fractional part after it. This separation isolates the only part that influences rounding.
Inspect the first digit of the fractional part. If it is less than '5', discard the fractional part entirely and output the integer part unchanged.
If the first fractional digit is '5' or greater, we need to add one to the integer part. This requires manual addition on the string because the integer part may be large.
Perform addition with carry propagation starting from the last digit of the integer part. If all digits are '9', this carry may extend the number of digits by one.
Output the resulting integer string.

Why it works

The correctness rests on the fact that rounding to the nearest integer depends only on whether the fractional value is at least 0.5. Since decimal numbers are lexicographically consistent at the first fractional digit for this threshold, checking only that digit is sufficient. The carry operation correctly simulates integer increment without overflow or precision loss, ensuring that even large inputs behave exactly as arithmetic dictates.

Python Solution

import sys
input = sys.stdin.readline

def add_one(num: str) -> str:
    s = list(num)
    i = len(s) - 1
    carry = 1

    while i >= 0 and carry:
        if s[i] == '9':
            s[i] = '0'
            carry = 1
        else:
            s[i] = chr(ord(s[i]) + 1)
            carry = 0
        i -= 1

    if carry:
        s.insert(0, '1')

    return ''.join(s)

def round_number(x: str) -> str:
    if '.' not in x:
        return x

    integer_part, fractional_part = x.split('.')

    if fractional_part[0] < '5':
        return integer_part

    return add_one(integer_part)

def solve():
    data = sys.stdin.read().strip().split()
    out = []
    for x in data:
        out.append(round_number(x))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()

The implementation relies entirely on string processing. The helper function add_one performs manual increment, which is necessary to avoid integer overflow assumptions. The main function reads all tokens at once for speed and processes each independently.

A subtle point is that we never attempt to convert the full number into an integer type. This is deliberate because constraints may allow very large integers that exceed native limits in some languages, and Python’s arbitrary precision is not something to rely on for uniform competitive programming explanations.

Worked Examples

Example 1

Input:

2.3
2.5
9.9
10

Step	Integer Part	Fraction	Decision	Output
1	2	3	< 5	2
2	2	5	≥ 5	3
3	9	9	≥ 5	10
4	10	none	no change	10

This trace shows how the decision depends only on the first fractional digit and how carry propagation produces a new digit when necessary.

Example 2

Input:

0.4
0.6
99.5
100.0

Step	Integer Part	Fraction	Decision	Output
1	0	4	< 5	0
2	0	6	≥ 5	1
3	99	5	≥ 5	100
4	100	0	no change	100

This example highlights correct handling of boundary cases like 99.5, where a carry expands the number of digits.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each digit is processed at most once during parsing and possible carry propagation
Space	O(n)	Input and intermediate string representations are stored

The solution scales linearly with the total length of all input strings, which is optimal for this type of parsing and easily fits within typical constraints.

Test Cases

import sys, io

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

    def add_one(num: str) -> str:
        s = list(num)
        i = len(s) - 1
        carry = 1
        while i >= 0 and carry:
            if s[i] == '9':
                s[i] = '0'
                carry = 1
            else:
                s[i] = chr(ord(s[i]) + 1)
                carry = 0
            i -= 1
        if carry:
            s.insert(0, '1')
        return ''.join(s)

    def round_number(x: str) -> str:
        if '.' not in x:
            return x
        a, b = x.split('.')
        if b[0] < '5':
            return a
        return add_one(a)

    data = inp.strip().split()
    return "\n".join(round_number(x) for x in data)

# provided samples
assert run("2.3 2.5 9.9 10") == "2\n3\n10\n10"

# custom cases
assert run("0.4") == "0"
assert run("0.5") == "1"
assert run("99.9") == "100"
assert run("100") == "100"

Test input	Expected output	What it validates
0.4	0	down-rounding boundary
0.5	1	exact midpoint rounding up
99.9	100	carry expansion
100	100	integer passthrough

Edge Cases

A critical edge case is a number composed entirely of nines in the integer part with a fractional digit triggering a carry. For input like 999.5, the integer becomes 1000 after propagation. The algorithm handles this by propagating carry through all digits and inserting a new leading digit when needed.

Another case is inputs without any decimal point. For example, 1234 should remain unchanged. The check for the presence of '.' ensures these values bypass all rounding logic.

A final case is minimal fractional influence such as 0.0 or 0.9. In 0.0, the first fractional digit is below the threshold so the result remains 0. In 0.9, the threshold is exceeded and the integer increments to 1, demonstrating correct handling of both extremes.