레이팅 미적용Time limit: 3 seconds
Memory limit: 512 MB
Page \(1/2\)
A group of Czech tourists is walking in a labyrinth of a strange self-similar shape. The ground plan of
the labyrinth is a Sierpinski triangle – a fractal structure named after the Polish mathematician Wacław
Sierpiński.
The labyrinth consists of a billion rows numbered from 0 to \(10^{9} - 1\) from top to bottom, and a billion columns
numbered from 0 to \(10^{9} - 1\) from left to right. The fields in the labyrinth can be either free or blocked.
The field in row \(X\) and column \(Y\) is free if the result of the bitwise ‘and’ operation on the numbers \(X\) and
\(Y\) is equal to zero, otherwise it is blocked. In other words, a field is blocked if, when \(X\) and \(Y\) are switched
to binary, there is an integer \(k\) such that the \(k^{th}\) digit from the right of the number \(X\) and the \(k^{th}\) digit from
the right of the number \(Y\) are equal to 1.
The first 32 rows and columns \(of\) the labyrinth. The blocked fields are colored \(in\) black.
The Czech tourists are tired from a long day of wandering and would like to meet up in a free field and
exchange experiences. In each step, one tourist can jump to one of the adjacent free fields (up, down, left or
right).
Write a programme that will, based on the current tourists’ locations, determine minimum total number
of steps necessary in order for all the tourists to meet in the same field.
Time limit: 3 seconds
Memory limit: 512 MB
Page \(2/2\)
subtask
subscore
constraints
1
17
\(N = 2\)
0 ⩽\(R_{K}\), \(S_{K} < 10^{9}\)
2
21
2 ⩽\(N\) ⩽100
0 ⩽\(R_{K}\), \(S_{K} < 10^{9}\)
3
22
2 ⩽\(N\) ⩽\(10^{5}\)
0 ⩽\(R_{K}\), \(S_{K} < 500\)
4
40
2 ⩽\(N\) ⩽\(10^{5}\)
0 ⩽\(R_{K}\), \(S_{K} < 10^{9}\)
The first line of input contains an integer \(N\) – the number of tourists. Each of the following \(N\) lines contains
two integers \(R_{i}\) and \(S_{i}\) – the row and column of the field where the \(i^{th}\) tourist is located.
All the tourists are located in free fields, and it is possible that there are multiple tourists in the same field.
The first and only line of output must contain the required minimum number of steps.
Please note: We recommend that you use a 64-bit integer data type (int64 in Pascal, long long in
\(C/C\)++).
2
2 1
4 3
6
2 5
3 4
8 7
9 6
10 5
11 4output
6
50Clarification of the first example: One of the fields where the brave Czech tourists could have met is
(2, 0).
Clarification of the second example: One of the fields where the playful Czech tourists could have met
is (8, 4).