Tape Movement Sequence (APCS 2023-06 Advanced)

Points 100 1.0s 256M

You are given a tape and a string of control instructions. The tape pointer initially points to position \(10\), and the input begins with T10. The string consists of T and loop instructions.

  • Txx: xx is a two-digit integer from \(10\) to \(99\) and moves the pointer to position \(xx\).
  • Lx...E: x is a one-digit integer from \(1\) to \(9\). The instructions between Lx and its matching E are executed \(x\) times. Loops may be nested, and every loop contains at least one T instruction.

Whenever Txx is executed, the pointer travels the absolute difference between its current position and \(xx\). Compute the total distance traveled after the entire instruction string is executed.

Input

The input contains one line: the tape pointer's control instruction string.

Constraints

  • The instruction string begins with T10.
  • Its length is at most \(10^5\).
  • Every loop count is between \(1\) and \(9\).
  • Every loop contains at least one T instruction.
  • The total distance does not exceed \(2^{60}\).

Output

Output one integer: the total distance traveled after all instructions are executed.

Scoring

There are \(20\) scored test cases. Each test case is worth \(5\) points.

Subtask Points Additional constraints
1 10 There is no loop, and the string length is at most \(50\)
2 30 The string length is at most \(10^4\), and the expanded number of T records is at most \(3\times10^4\)
3 60 No additional constraints

Sample Input 1

T10T15T23T23T22T22T44

Sample Output 1

36

Sample Input 2

T10L2T15T22L2T15ET23ET44

Sample Output 2

78

Source

APCS June 2023, Programming Problem 3; ZeroJudge k733 Tape Movement Sequence.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.