CardCollect | Topcoder Archive

Problem Statement

You're going to collect N type of cards with following method. They are numbered between 1 and N, inclusive.

There are N turns to take one card.
In i-th turn, you can get one card numbered from 1 to i, inclusive, in equal probability.
After N turns, you'll count the number of types of the cards.

Given an int N, return the expectation value of the number of types of the cards after N turns.

Definition

Class:: CardCollect
Method:: calc
Parameters:: int
Returns:: double
Method signature:: double calc(int N)
(be sure your method is public)

Constraints

N will be between 1 and 1,000, inclusive.

Examples

```
1
```
```
Returns: 1.0
```
```
2
```
```
Returns: 1.5
```
In the first turn, you'll get card 1. In the second turn, you'll get card 1 or 2 with the same probability. In result, you can get 2 kinds of cards with probability 1/2 and you can get 1 kinds of cards with probability 1/2. The expectation value is 1 * (1/2) + 2 * (1/2) = 1.5.
```
15
```
```
Returns: 7.999999999999999
```

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.