Internet Problem Solving Contest

IPSC 2012

Problem J – Jukebox

The IPSC organisers recently installed a new jukebox in their room. As expected, the jukebox was an instant hit. In fact, there have already been several violent exchanges between people trying to select different songs at the same time, but that is a story for another time. This story is about the jukebox and Milan. As a pianist, Milan likes music and especially likes to play the music he hears. Thus it become unevitable that Milan wants to play music from the jukebox. But here is the problem – the jukebox just contains a lot of recorded music and no music sheets.

In order to recover music sheets from the jukebox, Milan already copied all the music to his laptop. Now he just needs to convert these recordings into music sheets. And that, as you surely guessed, will be your task. Fortunately for you, Milan already made some progress, so you will only need to recover the pitches of separate tones.

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case describes one raw recording. It starts with a line containing a single integer n – the number of recorded samples from a mono microphone. The next n lines will contain a single integer vi – numerical value of i-th sample. The sample rate is 22050 Hz.

Moreover, for your convenience we provide MP3 files named j.{example,easy,hard}.testcase#.mp3 containing the same recordings (except for minor differences due to a lossy MP3 compression).

Output specification

For each test case, output all tones of the song. On the first line, output the count c of tones. On the next lines, output c whitespace-separated tones, where each tone is one of the following strings “A”, “A#”, “B”, “C”, “C#”, “D”, “D#”, “E”, “F”, “F#”, “G”, “G#”.

You may assume that each tone in the input matches one of the twelve musical notes. Note that you do not need to determine the exact octave of the tone.



... (216818 lines)

... (1535091 lines)

D A A G C A A G F D ...(74 more tones)

The first input is the C major scale. The second input is a traditional Slovak folk song ”Tota Heľpa” (for some strange reason also known in Japan as Hasayaki).