Problem B. Countryside Highway
Statement
Regional government wishes to build a new highway across the region, and it seems that the best route for the highway goes across the Kvadratnaya village.
The village consists of the N x N square estates.
All estates have a size of 100 by 100 meters.
Therefore, in the coordinate system tied to the village, the southwestern corner of the village has coordinates (0, 0), and northeastern corner - coordinates (N*100, N*100).
The highway will cross the village form the west to the east side, cutting through several estates. The government decided to compensate owners of those estates, and to estimate the necessary expenses one should calculate the number of estates crossed by the highway.
Given the village size N and the coordinates of the points where the highway crosses eastern and western borders of the village, you must find the number of estates.
You can assume, for the purpose of increasing the financial appeal of the highway project, that the highway is a straight line (i.e. has zero width).
If the highway just touches the edge of an estate, it is still considered a crossing.
The highway is a line between points (0, W) and (100*N, E).
Input file format
In the input file, there are three integers, N, W and E, separated by spaces.
Output file format
Output file must contain a single integer - the number of estates crossed by the highway.
Constraints
1 <= N <= 100
0 <= W, E <= 100*N
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
3 150 50
|
4
|
Problem C. Разделение отрезков
Statement
На прямой задано N отрезков с координатами (L
i, R
i). Требуется определить
минимальное количество прямых, на которых можно было бы разместить эти отрезки без перекрытия.
Input file format
В первой строке файла содержится число N. В следующих N строках содержатся координаты левого
и правого концов отрезков - действительные числа.
Output file format
Выходной файл должен содержать единственное число - минимальное количество прямых.
Constraints
1 <= N <= 100000
0 <= L
i, R
i <= 1000000
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
1
2 3
|
1
|
