Robot Mouse (APCS 2023-10 Beginner)

Points 100 1.0s 256M

There is food at \(n\) positions, and a mouse starts at position \(x\).

Before foraging, the mouse chooses to move either left or right. When it passes food it may stop and eat it; after eating it may continue in the same direction or end foraging for the day.

Find the maximum number of food items the mouse can eat, and the position of the last food it eats.

Input

The first line contains two integers \(x\) and \(n\) separated by a space: \(x\) is the mouse's starting position and \(n\) is the number of food items.

The second line contains \(n\) integers separated by spaces, the positions of the food, none of which coincides with the mouse's position.

Constraints

  • \(3 \le n \le 20\), and \(n\) is odd
  • The mouse and food positions are between \(-100\) and \(100\)
  • No food position coincides with the mouse's position

Output

Output two integers: the maximum number of food items eaten, and the position of the last food eaten.

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 = 3\).
  • Subtask 2 (\(40\) points): the general case.

Sample Input 1

10 3
1 5 13

Sample Output 1

2 1

Sample Input 2

10 9
-1 13 12 16 100 -9 7 8 25

Sample Output 2

5 100

Source

APCS programming exam, October 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.