CROATIAN OLYMPIAD IN INFORMATICS 2015
Time limit: 3 seconds
Memory limit: 512 MB
Page \(1/2\)
A group of Czech tourists is walking in a labyrinth of a strange se\(lf-si\)milar 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.
CROATIAN OLYMPIAD IN INFORMATICS 2015
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@@RISE_MATH_BLOCK_0@@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-bi\)t integer data type (int64 in Pascal, long long in
\(C/C\)++).

생성자가 기록되지 않았습니다.

출처 COCI 2014/2015 Olympiad