TrainTickets | Topcoder Archive

Problem Statement

John is buying train tickets for a group of people. He gave several banknotes to the cashier, but forgot to mention the exact number of tickets he needs. The cashier knows that John may want to buy K tickets only if K satisfies the following conditions:

The amount given to the cashier is enough to pay for K tickets.
John did not give any extraneous banknotes. In other words, if he were to take back any single banknote, he would no longer be able to pay for K tickets.

A int[] banknotes contains information about the banknotes John gave to the cashier, where banknotes[i] represents the value of the i-th banknote. Also given is the price of a single ticket. Return the number of possible values for K.

Definition

Class:: TrainTickets
Method:: howManyWays
Parameters:: int, int[]
Returns:: int
Method signature:: int howManyWays(int price, int[] banknotes)
(be sure your method is public)

Constraints

price will be between 1 and 100, inclusive.
banknotes will contain between 1 and 50 elements, inclusive.
Each element of banknotes will be between 1 and 100, inclusive.

Examples

```
5
```
```
{11, 21}
```
```
Returns: 2
```
John wants 5 or 6 tickets. If he had wanted 4 or less tickets then he would give only the last banknote. He can not buy more than 6 tickets if he gave only 11 + 21 = 32.
```
7
```
```
{14}
```
```
Returns: 2
```
Jonh wants one or two tickets.
```
10
```
```
{10, 20, 30}
```
```
Returns: 1
```
John wants exactly 6 tickets.
```
5
```
```
{100, 100}
```
```
Returns: 20
```
John wants between 21 and 40 tickets, inclusive.

{76, 84, 64, 94, 67, 82, 94, 82, 75, 64,
 85, 83, 97, 91, 98, 78, 74, 95, 93, 77,
 77, 94, 95, 83, 95, 93, 76, 86, 68, 86,
 99, 97, 72, 94, 84, 89, 88, 88, 83, 87,
 79, 73, 82, 66, 90, 69}

Returns: 16

{100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}

Returns: 100

```
5
```
```
{5, 1}
```
```
Returns: 0
```
```
10
```
```
{19, 1}
```
```
Returns: 1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.