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, determine their difference!

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.

Algo the serial composer absolutely loves to write music and does it all the time. In fact, he has composed so many pieces over the years that now he has grown bored of having so much creative freedom and would like to give himself a challenge. Algo will now limit himself to composing with only the notes from a set of $$$N$$$ chosen note lengths, and he wants to match the overall target length of his song exactly.

For instance, if Algo wants to compose a 1-measure song using only quarter notes, half notes, and whole notes—of beat-lengths 1, 2, and 4 respectively—then there are 6 total possible songs that he could compose:

Algo has just been commissioned to write a song that is $$$M$$$ four-beat measures long. Determine how many unique songs ending at exactly $$$M$$$ measures Algo could possibly write, using only his $$$N$$$ chosen notes!

Ice-T has remained a powerful player in the rap game for almost forty years, ever since his debut in the early 80's. It is a little known secret that Ice-T powers his incredible rapping abilities by amassing points in a 2D plane and harvesting all of the 'T's that he can find among them.

A 'T' is defined to be a set of four points $$$A$$$, $$$B$$$, $$$C$$$, and $$$D$$$ where:

1. Points $$$A$$$ and $$$B$$$ are collinear and form a segment $$$\overline{AB}$$$ that is parallel to either the $$$x$$$ or $$$y$$$ axis
2. Point $$$C$$$ rests on the midpoint exactly equidistant between $$$A$$$ and $$$B$$$
3. point $$$D$$$ forms a line segment perpendicular to the $$$\overline{AB}$$$ segment when connected with $$$C$$$

Help Ice-T become even more powerful! Given a set of $$$N$$$ points in 2D space, find the number of 'T's present.

As an avid musician, Santiago loves to practice his music and work on his fundamentals. One of his favorite exercises is playing through arbitrary scales with notes labelled from $$$1$$$ to $$$n$$$ in order. However, he's recently gotten tired of just playing the same scales over and over again and wants to switch up the order of the notes of the scale.

Before playing each note in the permuted scale, Santiago finds the highest previously played note lower than the current note, $$$l$$$, and the lowest previously played note higher than the current note, $$$r$$$, and defines the goodness of the note as the number of notes in the interval $$$(l, r)$$$ (exclusive). If no such $$$l$$$ exists, Santiago takes all notes equal to or below the current note as part of the interval and if no such $$$r$$$ exists, Santiago takes all notes equal to or above the current note as part of the interval.

Santiago then defines the total goodness of the scale ordering to be the sum of the goodness of the notes played within the scale ordering. Santiago feels he gets higher quality practice from scales with higher goodness. Given a proposed scale ordering, output the total goodness of the corresponding scale so that Santiago knows which scale orderings are worth practicing.

Salma is looking to create her new masterpiece symphony. She has created $$$10^{5}$$$ unique small pieces, each piece assigned a unique number between $$$1$$$ and $$$10^{5}$$$ respectively, to potentially use within the symphony (each piece takes the same amount of time to play). During one round of editing, she picked a non-empty subset of those pieces of size $$$n$$$ ($$$1 \leq n \leq 10^{5}$$$) that she wants to use in the symphony.

Now, given those $$$n$$$ pieces, she realized that the combination of those pieces, aka melodic sequence, that tends to sound the best follows the following rule:

• The pieces are played in strictly increasing order (so piece $$$4$$$ must be played before piece $$$5$$$ if both pieces are chosen for the sequence).
• If the sequence is of the form $$$x_1, x_2, \dots, x_k$$$ for some integer $$$k \geq 1$$$, it must be true that $$$\gcd(x_{i-1}, x_{i}) \gt 1$$$ for all integers $$$i$$$ satisfying $$$2 \leq i \leq k$$$.

Salma would like to make her symphony as long as possible so she would like given the $$$n$$$ pieces that she has picked, help her find the length of the longest melodic sequence (satisfying the conditions mentioned above) that she can make.

Yomo "Creati" Maoyorozu, the Everything Hero, is known for her "quirk" to create objects at will by using the amino acids stored up in her body in tandem with her vast knowledge of chemical compounds. As part of her training, Yomo would like to try to create a never-before-seen object by chaining some subset of $$$N$$$ available amino acids into a protein (for the sake of simplicity, assume the order of chaining acids does not matter in this problem).

Each amino acid has a unique ID that is a positive integer, but Yomo realizes that there is a restriction on certain subsets of amino acids being present in a chain. Her chemistry textbook states that having two acids with IDs that sum to a prime number makes a protein extremely prone to denaturation; thus Yomo would like to refrain from using certain amino acids to make her new object so that no two acids present in synthesis will have IDs that sum to a prime number.

Yomo wants your help to find the largest possible number of amino acids that can still be chained together without the resulting protein being susceptible to denaturation.

Mreddie Fercury is the vocalist for the locally famous Queen cover band, and he has been invited to perform his namesake's biggest hits in Moscow. It is quite a far distance from his hometown of Austin, which means Mreddie must travel via a series of flights. Although Mreddie does not particularly enjoy flying, he gets the most overanxious while waiting in airports. Every time he has a layover of $$$t$$$ minutes, his anxiousness increases by $$$t^2$$$ units.

We will define a layover as a contiguous period of time between the arrival of a flight and the departure of the next flight Mreddie boards, or the start of his journey (considered to be minute $$$0$$$) and the first flight Mreddie departs on.

Our protagonist is currently at airport $$$1$$$ in Austin and wants to travel to airport $$$N$$$ in Moscow using some series of the $$$M$$$ flights available to him. Since the total amount of time taken to travel to Moscow does not matter to Mreddie, he will even take flights that go back to the airport he started in to avoid time spent on the ground!

You, Mreddie's travel agent, need to find a sequence of flights that Mreddie can take to make it to Moscow while minimizing the units of anxiousness he accumulates while traveling. Good luck!