Path Detection (APCS 2023-06 Beginner)

Points 100 1.0s 256M

Consider a 2D plane with the usual mathematical coordinates (positive Y is north, positive X is east). You start at \((0, 0)\), and there are \(n\) coordinates you must visit in order. Movement is guaranteed to be only horizontal or vertical (axis-aligned, never diagonal), and the first point is guaranteed to be on the positive X axis (so the initial direction is to the right / east).

Output how many left turns, right turns, and U-turns the path contains.

Input

The first line contains a positive integer \(n\). The next \(n\) lines each contain two integers \(x\) and \(y\), the coordinates to visit in order.

Constraints

  • \(1 \le n \le 100\)
  • Consecutive points differ in only the horizontal or vertical direction (axis-aligned moves), with coordinate difference at most \(100\)
  • The first point is on the positive X axis (\(y = 0\), \(x \ge 1\))

Output

Output three integers: the number of left turns, right turns, and U-turns.

Scoring

The time limit for each test case is \(1\) second; your score is the sum over the test cases you pass. The subtasks are:

  • Subtask 1 (\(60\) points): \(n = 2\).
  • Subtask 2 (\(40\) points): \(n \le 100\).

Sample Input 1

2
2 0
2 1

Sample Output 1

1 0 0

Sample Input 2

9
4 0
4 9
4 8
4 10
4 2
4 3
6 3
6 10
6 9

Sample Output 2

2 1 5

Source

APCS programming exam, June 2023, Problem 1.

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.