1044EasyArrayStackSimulation

Tallying a Round With Corrections

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A scorer's sheet reads entries, worked through in order. Each entry is one of the following:

a whole number written as text: record that score;
"+": record a score equal to the last two recorded scores added together;
"D": record a score equal to twice the last recorded score;
"C": strike out the last recorded score, as though it had never been recorded.

Return all the recorded scores added together once the whole sheet has been worked through.

Every "+" has at least two scores already recorded, and every "D" and "C" at least one.

Examples

Example 1

Input: entries = ["3", "D", "D"]
Output: 21

Three is recorded, then twice it, six, then twice that, twelve. Three, six and twelve add to twenty-one.

Example 2

Input: entries = ["-5", "D", "+"]
Output: -30

Minus five is recorded, then twice it, minus ten, then those two added, minus fifteen. The three together come to minus thirty.

Example 3

Input: entries = ["10"]
Output: 10

One entry and one recorded score, so the total is that score.

Constraints

1 <= entries.length <= 1000
Each entry is "C", "D", "+", or a whole number written as text between -30000 and 30000.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def cal_points(entries: list[str]) -> int:

Java

public int calPoints(String[] entries)

The intended approach

Time O(n) over the sheet's length.Space O(n) for the recorded scores.

A stack of the recorded scores is exactly the shape the sheet calls for. Every entry either pushes one score on or takes the top one off, and both `"+"` and `"D"` look no further than the top of the stack. So walk the entries once: a number pushes its value, `"D"` pushes twice the top, `"+"` pushes the top two added together, and `"C"` pops the top. A struck-out score leaves the stack, so it also leaves the total, with no separate bookkeeping. Adding the stack up at the end gives the answer.

Pythonentry point: cal_points

def cal_points(entries):
    scores = []
    for entry in entries:
        if entry == "C":
            scores.pop()
        elif entry == "D":
            scores.append(scores[len(scores) - 1] * 2)
        elif entry == "+":
            scores.append(scores[len(scores) - 1] + scores[len(scores) - 2])
        else:
            scores.append(int(entry))
    total = 0
    for value in scores:
        total += value
    return total

The obvious version

Keep every score ever recorded and mark the struck-out ones rather than removing them. Before each entry, work out which recorded scores are still standing by scanning the marks, and take the last one or two of those where the entry calls for them. Adding the unmarked scores at the end gives the answer. Costs a scan per entry rather than a stack.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_cal_points(entries):
    recorded = []
    struck = []
    for entry in entries:
        live = []
        for at in range(len(recorded)):
            if not struck[at]:
                live.append(at)
        if entry == "C":
            struck[live[len(live) - 1]] = True
        elif entry == "D":
            recorded.append(recorded[live[len(live) - 1]] * 2)
            struck.append(False)
        elif entry == "+":
            recorded.append(recorded[live[len(live) - 1]] + recorded[live[len(live) - 2]])
            struck.append(False)
        else:
            recorded.append(int(entry))
            struck.append(False)
    total = 0
    for at in range(len(recorded)):
        if not struck[at]:
            total += recorded[at]
    return total

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in