CF 102697033 - Free Throws

CF 102697033 - Free Throws

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

Solution

Problem Understanding

The task asks for the team's overall free throw percentage. There are (n) players, and for each player we know two counts: how many free throws they made and how many they attempted. The team's percentage must be based on all free throws taken by the team, so we first combine the players' made shots and combine their attempts. The answer is

[ \frac{\text{total made}}{\text{total attempted}}\times 100 ]

rounded to exactly two digits after the decimal point.

The official problem uses a 1 second time limit and 256 MB of memory. The input contains one record for each of the (n) players, so simply reading the input already requires (\Theta(n)) work. There is no useful reason to do anything more expensive than a single pass through those records. In particular, an algorithm that repeatedly compares players or enumerates individual shot outcomes would introduce unnecessary work.

The key constraint for correctness is that an individual player's made throws cannot exceed their attempted throws, and the total number of attempts must be positive because a percentage with zero attempts would be undefined. Python integers are also a convenient choice because they do not overflow when the player counts are added together.

There are several small cases that commonly expose incorrect implementations. Suppose the input is

1
0 5

The correct output is 0.00. A program that calculates the percentage only when the number of made throws is positive could accidentally produce no answer or divide incorrectly.

Another boundary case is a player who makes every attempt:

1
7 7

The correct output is 100.00. Any implementation that treats the attempted count as the number of missed shots would get this wrong because the second value already represents all attempts, including successful ones.

A more useful aggregation case is

2
1 2
9 10

The correct output is 66.67, because the team made (1+9=10) of (2+10=12) attempts. Averaging the individual percentages would give ((50+90)/2=70), which is not the team's actual percentage. Players with different numbers of attempts must contribute according to their number of shots, not equally.

Approaches

A brute-force interpretation could treat every individual free throw as an independent event and enumerate all possible made or missed outcomes before calculating the percentage. If the team attempted (A) throws in total, there are (2^A) possible outcome sequences. That is already (2^{20}=1,048,576) possibilities for only 20 attempts, and (2^{100}) possibilities for 100 attempts, so this approach becomes unusable almost immediately. It is technically capable of finding the answer, but it solves a much harder problem than the input asks us to solve.

The input already gives the information needed to calculate the percentage. We do not need to reconstruct the individual shots because each player's made count contributes directly to the team's made count, and each player's attempted count contributes directly to the team's attempted count. We can accumulate these two quantities while reading the players, then perform one division at the end.

The distinction between summing counts and averaging player percentages is the central observation. For example, if one player makes 1 of 2 shots and another makes 9 of 10, their individual percentages are 50% and 90%, but the team's percentage is (10/12), or 83.33%. The total number of shots must be preserved, so the correct aggregation is a ratio of sums.

This gives a single-pass algorithm with constant auxiliary memory.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	(O(2^A))	(O(A))	Too slow
Optimal	(O(n))	(O(1))	Accepted

Algorithm Walkthrough

1. Read the number of players (n). We need exactly one pair of counts from each of these players.
2. Initialize made_total and attempted_total to zero. These variables represent the complete team totals seen so far.
3. For every player, read made and attempted, then add them to the corresponding totals. We sum the raw counts rather than calculating individual percentages because the final percentage must weight each player according to how many throws they attempted.
4. After all players have been processed, calculate made_total / attempted_total * 100. The numerator is now the number of successful free throws by the whole team, while the denominator is the number of free throws attempted by the whole team.
5. Print the result with exactly two digits after the decimal point. Python's :.2f formatting performs the required decimal rounding and also preserves trailing zeroes.

Why it works

After processing any prefix of the players, made_total equals exactly the number of successful free throws made by those players, and attempted_total equals exactly the number of throws they attempted. This invariant starts at zero before any players are processed and remains true because each player's two counts are added exactly once. After the final player, the two totals represent the entire team, so their ratio multiplied by 100 is precisely the team's free throw percentage. Formatting that value to two decimal places produces the required output.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input())

    made_total = 0
    attempted_total = 0

    for _ in range(n):
        made, attempted = map(int, input().split())
        made_total += made
        attempted_total += attempted

    percentage = made_total * 100 / attempted_total
    print(f"{percentage:.2f}")

if __name__ == "__main__":
    solve()

The first line gives the number of player records, so the loop runs exactly (n) times. Each iteration reads one player's made and attempted counts and adds them to the two running totals.

Multiplying the numerator by 100 before dividing is mathematically equivalent to multiplying the final ratio by 100. Keeping the calculation in floating point is appropriate here because the required output is a decimal rounded to two places. Python's integer type handles the accumulated counts without overflow before the division takes place.

The final formatting expression :.2f is significant. Printing the raw floating-point value could produce many decimal places, while integer division would lose the fractional part. The required result must contain exactly two digits after the decimal point, including cases such as 0.00 and 100.00.

There is no need to store the players after processing them. Each record contributes independently to the two totals, so constant auxiliary memory is sufficient.

Worked Examples

For the first sample, the four players contribute the following counts.

Player	Made	Attempted	Total Made	Total Attempted
1	1	5	1	5
2	3	4	4	9
3	7	7	11	16
4	6	8	17	24

The final percentage is (17/24\times100=70.8333\ldots), which rounds to 70.83. The trace demonstrates why the algorithm needs the two cumulative totals rather than an average of the four individual percentages.

A second example can expose the weighting issue:

2
1 2
9 10

Player	Made	Attempted	Total Made	Total Attempted
1	1	2	1	2
2	9	10	10	12

The final calculation is (10/12\times100=83.3333\ldots), so the output is 83.33. The individual percentages are 50% and 90%, but their simple average would be 70%, demonstrating that averaging percentages does not preserve the correct weighting.

Complexity Analysis

Measure	Complexity	Explanation
Time	(O(n))	Every player's two counts are read and processed once.
Space	(O(1))	Only the two accumulated totals and a few temporary integers are stored.

The algorithm performs exactly one pass over the input, which is optimal because every player record must be read at least once. It also avoids storing the input, so memory usage remains constant regardless of the number of players. With the problem's 1 second and 256 MB limits, this is comfortably within the intended resource bounds.

Test Cases

The official sample is included below, followed by cases for zero success, a perfect shooting record, unequal attempt counts, and a larger input. The statement does not publish a separate maximum value for (n), so the larger case uses 100,000 players as a stress test rather than claiming that 100,000 is the official maximum.

import sys
import io

def solve():
    input = sys.stdin.readline

    n = int(input())
    made_total = 0
    attempted_total = 0

    for _ in range(n):
        made, attempted = map(int, input().split())
        made_total += made
        attempted_total += attempted

    print(f"{made_total * 100 / attempted_total:.2f}")

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 sample
assert run(
    "4\n"
    "1 5\n"
    "3 4\n"
    "7 7\n"
    "6 8\n"
) == "70.83\n", "sample 1"

# Minimum-size input
assert run(
    "1\n"
    "0 1\n"
) == "0.00\n", "minimum-size input"

# Perfect percentage
assert run(
    "1\n"
    "7 7\n"
) == "100.00\n", "all attempts made"

# Unequal attempt counts, catches averaging individual percentages
assert run(
    "2\n"
    "1 2\n"
    "9 10\n"
) == "83.33\n", "weighted aggregation"

# Boundary values with many players
large_input = "100000\n" + ("1 2\n" * 100000)
assert run(large_input) == "50.00\n", "large input"

Test input	Expected output	What it validates
4 / 1 5 / 3 4 / 7 7 / 6 8	70.83	Official sample and normal aggregation
1 / 0 1	0.00	Minimum-size input and zero made throws
1 / 7 7	100.00	Perfect shooting and trailing zero formatting
2 / 1 2 / 9 10	83.33	Correct weighting by attempts
100,000 players with 1 2 each	50.00	Linear-time processing and large input

Edge Cases

The zero-success case is handled directly by the accumulated numerator. For

1
0 5

the algorithm finishes with made_total = 0 and attempted_total = 5, giving (0/5\times100=0). The output is 0.00, including the required trailing zeroes.

The perfect-percentage case works without any special branch. For

1
7 7

the totals are 7 made and 7 attempted, so the calculated percentage is exactly 100. The output is 100.00. A common mistake is to interpret the attempted count as the number of missed throws, which would incorrectly make the denominator 14.

The most subtle edge case is unequal numbers of attempts. For

2
1 2
9 10

the first player contributes 1 successful throw out of 2, while the second contributes 9 out of 10. The totals become 10 made and 12 attempted, giving 83.33. The algorithm never calculates the two individual percentages, so it cannot accidentally average them.

Finally, when many players are present, the algorithm keeps only two cumulative values. For 100,000 copies of 1 2, the totals are 100,000 made and 200,000 attempted, giving exactly 50.00. The running time grows linearly with the number of players, while the memory usage remains constant, so the implementation scales with the size of the input rather than with the number of possible shot outcomes.