408173: GYM103037 D Melodic Harmonies II

Note: The introduction explaining musical frequencies is the same as part 1 of this problem.

As many people know, there are 88 keys on the piano. When a key is pressed, the frequency of the sound produced can be measured. As it turns out, a perfectly tuned piano has as Middle C the frequency of 440 Hz. From there, an octave above is exactly double this, or 880 Hz, and an octave below is exactly 220 Hz. As it turns out, an octave is actually defined mathematically as the note that is double or half of the starting note.

For the notes in between, they happen to be exactly evenly spaced based on the log scale! In fact, given the octave starting at Middle C, the first note to follow Middle C, or D, has a frequency of exactly $$$440 \cdot 2^{\frac{1}{12}}$$$, and the second note has a frequency of exactly $$$440 \cdot 2^{\frac{2}{12}}$$$, and so on and so forth. As it turns out, this pattern holds for all octaves.

Matt has developed a robot that listens to music, and after listening to Alice and Bob's performances of the same song, it has determined the central $$$n$$$ frequencies that make up the melody of both Alice and Bob's performances. Now, given that they performed on an infinitely long piano, and that they both performed for the same time, we can define the difference between the melodies as follows. For every note $$$i$$$, we take the note's difference as $$$b_i - a_i$$$, where $$$b_i$$$ is Bob's note's position on the piano, and $$$a_i$$$ is Alice's note's position on the piano. Taking the sum over all $$$i$$$, we can define the overall difference as the absolute value of that sum.

Given Alice and Bob's melodies in terms of frequencies, we already know how to determine their difference. However, Eve noticed that perhaps, Alice and Bob are playing in different scales! In other words, if we move all of Alice's notes up or down an integer amount on the piano, then the difference with Bob's performance can be reduced. Given this, determine with the best possible movement for Alice, the minimum difference between the two.

The first line of the input will contain $$$n (1 \le n \le 10^4)$$$, the number of notes that both Alice and Bob will play.

The next $$$n$$$ lines of input will each contain two frequencies $$$f_i^a, f_i^b$$$, with the first being Alice's note, and the second being Bob's note that he plays at the same time. It is given that $$$10 \le f_i^a, f_i^b \le 10^{12}$$$. It is guaranteed each frequency will correspond to an exact note on an infinite piano within an error bound of $$$10^{-6}$$$.

A single integer, the minimum possible overall difference between Alice and Bob's performances.

7
440.000000 493.883301
440.000000 493.883301
659.255114 739.988845
659.255114 739.988845
739.988845 830.609395
739.988845 830.609395
659.255114 739.988845

0

The sample input is Alice playing the first 7 notes of Twinkle Twinkle Little Star in C Major, and Bob playing the same piece in D major. Shifting Alice up by 2, there is no difference in their melodies, and hence the minimum possible overall difference is 0.