Want to try solving this problem? You can submit your code online if you log in or register.

There are *N* budgies down in your garden each day,

who eat seeds from the ground and sit up on the wall.

You would like to use your shiny camera to

take some colourful photographs (*shots*) of them all.

who eat seeds from the ground and sit up on the wall.

You would like to use your shiny camera to

take some colourful photographs (

You have watched the birds closely and know them quite well.

You know each of the budgies can only be seen

at a certain fixed interval every day

when that budgie emerges, all feathered and green.

You know each of the budgies can only be seen

at a certain fixed interval every day

when that budgie emerges, all feathered and green.

You can photograph multiple budgies at once

and/or one budgie multiple times, if that's best.

If a budgie flies in or out right when you shoot

you will capture it still (so please don't feel too stressed!).

and/or one budgie multiple times, if that's best.

If a budgie flies in or out right when you shoot

you will capture it still (so please don't feel too stressed!).

Now, you want to shoot every bird at least once,

but your film is expensive - try keeping costs low!

Finding out the least number of shots you must take

is your task in this part of the AIIO.

but your film is expensive - try keeping costs low!

Finding out the least number of shots you must take

is your task in this part of the AIIO.

The first line of input will contain the single integer *N*
(1 ≤ *N* ≤ 100,000), the number of budgies. The
following *N* lines will describe the
times when each budgie is visible (and hence able to be photographed).
The *i*'th of these lines will contain two
integers *a _{i}* and

Output should consist of a single integer: the minimum number of shots required to photograph every budgie at least once.

5 0 2 2 4 5 7 6 9 8 10

3

2 60 240 13 37

2

In the first example, you require at least three photos to capture all the budgies. Here is one way:

- Take a photo at time
*t*=2 minutes, capturing budgies 1 and 2. - Take a photo at time
*t*=6 minutes, capturing budgies 3 and 4. - Take a photo at time
*t*=9 minutes, capturing budgies 4 and 5.

In the second example, the budgies appear at completely different times. You have no choice but to take a new photo for each budgie.

- For Subtask 1 (45 points),
*N ≤ 1000*. - For Subtask 2 (55 points), no further constraints apply.

Privacy
statement

© Australian Mathematics Trust 2001-2020

Page generated: 25 May 2020, 11:12am AEST