Golf

Interview

Time limit1sMemory limit128 MB

Summary
Given a target distance and up to 32 distinct club distances, find how many strokes give an exact sum, using unlimited repeats of each club.
Level

Medium4 of 10

Topics
Dynamic programming, Greedy, Brute force, Math
Solved
No attempts yet

Problem

Roberta the Robot plays a perfect game of golf. Whenever she hits the ball, it always travels straight toward the hole and moves exactly the distance specified for the club she used. Each such hit is called a stroke, and the goal of golf is to send the ball from the tee to the hole in as few strokes as possible.

Roberta needs a program that chooses the best combination of clubs to reach the hole in the fewest strokes. If it is impossible to reach the hole exactly, she graciously acknowledges defeat.

Roberta can carry at most 32 clubs, and she may use each club as many times as she likes. The distance from the tee to the hole is at most 5,280 metres. Because the ball may never pass the hole, the chosen club distances must sum to exactly the tee-to-hole distance.

Input

The first line contains the distance from the tee to the hole, an integer number of metres between 1 and 5,280.

The second line contains the number of clubs, an integer between 1 and 32.

Each of the next lines describes one club, giving the distance in metres that the club hits the ball, an integer between 1 and 100. No two clubs hit the same distance.

Output

If Roberta can get the ball from the tee to the hole without passing the hole, print Roberta wins in n strokes., where n is the minimum possible number of strokes.

If Roberta cannot get the ball from the tee to the hole, print Roberta acknowledges defeat.

Examples2

  1. Example 1

    Input
    100
3
33
66
1
    Expected output
    Roberta wins in 3 strokes.

  2. Example 2

    Input
    5
1
2
    Expected output
    Roberta acknowledges defeat.